Количество битов (может повторять столько же раз, как число битов)

Question

Возможный дубликат:
Best algorithm to count the number of set bits in a 32-bit integer?
Counting the number of bits that are set

Как найти число битов в целое число без знака, когда ему разрешено итерировать цикл столько же раз, сколько установлено количество бит (если установлены 3 бита, вы можете повторять цикл всего 3 раза)

Answer 1

Это метод, который я знаю для этого, он будет перебирать только для числа битов в v, в конце выполнения c будет содержать число битов в v:

unsigned int v; // count the number of bits set in v 
unsigned int c; // c accumulates the total bits set in v 
for (c = 0; v; c++) 
{ 
    v &= v - 1; // clear the least significant bit set 
} 

источник : C Язык программирования 2-е изд. (Брайан У. Керниган и Dennis M. Ritchie)

пример:

v = 1010; //2 bits are set 
v - 1 = 1010(10 decimal) - 1 = 1001(9 decimal) 

1010 
1001 & 
------ 
1000   The least significant bit is unset, c is incremented by 1 

v = 1000 
v - 1 = 1000 - 1 = 0111 

1000 
0111 & 
------- 
0000   The least significant bit is unset again, c is incremented 
      by 1, the loop stops because there are no more set bits.