[book] Beautiful Code - population count

面試的時候 有時會問到, 給你一個數字, 求出他二進位表示當中 有多少個1

ex:

5₁₀ = 101₂ 所以答案就是2 (因為有兩個1)

跳過最直接的解法 (就是一位一位去數), 下面這個方式應該是有看過這題目會提出的解法

 

int pop(unsigned int n)
{
    int count = 0;
    while(n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

建表的方法

int pop(unsigned int n)
{
  char table[256] = {0, 1, 1, ...};
  return table[n & 0xff] + table[(n>>8)&0xff] + table[(n>>16)&0xff] + table[n>>24];
}

但是其實還有其他也蠻有趣的解法~ 就是常常會聽到的divide & conquere

 

int pop2(unsigned int 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;
}

int pop3(unsigned int n)
{
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
// 因為 4bit 互加, 不會干擾到前面的欄位, 也就是不會進位前一個4 bites
// 順便清除 結果8 bits的前4個bits
n = (n + (n >> 4)) & 0x0f0f0f0f;
n = (n + (n >> 8));
n = (n + (n >> 16));
// 因為最高只會是32, 所以最後只要取出我們要得bits(6個bits)
return (n & 0x3f);
}

有了這些, 接下來如果我們要比較x, y誰的1比較多, 當然可以先算出個別的數字在比較
如果要求出兩個數字總共有幾個1, 也可以利用上面4 bits相加部會溢位, 在第三步就先加起來~
相減的話, 可以利用pop(x) - pop(y) = pop(x) - (32 - pop(y')) = pop(x) + pop(y') - 32
y' 是y 的1補數

不過書上提供另一種作法, 就是先把雙方重複的1先刪掉, 在一起數

int pop_comp(unsigned int x, unsigned int y)
{
    unsigned int x1 = x & (~y);
    unsigned int y1 = y & (~x);

    while(1) {
        if(x1 == 0) return y1?-1:0;
        if(y1 == 0) return 1;
        x1 = x1 & (x1 - 1);
        y1 = y1 & (y1 - 1);
    }
}

而且接下來要求出Hamming distance (兩個數字的二進位當中有幾位元不一樣)也很容易
先求出兩個數字的xor, 在找出他二進位有幾個1