YongXMan's Blog » 首页 » 关于 » 归档

比如一个32位的无符号整型,如果要统计其中二进制中1的个数,直接从最低位遍历,不管二进制中1的个数有多少,时间复杂度是一样的。

还有比较快速的计算方式:

int countOneBit(unsigned int num) {
int count;
for (count=0;num>0;count++) {
num &= num - 1;
}
return count;
}

每次位与运算都会将其中最后一位比特1置0,直到所有位都是0结束。

对应优化在Tidis中bitcount命令,commit 6f1f7e9

(完)