- 题目来源：《The C programming language》中的习题P38
- 练习2-9： 在求对二的补码时，表达式x &= (x-1)可以删除x中最右边值为1的一个二进制位。请解释这样做的道理。用这一方法重写下面的bitcount函数，以加快其执行速度。
#include<stdio.h> void main(){ unsigned x = 0645; // 110_100_101 int a = bitcount(x); printf("%d\n",a); } /*bitcount:获得x（二进制）中1的个数*/ int bitcount(unsigned x){ int b = 0; for(;x != 0; x >>= 1){ if(x & 1){ b++; } } return b; }
解题思路：对于x的二进制形式，分为两种：最右边二进制位为0和最右边二进制位为1
- 如果x的形式如XXX1, 那么x & （x-1）应该为 XXX0 & XXX1 = XXX0。 例如: 110_100_101 & 110_100_100 = 110_100_100。最右边的1被删除。
- 如果x的形式如XX10..00, 那么x & （x-1）应该为 XX01..11 & XX10..00 = XX00..00例如： 110_100_100 & 110_100_011 = 110_100_000。最右边的1被删除。
代码实现：
#include <stdio.h> void main() { unsigned x = 0645; // 110_100_101 int count = 0; while (x != 0) { x &= (x-1); count++; } printf("1-bit count: %d\n", count); }