Задача об оптимальном подчсёте единичных битов в целочисленном типе. Моя реализация основана на использовании малой дополнительной памяти, из-за чего скорость вычисления пропорцианалься Օ(1). Это стандартный алгоритм, применяемый во многих известных мне библиотеках, просто я сам до него допёр когда столкнулся с такой задачей по работе.
Code:
#include <iostream>
struct byte {
static const unsigned char ones_in_nibble[];
unsigned char low: 4;
unsigned char hi: 4;
inline unsigned char getones() const {return ones_in_nibble[low] + ones_in_nibble[hi];}
};
const unsigned char byte::ones_in_nibble[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
unsigned char getBitCount(unsigned int n) {
byte* bytes = (byte*)&n;
return bytes[3].getones() + bytes[2].getones() + bytes[1].getones() + bytes[0].getones();
}
void binOutput(unsigned int n) {
for(int i = ((sizeof(n) << 3) - 1); i >= 0; std::cout << ((n >> i--) & 1));
}
int main() {
const unsigned int num = 0xaabbccdd;
std::cout << "The binary number (";
binOutput(num);
std::cout << ") has in total of " << (int)getBitCount(num) << " set bits.";
return 0;
}
P.S. Пытаюсь писать наиболее самокоментируемый код, во избежание тривиальных
комментариев.