LeetCode.191.Number of 1 Bits 位1的个数

题目描述

191 Number of 1 Bits
https://leetcode-cn.com/problems/number-of-1-bits/
https://leetcode.com/problems/number-of-1-bits/description/

Write a function that takes an unsigned integer and return the number of ‘1’ bits it has (also known as the Hamming weight).

Example 1:

Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

 
Note:
Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3 above the input represents the signed integer -3.
 
Follow up:
If this function is called many times, how would you optimize it?

---

解题过程

统计所有位上1的个数-对2求余

本来是很简单的题，依次模2取余数之和，但忽略了输入是无符号整型。
其实我都不知道java中的所有整型都是有符号的，java不支持无符号整型。
第一提交后得了个Wrong Answer，错误用例是：2147483648 (10000000000000000000000000000000)

不知道后台是怎么把这个数传给int类型的参数的，反正我本地直接用2147483648测试，连编译都通不过

后来专门查了java中怎么处理无符号整型，原来都要转为更多位数的整型类型（比如用int表示无符号short，用long表示无符号int），所以转为long型提交一次，通过了：

private static class SolutionV2018 {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        long unsignedn = n & 0xFFFFFFFFL; //用long型表示无符号int
        int result = 0;
        while (unsignedn > 0) {
            result += unsignedn % 2;
            unsignedn = unsignedn / 2;
        }
        return result;
    }
}

统计所有位上1的个数-移位和位运算

可以把 n 不断 逻辑右移>>> 与 1 做 “与” 运算，注意一定是逻辑右移，也就是右移左补0
也可以把 1 不断左移和 n 做 “与” 运算

public static int hammingWeight(int n) {
    int ones = 0;
        while(n!=0) {
            ones = ones + (n & 1);
            n = n>>>1;
        }
        return ones;
}

注意两点：

• 1、右移1位（也就是除以2）要用逻辑右移（无符号右移）操作符>>>，保证高位永远补0
• 2、循环结束条件必须是n!=0，不能用n>0，因为无符号测试用例2147483648在java中表示-2147483648，如果用n>0判断直接无法进入循环。

还有人提到，Integer类直接就提供一个计算整型的二进制表示中1的数量的方法：
Integer.bitCount(int i)，返回指定 int 值的二进制补码表示形式的 1 位的数量

只统计1的个数(将最右边的1设为0:x&(x-1))

x&(x-1) 可将 x 最右边的 1 设为 0，我们不断重复这个操作，直到x为0，就是1的个数

Java中Integer.bitCount()的源码分析

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

首先要了解一个运算：对于一个两位的二进制数，他的 "1" 的数量 = 二进制数本身 - 二进制的高位
验证：
原值 - 高位 = 1个数
00 - 0 = 0;
01 - 0 = 1;
10 - 1 = 1;
11 - 1 = 10 = 2;

第一行代码 i = i - ((i >>> 1) & 0x55555555);，的目的就是统计每两位二进制中1的个数，解释如下：
i>>>1 是将每两位的高位右移，由于
0x55555555 = ‭0b01010101010101010101010101010101‬
所以 (i >>> 1) & 0x55555555 是把每2位的高位清零，i - ((i >>> 1) & 0x55555555) 就是 原值 - 每两位的高位，把结果再存储到 i 中。
这时 i 中存储了每两位的统计结果，可以进行两两相加，最后求和。

第二行代码 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 的目的是把每四位中的高两位和低两位相加，也就是统计每四位中1的个数
i >>> 2 是将 每四位 中的 高两位 移到 低两位，和
0x33333333 = ‭0b00110011001100110011001100110011‬
进行 “与” 操作就是只保留这低两位，然后 (i & 0x33333333) + ((i >>> 2) & 0x33333333) 就是 每四位中的高两位和低两位相加

第三行代码 i = (i + (i >>> 4)) & 0x0f0f0f0f; 是统计每8位中1的个数，也就是每个字节中1的个数
由于这个值最大是 8(0b1000)， 只占字节的一半，所以不需要像前两行代码那样分别得出高低位后再运算，运算完再把高四位清零即可

第四行代码 i = i + (i >>> 8); 是统计每两个字节的1个数

第五行代码 i = i + (i >>> 16); 是统计 4 字节的 32 位整型的 高两个字节中1的个数 和 低两个字节中1的个数 之和。

最后 i & 0x3f 是因为 32 位整型中 1 的个数最多是 32 个，也就是 0b100000 最多占 6 个位，所以与 0x3f = ‭0b00111111‬ 做与运算，把高位的全部清零即可。

            二进制                       十进制
1  0   1  1   1  1   1  1   1  1     10 11 11 11 11
 01     10     10     10     10       1 2  2  2  2
         \     /       \     /           \/    \/
 01       0100           0100         1   4    4
               \       /                   \  /
 01               1000                1      8
     \          /                       \   /
         1001                             9

---

GitHub代码

algorithms/leetcode/leetcode/_191_NumberOf1Bits.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_191_NumberOf1Bits.java

---