Q15_二进制中1的个数.java

package com.algorithm.demo.剑指Offer;

/**
 * 请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，
 * 有 2 位是 1。因此，如果输入 9，则该函数输出 2。
 * 如果 n & 1 = 0, 则 n 的最后一位是 0 ；如果 n & 1 = 1, 则 n 的最后一位是 1。
 * <p>
 * 基于这两个特点，可以统计出最后一位是否为 1，如果为 1，则更新记录统计的 1 的个数，然后将 n 右移一位，
 * 这样就能统计到原来 n 的倒数第二位，依次操作；如果为 0，则不需要更新记录统计的 1 的个数，
 * 直接将 n 右移一位。
 * <p>
 * 符号	描述	示例	运算规则
 * &	与	A & B	A 和 B 都为 1 时，结果为 1
 * |	或	A | B	A 和 B 都为 0 时，结果为 0
 * ^	异或	A ^ B	A 和 B 相同为 0 ，相异为 1
 * ~	取反	~A	0 变 1 ，1 变 0
 * <<	左移	A<<	全部左移若干位，高位丢弃，低位补 0
 * >>	右移	A>>	全部右移若干位，对无符号数，高位补 0 ，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补 0（逻辑右移）
 */
public class Q15_二进制中1的个数 {

    public static void main(String[] args) {
        int result = hammingWeight2(10);
        System.out.println("result=" + result);
    }

    /**
     * 先判断证书二进制表示中最右边一位是不是1；接着把输入的整数右移一位，此时原来处于从右边数起的第二位被移动到最右边了，在判断是不是1；
     * 这样每次移动一位，知道整个整数变为0为止。现在的问题变成了怎么判断一个整数的最右边是不是1。只要把整数和1做位与运算看结果是不是0。
     * 时间复杂度为 O(log2n)。
     * 空间复杂度为 O(1)。
     *
     * @param n
     * @return
     */
    public int hammingWeight(int n) {
        //用来保存统计到的结果
        int res = 0;
        //不断的右移n ， 直到为 0
        while (n != 0) {
            //统计结果
            res = res + (n & 1);
            //无符号右移 1 位
            n = n >>> 1;
        }
        return res;
    }

    /**
     * 如果一个整数不等于0，那么该整数的二进制表示中至少有一位是1。先假设这个数的最右边一位是1，那么减去1时，最后一位变为0而其他所有位都保持
     * 不变。也就是最后一位相当于做了取反操作，由1变成0。
     * 假设最后一位不是1而是0的情况。如果该整数的二进制表示中最右边的1位于第m位，那么减去1时，第m位由1变成0，而第m位之后的所有0都变成1，整数中
     * 第m位之前的所有位都保持不变。例：一个二进制数1100，它的第二位是从最右边数起的一个1。减去1后，第二位变成0，他后面的两位0变成1，而前面的1
     * 保持不变，因此得到的结果是1011。
     * 在前面两种情况中，发现把一个整数减去1，都是把最后变的1变成0。如果它的右边还有0，则所有的0都变成1，而它左边的所有位都保持不变。接下来我们
     * 把一个整数和它减去1的结果做位与运算，相当于把它最右边的1变成0。还是以前面的1100为例，它减去1的结果是1011。我们再把1100和1011做位与运算，
     * 得到的结果是1000。我们把1101 最右边的1变成了0，结果刚好就是1000。
     * <p>
     * 把一个整数减去1，再和原整数做与运算，会把该整数最右边1变为0。那么一个整数的二进制表示中有多少个1，就进行多少次操作。
     *
     * @param n
     * @return
     */
    public static int hammingWeight2(int n) {
        int count = 0;
        while (n != 0) {
            ++count;
            n = (n - 1) & n;
        }
        return count;
    }


}