模拟题 07 二进制中1的个数

• 题目
  • 请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 思路

  • 如果二进制数量小于128位， 查表
  • 如果二进制数量大于等于128位，swar算法来计算汉明重复。

• 代码

public class Solution {
    private static byte[] wightInBit = {25, 26, 26, 27, 26, 27, 27, 28, 26, 27, 27, 28, 27, 28, 28, 29, 26, 27, 27, 28, 27, 28, 28, 29, 27, 28, 28, 29, 28, 29, 29, 30, 26, 27, 27, 28, 27, 28, 28, 29, 27, 28, 28, 29, 28, 29, 29, 30, 27, 28, 28, 29, 28, 29, 29, 30, 28, 29, 29, 30, 29, 30, 30, 31, 26, 27, 27, 28, 27, 28, 28, 29, 27, 28, 28, 29, 28, 29, 29, 30, 27, 28, 28, 29, 28, 29, 29, 30, 28, 29, 29, 30, 29, 30, 30, 31, 27, 28, 28, 29, 28, 29, 29, 30, 28, 29, 29, 30, 29, 30, 30, 31, 28, 29, 29, 30, 29, 30, 30, 31, 29, 30, 30, 31, 30, 31, 31, 32, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7};

    public int hammingWeight(int n) {

        if(n <= Byte.MAX_VALUE && n >= Byte.MIN_VALUE) {
            return wightInBit[n +128 ];
            # 汉明重复 swar 算法
        } else {
            n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
            //第二步
            n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
            //第三步
            n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
            //第四步
            n = (n * (0x01010101) >> 24);
            return n;
        }
    }
}