如何計算一個整數(shù)中二進制中1的個數(shù)
int fu?nc(int x)
{
int count = 0;
while(x)
{
count ++;
x = x&(x-1);
}
return 0;
}
理解這個算法的核心是：
- 當一個數(shù)被減1時凡桥，它最右邊的那個值為1的bit將變?yōu)?；同時其右邊的所有的bit都會變成1贫奠。
- 每次執(zhí)行
x&(x-1)的作用是把x對應的二進制數(shù)中的最后一位1去掉唬血。因此望蜡，循環(huán)執(zhí)行這個操作直到x等于0的時候唤崭，循環(huán)的次數(shù)就是x對應的二進制中1的個數(shù)。
