-
题目
- 请实现一个函数,输入一个整数,输出该数二进制表示中 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;
}
}
}
网友评论