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

题目

计算在一个 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;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏十月梦想

PHP输出语句

prinf_r()是PHP的内置函数可以输出任意的数据(变量,数组,字符串),也是只能输出一个数据

1066
来自专栏mathor

枚举+优化(7)——前缀和1

1727
来自专栏十月梦想

ES6语法基础之变量解构赋值(数组)

ES6变量解构赋值,看下数组与es5等区别,ES6的新特性大大节省了代码量,使代码可读性大大提高!

842
来自专栏Python

Python 里 and、or 的计算规则

引子: >>> print '' or 5 or 0 5 >>> print 5 and 4 4 >>> print '' or 5 or 0 and 4 5 ...

1899
来自专栏java一日一条

常见Java面试题– 第一部分:非可变性(Immutability)和对象引用(Object reference)

由于字符串前后都有空格,因为有些人可能会认为结果是”Hello World”。那么,这个题目想要考察的是什么呢?

732
来自专栏遊俠扎彪

C++中的字符数组、字符串、字符指针的一些笔记

1、sizeof会计算实际内存空间,strlen会计算C风格的字符串的实际字符数(不包括\0)。

19610
来自专栏计算机视觉

Python 函数使用记录,join函数和os.path.join用法

1.join()函数 语法:‘sep’.join(seq) 参数说明: sep:分隔符。可以为空 seq:要连接的元素序列、字符串、元组、字典等 上面的语法即:...

2907
来自专栏十月梦想

函数的return(返回值)

return之后,函数就停止,return之后的语句将不执行,但是php也不会报错。

1183
来自专栏linux驱动个人学习

typeof关键字的作用

一、typeof详解: 前言:     typeof关键字是C语言中的一个新扩展,这个特性在linux内核中应用非常广泛。(其实这和C++的auto关键字和可以...

3375
来自专栏数据结构笔记

数据结构(四):栈的应用之表达式求值

用户从控制台输入一个数学表达式(所有输入均合法),数学表达式只包含四则运算,程序需输出表达式对应的结果,如:

1012

扫码关注云+社区

领取腾讯云代金券