计算位1的个数方法总结

tags: DSA C++ Python

写在前面

之前介绍过一种计算整数二进制表示中位​​1​​个数的文章, 是介绍通过不断减去右移一位之后的值的方法来完成的, 后来发现还有一种更快更经典的方法, 下面来总结下.

​​191. 位1的个数 - 力扣（LeetCode）​​;

各种思路

转换字符串

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;
    }
};

最经典的位运算

​​统计二进制展开中数位1的个数的优化 - Maples7 - 博客园 (cnblogs.com)​​;

分组计算

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;
    }
};