写在前面
之前介绍过一种计算整数二进制表示中位1个数的文章, 是介绍通过不断减去右移一位之后的值的方法来完成的, 后来发现还有一种更快更经典的方法, 下面来总结下.
各种思路
转换字符串
def calcbit1_v1(n):
return bin(n).count("1")
# return n.bit_count()
取最低位
def calcbit1_v2(n):
ans = 0
while n:
tmp = n & 1 # 取最末位
ans += tmp
n >>= 1 # 进位
return ans
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans{};
while (n) ans += (n & 1), n >>= 1;
return ans;
}
};
加减法
def calcbit1_v3(n):
total = 0
tmp = n
while tmp:
tmp >>= 1
total += tmp
return n - total
def calcbit1_v4(n):
diff = n
while n:
n >>= 1
diff -= n
return diff
之前介绍过, 比较超出常规的方法.
class Solution {
public:
int hammingWeight(uint32_t n) {
auto diff{n};
while (n) n >>= 1, diff -= n;
return diff;
}
};
另一种取最低位的方法
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans{};
while (n) n &= n - 1, ++ans;
return ans;
}
};
最经典的位运算
分组计算
class Solution {
public:
int hammingWeight(uint32_t n) {
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
return n;
}
};