剑指offer15:二进制中1的个数

题目：

请实现一个函数，输入一个整数，输出该二进制中表示1的个数.

对于二进制运算，主要是按位与、或、非. 1与1相与为1，1与0相与为0. 因此,算法主体为：

while(n){
    if(n & 1)
        count ++;
    n = n >>1;
}

以上代码最容易想到，对于输入大于等于0的数而言，以上代码没有问题. 当输入负数时，负数在计算机中补码形式存在，右移时左边填1，以上代码会陷入死循环. 既然不能右移，可以使用左移替代.

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

以上代码的移动次数依赖于计算机是多少位的. 拓展：当一个整数减去1再与原数相与的时候，会把该数最右边的1变为0. 通过此方式，该数二进制中有多少个1，则计算几次.

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

判断一个数是否是2的整数次方. 若一个数是2的整数次方, 那么该数的二进制表示中必定只有一位为1, 将此数-1, 那么从为1的位开始与原值相反, 此时与原数相与必为0, 否则不是二的整数次方.

bool f(int n){
    if((n-1) & n)
        return false;
    return true;
}

给定两个数A与B, 计算将A的2进制表示变换为B的二进制需要改变A中多少位. 两个数的异或能统计出两个数哪些位置不一样, 然后统计异或结果中1的个数即可.

int A2B(int m, int n){
    unsigned int flag= m ^ n;
    return NumberOf1(flag);
}