4.6 应用 x&(x-1)


原理


x&(x-1)可以消除数字x二进制表示的最后一个1,如:

int x = 0xf6;
printf("%x\n", x);		//0b11110110 
printf("%x\n", x&(x-1));	//0b11110100

判断一个正数是不是2的次幂


如果一个正数是2的次幂,则这个数的二进制表示中只含有一个1。

int x;
if(x&(x-1)){
	//x至少含有两个1,所以不是2的次幂
} 

计算一个数的二进制含有多少个1


x中的最后一个1可以通过操作x = x&(x-1)循环消去,当最后x值为0时,便可以求出二进制中1的个数。

int x, total;
while(x > 0){ 
	x = x&(x-1);
    total++;
}