面试题：二进制中1的个数（剑指offer）
题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。如把9表示成二进制是1001，有2个1.因此输入9时，输出2。
题记：
与、或、异或的运算规律
00001010<<2=00101000 10001010<<=301010000
右移运算符m>>n，表示把m右移n位。右移n位时，最右边的n位舍弃，同时在在最左边补上n个0（无符号数）或补上n个1（有符号数）。
例如两个有符号数（0表示整数，1表示负数）：
00001010>>2=00000010 10001010>>3=11110001
解题思路1：
判断整数二进制表示中最右边一位是否为1，接着把整数右移一位，判断倒数第二位是否为1，以此类推，直到整数变成0为止。现在问题变为如何判断一个整数的最右边是不是1了。只要将该整数与1做位与运算即可。因为1的二进制表示为0001，如果一个整数的二进制与1做与运算，结果是1，表示该整数的二进制的最右边一位是1，否则是0。
功能函数：
int numberofbit1(int n) { int count=0; while(n) { if(n & 1) count++; n=n>>1; } return count; }
分析以上程序，如果输入一个负数，如果一直对该负整数的二进制进行右移操作，最终这个数就会变成全1，从而陷入死循环。例如：
-5的二进制表示为1101（最左边的1表示负数），对其进行右移操作如下：
1101>>1=1110 1101>>2=1111 1101>>3=1111 1101>>4=1111
为了避免上述死循环的出现，有下面的解题思路。
解题思路2：
可以不右移输入的数字，先将输入数字和1做与运算，判断最低位是否为1，接着将1左移一位，判断倒数第二位是否为1，以此类推。
功能函数：
int numberofbit1(int n) { int count=0; int flag=1; while(flag) { if(n & flag) count++; flag=flag<<1; } return count; }
分析以上程序会发现，循环的次数等于整数二进制的位数，显然循环次数较多。
解题思路3：
把整数减去1，在和原整数做与运算，会把整数最右边的一个1变成0，那么一个整数的二进制表示中有多少个1，就可进行多少次这样的操作。显然可以减少循环次数。
例如，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的1（也就是最低位的1）。
功能函数：
int numberofbit1(int n) { int count=0; while(n) { ++count; n=n & (n-1); } return count; }
注：把一个整数减去1后，再和原来的整数做与运算，得到的结果相当于将整数的二进制表示中的最右边一个1变成0。很多二进制的问题都可以用这个思路解决。
解题思路4：（来自博客：http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html）
先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。
以217（11011001）为例，下面的图足以说明一切了。217的二进制表示中有5个1。
功能函数：
int numberofbit1(int n) { n = (n & 0x55555555) + ((n>>1) & 0x55555555) ; n = (n & 0x33333333) + ((n>>2) & 0x33333333) ; n = (n & 0x0f0f0f0f) + ((n>>4) & 0x0f0f0f0f) ; n = (n & 0x00ff00ff) + ((n>>8) & 0x00ff00ff) ; n = (n & 0x0000ffff) + ((n>>16) & 0x0000ffff) ; return n ; }
测试程序：
int main() { int a,b,c,d,num=0; printf("解题思路1 "); printf("请输入一个整数："); scanf("%d",&a); num=numberofbit1_1(a); printf("整数%d的二进制表示有%d个1。 ",a,num); printf(" "); printf("解题思路2 "); printf("请输入一个整数："); scanf("%d",&b); num=numberofbit1_2(b); printf("整数%d的二进制表示有%d个1。 ",b,num); printf(" "); printf("解题思路3 "); printf("请输入一个整数："); scanf("%d",&c); num=numberofbit1_3(c); printf("整数%d的二进制表示有%d个1。 ",c,num); printf(" "); printf("解题思路4 "); printf("请输入一个整数："); scanf("%d",&d); num=numberofbit1_4(d); printf("整数%d的二进制表示有%d个1。 ",d,num); printf(" "); system("pause"); return 1; }
测试结果：
