求二进制中 1 的个数

Tips

《编程之美》 记录

解法一 ： 除法

int count(int v){
    int num = 0;
    while(v){
        if(v % 2 == 1)
            num++;
        v /= 2;
    }
    return num
}

解法二 ： 位运算

效率较解法 一 较高 ， 时间复杂度 O（log₂n ）

int count(int v){
    int num = 0;
    while(v){
        if(v & 1)
            num++;
        v >>= 1;
    }
    return num;
}

解法三

让算法复杂度只与 二进制数中 1 的个数有关， 当然最坏情况下 为 O(log₂n)

int count(int v){
    int num = 0;
    while(v){
        v = v & (v - 1);  // 依次将最右面的 1 消去
        num++;
    }
    return num;
}

解法四 : 分支运算

把所有结果都罗列出来， 不可取

解法五 ： 查表

空间换时间， 复杂度O(1), 需谨慎使用, 以下为 0 到 255 的

int countTable[256] = {
    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,
    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,
    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,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

int Count(int v){
    return countTable(v);
}