【编程之美】 2.1 统计一个正整数二进制中1的个数

发表于

普通法

1
2
3
4
5
6
7
8
int countBinary1(int num) {
    int sum = 0;
    while (num) {
        sum += num % 2;
        num /= 2;
    }
    return sum;
}

移位法

1
2
3
4
5
6
7
8
int countBinary2(int num) {
    int sum = 0;
    while (num) {
        sum += num & 1;
        num >>= 1;
    }
    return sum;
}

快速法
这个效率是与1的个数有关，超级牛逼！

1
2
3
4
5
6
7
8
int countBinary3(int num) {
    int sum = 0;
    while (num) {
        num &= (num - 1);
        sum++;
    }
    return sum;
}

还有以空间换取时间的方法,列出一个很大是数组，直接返回， 时间复杂度是O(1).
参考文章