[数据结构与算法]LeetCode-338-比特位计数

1、Brian Kernighan 算法

算法的核心思想在于对于任意整数x，每次都将x与x-1相与，从而让其二进制的最后一位1变成0。我们可以利用算法计算出每一个数的1的个数并输出。

class Solution {
public:
    int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }

    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        for (int i = 0; i <= n; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }
};

2、找规律

Bits[0]=0，Bits[1]=1，而后偶数位的值等于其一半的值，奇数位的值等于上一个的值加1。

vector<int> countBits(int n) {
    if (n == 0) return {0};
    vector<int> Bits(n + 1, 0);
    Bits[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (i % 2 == 0) Bits[i] = Bits[i / 2];
        else Bits[i] = Bits[i - 1] + 1;
    }
    return Bits;
}

3、动态规划法-最高有效位

我们可以利用highBits记录当前的最高有效位：1、若$i\&(i?1)=0$，说明当前值为2的幂，只有一个有效的1，最高有效位更新为i；2、i比i-highBits的二进制表示多一个1，令$bits[i]=bits[i?highBits]+1$。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
};

4、动态规划法-最低有效位

我们将当前数字除二，相当于右移一位，此时若当前值为偶数则末位为0无影响；若为奇数则需要加1。相当于$bits[i]=bits[i/2]+i\%2$。实际上等同于方法二。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
};

5、动态规划法-最低设置位

根据Brian Kernighan 算法，实际上$i\&(i?1)$相当于找到i二进制表示中最后一位为1的数改为为0的数，因此显然$Bits[x]=Bits[x\&(x?1)]+1$。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    }
};