如何计算一个二进制数字中1出现的次数

2019-03-22 14:40:23   最后更新: 2019-03-22 14:40:23   访问数量:896




闲来无事,在博客园里看到一篇博客

如何统计二进制中 1 的个数

 

感觉解法非常新颖,分享一下

 

这个问题描述起来很简单,一句话,实际上解决起来也很简单

 

解法及代码

想知道最右边一位是否为 1,只需要用这个数和 1 按位与,判断结果为 0 或是 1 就可以,接着,只要循环按位右移原数字,直到原数字变为 0 即可

def NumberOf1(n): count = 0 while n != 0: count += n & 1 n = n >> 1 return count if __name__ == '__main__': print(NumberOf1(24183))

 

 

运行结果:11

 

存在的问题 -- 负数与补码

一旦传入的数字变成负数,就会进入死循环,原因就在于计算机对于负数的存储 -- 2的补码

计算机保存负数的方式是2的补码,简单的来说,一个整数 * -1 后的结果为该整数按位取反再加 1:

 

 

计算机为什么要这样存储呢?因为计算机只有加法器没有减法器,两个数的减法运算会被计算机转换为加法运算,而补码恰恰解决了这个问题

 

在 python、php 等语言中,在数字的实际位数超过预定位数,解释器会通过字符串的方式去处理数字

从而只要内存够大,就可以支持无限小的负数,这类语言因为不使用传统的数字存储方式,所以探讨其数字中 1 的数量是没有意义的

针对 python 语言,在 python2 中,我们可以通过 sys.maxint 获取到上面说的“预定位数”的最大数字来计算,在 python3 中 sys.maxint 更换为了 sys.maxsize,因此我们这里只探讨数字的绝对值小于等于 maxsize 的情况

 

针对上面的题目,大部分编程语言在移位操作时,会在高位补符号位,也就说,对于负数而言,右移操作会在高位补 1,于是无论怎么右移,数字 n 永远不会变成 0

那么基本的解决思路有下面几个:

  1. 利用 java 语言的 >>> 操作,让解释器强制在高位补 0
  2. 预先定义最大移位次数变量
  3. 对负数的最高位直接置 0,然后使用上述程序,并在最终将结果加 1

 

方法 1 是最简单的,但是其他大部分语言并不支持

方法 2 需要知道数字的位数,这在不同语言,不同编译环境中是不同的

方法 3 可行,但是如果想要做到就要先获取最高位为 0 其他位均为 1 的数字,在 C/C++ 、java 等语言中,我们可以通过移位操作来实现,但是和上述理由相同,python、php 等语言中仍然是无法实现的

 

方法1 -- java

package cn.techlog.test.springboot.service; public class NumberOfOne { private static int numberOfOne(int n) { int count = 0; while (n != 0) { count += n & 1; n = n >>> 1; } return count; } static void main(String args[]) { int count = numberOfOne(-3); System.out.println(count); } }

 

 

java 语言的 >>> 让这个问题简单了不少,不幸的是其他语言很少有这样便捷的操作

 

方法2 -- python

import sys def NumberOf1(n): count = n & 1 maxtime = len(bin(sys.maxsize)[2:]) while n != 0 and maxtime > 0: n = n >> 1 count += n & 1 maxtime -= 1 return count if __name__ == '__main__': print(NumberOf1(-3))

 

 

我们通过 len(bin(sys.maxsize)[2:]) + 1 得到了最大能够移位的次数,从而限制循环次数,得到正确的结果:

63

 

方法3 -- C++

#include <iostream> using namespace std; int numberOfOne(int n) { int count = 0; while (n != 0) { count += (n & 1); n = (n >> 1); } return count; } int numberOfOneV2(int n) { int base = 1; if (n >= 0) { return numberOfOne(n); } while ((base << 1) > 0) { base = ((base << 1) | 1); } n = n & base; cout << "base: " << base << endl; cout << "n: " << n << endl; return numberOfOne(n) + 1; } int main () { int count = numberOfOneV2(-3); cout << count << endl; return 0; }

 

 

上述代码中,我们通过将初始值为 1 的变量 base 进行移位,从而得到我们所需要的除符号位全 1 数字,从而实现对负数符号位的复位

最终得到答案:

base: 2147483647

n: 2147483645

31

 

山不过来我过 -- 引入测试位

上述所有方法我们都是通过对传入参数移位实现的,如果不对传入参数移位,而是使用测试位,就不会出现上述的问题了

#include <iostream> using namespace std; int numberOfOneV3(int n) { int flag = 1; int count = 0; while (flag != 0) { if ((flag & n) != 0) { count++; } flag = flag << 1; } return count; } int main () { int count = numberOfOneV3(-3); cout << count << endl; return 0; }

 

 

高效新颖的解法

下面是最巧妙的一个方法,基本思路是把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0

 

 

那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作

public static int NumberOfOneV4(int n) { int count = 0; while (n > 0) { count++; n = (n - 1) & n; } return count; }

 

 

欢迎关注微信公众号,以技术为主,涉及历史、人文等多领域的学习与感悟,每周三到七篇推文,全部原创,只有干货没有鸡汤

 

 

https://www.cnblogs.com/edisonchou/p/4752086.html

 






技术帖      算法      c语言      python      技术分享      java      algorithm     


京ICP备15018585号