Как быстро посчитать кол-во единиц в двоичном числе

starmaster

Мб у проца команда есть специальная для этого?

starmaster

Значит команды нету
Жаль.
Спасибо за ссылку.

kachokslava

существенно завязано на 32-битность int.
для 64-битных надо будет модифицировать

navstar



int bit_count (unsigned int x)
{
static const char bit_count_array [] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
int res;
for (res = 0; x > 0; x >>= 8)
res += bit_count_array [x & 0xFF];
return res;
}

navstar

или так (хотя этот вариант зависит от размера типа int)


int bit_count (unsigned int x)
{
x = (x & 0x55555555) + x >> 1) & 0x55555555);
x = (x & 0x33333333) + x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + x >> 16) & 0x0000FFFF);

return x;
}

Оставить комментарий
Имя или ник:
Комментарий: