二进制中1的个数

《剑指offer》面试题15：二进制中1的个数

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

最优解法思路：将整数减去1后再与原来的整数做与运算，得到的结果相当于把原来的整数的二进制表示中最右边的1变为0。做了多少次运算，该整数的二进制表示中就有多少个1。

代码如下：

public static int getNumOf1InBinary(int n) {
    int count = 0;
    while (n != 0) {
        count++;
        n = (n - 1) & n;
    }
    return count;
}

相关题目：
1、用一条语句判断一个整数是不是2的整数次方。（一个整数如果是2的整数次方，那么它的二进制表示中有且仅有一位是1，其它所有位都是0）。

思路：将这个整数减去1之后再和它自己做与运算，这个整数的二进制表示中唯一的1变为0，即这个整数变为了0。

代码如下：

public static boolean judgeIntegerIsPowerOfTwo (int n) {
    return ((n - 1) & n) == 0;
}

2、输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制表示为1010,13的二进制表示为1101，需要改变1010中的3位才能得到1101。

思路：第一步求这两个数的异或；第二步统计异或结果中1的个数。

代码如下：

public static int changeMToN (int m,int n) {
    int temp = m ^ n;
    int count = 0;
    while (temp != 0) {
        count++;
        temp = (temp - 1) & temp;
    }
    return count;
}