剑指offer-二进制中1的个数

题目描述

• 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
• 地址：牛客链接

解决方法：

• 方法1：因为输入可能是负数，所以利用 >>> 逻辑右移 符号，来使每一位与 1 进行位与，若结果为1，则count++，直至n右移变为0
• 方法2：利用一个 int 类型的辅助值 temp,初始值为1。来和n进行位于，若结果不为0，说明n的二进制当前位置上为1，count++; temp一直左移，直至溢出为0。
• 方法3：利用 n & (n - 1) 能消除掉二进制最右边1的性质：例如 5（0101）与 4（0100）位与，结果为 0100，最右边的1消除了，然后0100继续与0011与，结果为0000，同样消除了最右边的0，这样来迭代更新 n并计数，直至n变为0.
  原理： n-1的二进制与n的二进制相比，是把n的二进制最右边的1变为了0，然后以前1后面所有的0（如果存在）变为了 1，这样两者进行位与，以前最右边1及其右边都变为了0

经验教训

• 注意逻辑右移 >>> 与 >>的区别，后者带着符号位右移，并在高位补与符号位相同的数字，正数补0，负数补1
• 注意不论是正数还是负数，在计算机都都是以补码的形式存储的，并且位运算也是直接对补码进行运算（进行位运算时，只关于补码，无需纠结正负）,，关于原码，反码，补码，见详解原码反码与补码
• n & (n - 1) 的妙用
• 在java中，对于1<<32，那么会输出1；但是对于(1<<31)<<1，那么会输出0；其底层对左移做了一些处理，即如果移动的位数超过了该类型的最大位数，那么编译器会对移动的位数取模。如对int型移动33位，实际上只移动了33%32=1位

代码实现

• 方法1：

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

• 方法2：

    public int NumberOf1(int n) {
        int count = 0;
        int temp = 1;
        while (temp != 0) {
            if ( (n & temp) != 0) {
                ++count;
            }
            temp = temp << 1;
        }
        return count;
    }

• 方法三

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