二进制中1的个数
程序员文章站
2022-07-02 19:12:17
前言
最近会手写一些常考的面试题目,测试通过后会跟大家分享一下
移位法
仅适应于正数的做法:
移位法就是每次判断n的二进制的最低位是否为1,时间复杂度为o(logn)
&...
前言
最近会手写一些常考的面试题目,测试通过后会跟大家分享一下
移位法
仅适应于正数的做法:
移位法就是每次判断n的二进制的最低位是否为1,时间复杂度为o(logn)
int nativeonenum(int n) { int count = 0; while (n) { if (n & 1) count ++; n >>= 1; } return count; }
对于正数没问题,但是如果n为负数,这里就出现问题了,以负数-8为例,二进制补码形式为11111111|11111111|11111111|11111000|,右移一位之后,变成了11111111|11111111|11111111|11111100|,因为是负数,所以符号位会一直补1,导致最后全1,出现死循环
针对这种情况,我们可以用变量flag =1,从右向左去和n比较,32位int最多比较32次即可知道n中1的数量
int onenum(int n) { int count, flag; for (count = 0, flag = 1; flag; flag <<= 1) { if (flag & n) count ++; } return count; }
快速法
这种解法的思路是,二进制中1的个数只与1的位数有关,n & (n - 1)快速的去掉最左边的1,例如7(0111) & 6(0110)= 6(0110),快速的去掉了最左边的1
int quickone(int n) { int count = 0; while (n) { count ++; n = n & (n - 1); } return count; }
上一篇: JSP指令元素
推荐阅读
-
vue.js 1.x与2.0中js实时监听input值的变化
-
linux shell 中 2>&1的含义
-
让Word页眉或页脚中显示的页码从 1 以外的值开始
-
浅谈python中np.array的shape( ,)与( ,1)的区别
-
php中可能用来加密字符串的函数[base64_encode、urlencode、sha1]
-
详解JS取出两个数组中的不同或相同元素
-
Shell脚本中判断输入参数个数的方法
-
Shell脚本中不同进制数据转换的例子(二进制、八进制、十六进制、base64)
-
NET 在一个数组中查找另一个数组所在起始位置(下标从0开始,未找到返回-1)
-
Python实现在某个数组中查找一个值的算法示例