Changchun Master Li

one form to understand Hamming weight 一个表理解汉明重量

2015-08-12

There are three solutions to calculate hamming weight.

bruce force

1
2
3
4
5
6
7
8
int hammingWeight(uint32_t n) {
    int count = 0;
    while(n != 0) {
        count += n %2;
        n = n /2;
    }
    return count;
}

lowbit

operator AND between n with n-1 will remove the right 1.

1
2
3
4
5
6
7
int hammingWeight(uint32_t n)
{
    int count = 0;
    for(; n > 0; ++ count)
        n &= n - 1;
    return count;
}

tree pattern

1
2
3
4
5
6
7
8
9
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;
}

分划和为所求结果

wikipedia

Tags: algorithm
← Python异步队列实现生产者消费者模式 An Introduction to Machine Learning Theory and Its Applications →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章