剑指Offer-二进制中1个个数

转自https://www.cnblogs.com/AndyJee/p/4630568.html

题目：

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：

很明显，这道题考察的是位运算。

1、依次将整数右移，判断整数最后一位是否为1(&1)；

问题：如果该整数为负数，则会陷入无限循环，为什么？因为负数右移的时候，左边补1，整数右移过程中不可能为0，因此会陷入无限循环。

补码的移位：

左移，无论正数负数都在右边补0；

右移，正数在左边补0，负数在左边补1；

int  NumberOf1( int  n){
    int  count=0;
    while (n){
        if (n&1)
            count++;
        n=n>>1;
    }
    return  count;
}

2、依次将1左移i位，然后跟该整数做与&操作，如果结果不为0，则第i位为1；

问题：整数有多少位，就得循环多少次。

3、利用小技巧

x&(x-1)可以将整数最右边的1变成0，通过这个小技巧，我们只要循环判断n=n&(n-1)是否为0，即可统计1的个数。

整数中有多少个1，则循环多少次。

4、位运算相关题目

• 用一条语句判断一个整数是不是2的整数次方。

if(n&(n-1)==0) return true;

• 输入两个整数m,n,计算需要改变m的二进制表示中的多少位才能得到n？

int x=m^n; return NumberOf1(x);　　

代码：

#include <iostream>

using  namespace  std;

int  NumberOf1_shift( int  n){
    int  count=0;
    unsigned  int  flag=1;
    while (flag){
        if (n&flag)
            count++;
        flag=flag<<1;
    }
    return  count;
}

int  NumberOf1_fast( int  n){
    int  count=0;
    while (n){
        count++;
        n=n&(n-1);
    }
    return  count;
}

int  main()
{
    cout <<NumberOf1_shift(-8)<< endl;
    cout <<NumberOf1_fast(-8)<< endl;
    return  0;
}

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/8ee967e43c2c4ec193b040ea7fbb10b8?rp=1

AC代码：

class  Solution {
public :
     int   NumberOf1( int  n) {
         int  count=0;
         while (n){
             count++;
             n=n&(n-1);
         }
         return  count;
     }
};