如题,求一个整数的二进制形式中,"1"的个数

写出时间复杂度 O(sizeof(int)) 的代码并不难。
结果 += 数字 & 1
数字 = 数字 >> 1
循环执行直至数字为 0 即可。

[quote]cat73 发表于 2016-8-5 19:13
写出时间复杂度 O(sizeof(int)) 的代码并不难。
结果  = 数字

没看懂，可以贴个具体代码吗

除了这个最笨的方法，遍历数字二进制字符串，数1的个数，还有其他简便算法吗。求详解

拿个正整数举例
int n;
int count =0;
while(n >=0) {
n = n & n-1;
count++;
}
输出count就可以了

[Java] 纯文本查看 复制代码

        static int BinaryCount2(int i){
                int c = 0;
                while(i>0){
                        if((i%2)==1){
                                c++;
                        }
                        i>>=1;
                }
                return c;
                
        }
        static int BinaryCount(int n) {
        int c = 0; // 计数器
        while (n > 0) {
            if ((n & 1) == 1) {
               c++;// 计数器加1
            }
            n >>= 1; // 移位
        }
        return c;
    }

yuxing 发表于 2016-8-6 23:42
拿个正整数举例
int n;
int count =0;

循环能结束吗.........  我想问的就是 n = n & n -1; 这句的意思. 什么意思呢

ylca 发表于 2016-8-7 01:11
[mw_shl_code=java,true]        static int BinaryCount2(int i){
                int c = 0;
           ...

是个好办法,受教受教

Buer 发表于 2016-8-7 15:37
循环能结束吗.........  我想问的就是 n = n & n -1; 这句的意思. 什么意思呢

用位运算符 消除二进制的最后一个1.
n  =     (n&n-1)
这样应该看懂了吧

[quote]yuxing 发表于 2016-8-7 18:30
用位运算符 消除二进制的最后一个1.
n  =     (n

虽然不理解为什么能消除1，但确实是见过最简练的方法，赞\(≧▽≦)/。
还有循环条件应该是＞0，不可以等于。谢谢

Integer.bitCount(n) 就可以了