編寫一個(gè)函數(shù)返回?cái)?shù)字的二進(jìn)制位中‘1’的個(gè)數(shù)。
方法一，遞歸
int findOneinBin(int n)
{
if(n<2)
return 1;
else return n%2+findOneinBin(n/2);
}
這個(gè)方法很容易想到，如果是奇數(shù)的話就是他的n/2+1，也就是有一位加上1個(gè)1.
方法二，google一下找出來(lái)的，沒(méi)看懂
#define POW(c) (1<<(c))
#define MASK(c) (((unsigned long)-1) / (POW(POW(c)) + 1))
#define ROUND(n, c) (((n) & MASK(c)) + ((n) >> POW(c) & MASK(c)))
int bit_count(unsigned int n)
{
n = ROUND(n, 0);
n = ROUND(n, 1);
n = ROUND(n, 2);
n = ROUND(n, 3);
n = ROUND(n, 4);
return n;
}
一下子看不明白，先把宏展開來(lái)：
POW是計(jì)算2的冪
MASK很奇怪，一個(gè)全1的無(wú)符號(hào)數(shù)字除以2的冪的冪加1？
好在打印出來(lái)還能看得懂：
MASK(0) = 55555555 h = 01010101010101010101010101010101 b
MASK(1) = 33333333 h = 00110011001100110011001100110011 b
MASK(2) = 0f0f0f0f h = 00001111000011110000111100001111 b
MASK(3) = 00ff00ff h = 00000000111111110000000011111111 b
MASK(4) = 0000ffff h = 00000000000000001111111111111111 b
這些mask分別把32位數(shù)字劃分為幾個(gè)部分。每個(gè)部分的前一半和后一半分別是全'0'和全'1'。
MASK(0)分為16個(gè)部分，MASK(1)分為8個(gè)部分，...
ROUND中對(duì)n的處理：(n & MASK) + (n >> POW & MASK)
POW的值剛好是MASK中連續(xù)'0'(或者連續(xù)'1')的長(zhǎng)度。也就是說(shuō)ROUND把由MASK分開的n的各個(gè)部分中的高POW位和低POW位相加。
為了便于說(shuō)明，取一個(gè)簡(jiǎn)單的部分：MASK(1)的0011
假設(shè)n的值為1001，那么ROUND后的結(jié)果就是10 + 01 = 11 b，把這個(gè)結(jié)果賦值給n，這時(shí)n的含義由原來(lái)的二進(jìn)制位串變?yōu)?1'位的數(shù)量。特別的，當(dāng)ROUND(n, 0)時(shí)，把n當(dāng)作一個(gè)32個(gè)部分各自'1'位的數(shù)量。（'0'表示沒(méi)有'1'，而'1'則表示有1個(gè)'1'）
計(jì)算完n = ROUND(n, 0)后，n是一個(gè)16個(gè)部分各自'1'位數(shù)量的'數(shù)組'，這個(gè)'數(shù)組'的每個(gè)元素只有2個(gè)二進(jìn)制位。最大值為2，足夠由2個(gè)二進(jìn)制位來(lái)表示。
接下來(lái)，計(jì)算完n=ROUND(n,1)后，n是一個(gè)8個(gè)部分各自'1'位數(shù)量的'數(shù)組'，這個(gè)'數(shù)組'的每個(gè)元素只有4個(gè)二進(jìn)制位。最大值為4，足夠由4個(gè)二進(jìn)制位來(lái)表示。（實(shí)際只需要3個(gè)二進(jìn)制位）
...
最后一步，計(jì)算n=ROUND(n,4)后，n是一個(gè)1個(gè)部分各自'1'位數(shù)量的'數(shù)組'，這個(gè)'數(shù)組'的每個(gè)元素有32個(gè)二進(jìn)制位。最大值為32，足夠由32個(gè)二進(jìn)制位來(lái)表示。（實(shí)際只需要6個(gè)二進(jìn)制位）
這個(gè)代表32位內(nèi)'1'位數(shù)量的32位二進(jìn)制數(shù)也就是我們要求的結(jié)果。