求二进制数中 1 的个数

ddatsh

dev #算法

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

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

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