LintCode 二进制中有多少个1题目分析

desperate633

发布于 2018-08-22 09:52:21

2030

发布于 2018-08-22 09:52:21

文章被收录于专栏：desperate633

题目

计算在一个 32 位的整数的二进制表式中有多少个 1.

样例给定32(100000)，返回1

给定5(101)，返回2

给定1023(111111111)，返回9

分析

方法一普通法

最容易想到的方法，通过移位加计数，一个个计算统计1的个数

public int countOnes1(int num){
        int count = 0;
        while(num!=0){
            if(num%2==1)
                count++;
            num=num/2;
        }
        return count;
    }

改进的普通法

用位操作替代方法一

public int countOnes2(int num){
        int count = 0;
        while(num!=0){
            count +=num&0x01;
            num = num>>1;
        }
        return count;
    }

方法三快速法

这种方法速度比较快，其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0 为什么n &= (n – 1)能清除最右边的1呢？因为从二进制的角度讲，n相当于在n - 1的最低位加上1。举个例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的1（也就是最低位的1）

public int countOnes3(int num){
        int count = 0;
        while(num!=0){
            num = num & (num-1);
            count++;
        }
        return count;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016.11.24 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二进制

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二进制

登录后参与评论

0 条评论

热度