黑马程序员技术交流社区

标题: 一个int数n,问其二进制数中1的个数,有哪些简便方法 [打印本页]

作者: Buer 时间: 2016-8-5 13:09
标题: 一个int数n,问其二进制数中1的个数,有哪些简便方法
如题,求一个整数的二进制形式中,"1"的个数

作者: cat73 时间: 2016-8-5 19:13
写出时间复杂度 O(sizeof(int)) 的代码并不难。
结果 += 数字 & 1
数字 = 数字 >> 1
循环执行直至数字为 0 即可。

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

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

作者: Buer 时间: 2016-8-6 12:49
除了这个最笨的方法，遍历数字二进制字符串，数1的个数，还有其他简便算法吗。求详解

1470458890192..jpg (72.01 KB, 下载次数: 6)

作者: yuxing 时间: 2016-8-6 23:42
拿个正整数举例
int n;
int count =0;
while(n >=0) {
n = n & n-1;
count++;
}
输出count就可以了

作者: ylca 时间: 2016-8-7 01:11
本帖最后由 ylca 于 2016-8-7 01:18 编辑

[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;

    }

作者: Buer 时间: 2016-8-7 15:37

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

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

作者: Buer 时间: 2016-8-7 15:38

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

是个好办法,受教受教

作者: yuxing 时间: 2016-8-7 18:30

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

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

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

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

作者: 阿卜 时间: 2016-8-8 13:35
Integer.bitCount(n) 就可以了

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2