判斷一個整數的二進制位中有多少個1

// 判斷一個整數的二進制位中有多少個1

void totalOne(int x)

{

int count = 0;

while(x)

{

x = x & ( x - 1 );

count++;

}

printf("count = %d/n", count);

}

循環： x = x & ( x - 1 ); count++; 直到x為0為止。該方法的時間複雜度是O(m)

在此，不妨把x的二進制位表示為

          x=an-1an-2...a0。

按從低位到高位的順序，不失一般性，假設x的第i位為第一個為1的二進制位，即：ai=1。此時有：

          x       =an-1an-2...ai+1100...0              <1>

         (x-1)  =an-1an-2...ai+1011...1              <2>

很明顯，從式1和式2可以得出，在第一次 x & (x-1) 後：

          x=an-1an-2...ai+1000...0

之後重複同樣操作，直到x的二進制位中沒有1為止

從上面可以看出，每執行過一次 x & (x-1) 後，都會将x的二進制位中為1的最低位的值變為0，并記數加1。

目前而言，一個整數最大64bit，所有三種方法執行起來都可以認為是0(1)。