LeetCode OJ: 191. Number of 1 Bits (Hamming weight) 漢明重量

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

題目連接,筆者一開始很單純一個一個bit去算:

int hammingWeight(uint32_t n) {
    int bitCnt = 0;
    uint32_t v = n;
    while( v > 0 ) {
        if( v & 0x01 ) bitCnt++;
        v = v >> 1;
    }

    return bitCnt;
}


但看了Discuss後,才知道原來在Wiki上有幾種比較快速的解法,底下列出筆者比較容易理解的版本:

//This is better when most bits in x are 0
//It uses 3 arithmetic operations and one comparison/branch per "1" bit in x.
int popcount_4(uint64_t x) {
    int count;
    for (count=0; x; count++)
        x &= x-1;
    return count;
}


沒有留言: