美文网首页
模拟题 07 二进制中1的个数

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

作者: 格林哈 | 来源:发表于2020-09-30 16:06 被阅读0次
  • 题目
    • 请实现一个函数,输入一个整数,输出该数二进制表示中 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;
        }
    }
}

相关文章

网友评论

      本文标题:模拟题 07 二进制中1的个数

      本文链接:https://www.haomeiwen.com/subject/bszuuktx.html