求二进制数中 1 的个数

不断清除 n 的二进制表示中最右边的 1,同时累加计数器,直至 n 为 0

运算次数与输入 n 的大小无关,只与 n 中 1 的个数有关

1
2
3
4
5
6
7
int bitCount(unsigned int n) {
    unsigned int c;
    for (c = 0; n; ++c) {
        n &= (n - 1); // 清除最低位的1
    }
    return c;
}