题目描述:
光棍们对 1 总是那么敏感, 因此每年的 11.11 被戏称为光棍节. 小 Py 光棍几十载, 光棍自有光棍的快乐. 让我们勇敢地面对光棍的身份吧, 现在就证明自己: 给你一个整数 a, 数出 a 在二进制表示下 1 的个数, 并输出.
例如: a=7
则输出: 3
分析:
看到这个题目, 我们大多想到的是 "左移" 或者 "右移","与" 操作等, 然后根据自己的想法很快写出函数, 并输入 7,10 等整数验证, 但是这个题目中, 我们需要注意, 一个整数的范围是多少, 有多少位, 是正整数还是负整数, 在 Python 中, 我们要知道, Python 中似乎没有数据位数的概念, 数据位数与虚拟内存有关, 在我们认为溢出之后, python 会自动将 int 类型转换为 long 类型.
方法 1: 左移 & 右移法
我们首先想到的一般都是右移, 一直移动到数字为 0 即可, 如下代码所示:
- # -*- coding: utf-8 -*-
- # @Time :2018/11/23 21:48
- # @Author :AstroBoy
- # @Site :
- # @File :CalcBinaryNum_1.py
- # @Software :PyCharm
- def CalcBinaryNum(num):
- cnt = 0;
- while(num):
- if (num & 1):
- cnt += 1
- num = num>> 1
- return cnt
我们输入一个负数, 发现系统很久没有输出结果, 这是因为程序已经陷入了死循环, 这是因为, 在计算机程序语言中, 负数在计算机中是用补码表示的, 负数的补码最高位为 1, 向右移动时, 最高位一直用 1 来填充, 所以 while 循环条件一直为真. 既然右移的方法不可取, 那么我们就利用左移, 在用 32 位表示的整数中, 左移 32 位 1 就会变成 0, 这可以作为判断条件, 但是在 python 中左移并不会简单的溢出, 而是自动扩展位数. 为了在 python 中使用 c 语言, 可以利用 python 的库库 ctypes, 代码如下:
- #!/usr/bin/python
- # -*- coding: utf-8 -*-
- # @Time :2018/11/26 21:27
- # @Author :AstroBoy
- # @Site :
- # @File :CalcBinaryNum_Ctype.py
- # @Software :PyCharm
- from ctypes import *
- def CalcBinaryNumByCtype(num):
- count = 0
- flag = 1
- while(c_int(flag).value):
- if (c_int(flag & num).value):
- count += 1
- flag = flag <<1
- return count
- print(CalcBinaryNumByCtype(5))
- print(CalcBinaryNumByCtype(-1))
方法 2: 大众算法
上述代码需要循环移位 32 次才能得到结果, 我们可以利用 N & (N -1) 的方法, 把整数的二进制中最右边的二进制从 1 变为 0
- #!/usr/bin/python
- # -*- coding: utf-8 -*-
- # @Time :2018/11/28 20:18
- # @Author :AstroBoy
- # @Site :
- # @File :CalcBinaryNumByCtype_2.py
- # @Software :PyCharm
- from ctypes import *
- def CalcBinaryNumByCtype(num):
- cnt = 0;
- while(c_int(num).value):
- cnt += 1
- num = num & (num -1)
- return cnt
- print(CalcBinaryNumByCtype(5))
- print(CalcBinaryNumByCtype(-1))
方法 3: 库函数方法
当前我们可以借助 Python 特有的库函数 bin, 来解决该问题
- #!/usr/bin/python
- # -*- coding: utf-8 -*-
- # @Time :2018/11/28 20:25
- # @Author :AstroBoy
- # @Site :
- # @File :CalcBinaryNumByBin_1.py
- # @Software :PyCharm
- #!/usr/bin/python
- # -*- coding: utf-8 -*-
- # @Time :2018/11/28 20:18
- # @Author :AstroBoy
- # @Site :
- # @File :CalcBinaryNumByCtype_2.py
- # @Software :PyCharm
- def CalcBinaryNumByBin(num):
- if (num>= 0):
- nbin = bin(num)
- return nbin.count('1')
- else:
- num = abs(num)
- nbin = bin(num - 1)
- return 32 - nbin.count('1')
- print(CalcBinaryNumByBin(5))
- print(CalcBinaryNumByBin(-1))
当前还有更简单的做法, 利用 python 的特性:
- #!/usr/bin/python
- # -*- coding: utf-8 -*-
- # @Time :2018/11/28 20:46
- # @Author :AstroBoy
- # @Site :
- # @File :CalcBinaryNumByBin_2.py
- # @Software :PyCharm
- def CalcBinaryNumByBin(num):
- nbin = bin(num & 0xffffffff)
- return nbin.count('1')
- print(CalcBinaryNumByBin(5))
- print(CalcBinaryNumByBin(-1))
在 python 中, 负数与 0xFFFFFFFF 按位与, 实际上按照语法, 负数在做与操作之前会先把自己转为计算机中的二进制表示形式, 然后与 0xFFFFFFFF 做与操作, 也就变成了一个二进制表示的无符号数
方法 4: 查表法
除以上方法外, 还有查表的方法, 先建立一个存储 0 到 15 的二进制中 1 的个数的列表, 然后计算的时候每 4 位进行一次查表.
- #!/usr/bin/python
- # -*- coding: utf-8 -*-
- # @Time :2018/11/28 21:04
- # @Author :AstroBoy
- # @Site :
- # @File :CalcBinaryNumByList.py
- # @Software :PyCharm
- counts = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]
- def CalcBinaryNumByList(num):
- result = 0
- for i in range(0,32,4):
- result += counts[(num>> i) & 0xf]
- return result
- print(CalcBinaryNumByList(5))
- print(CalcBinaryNumByList(-1))
当前还有其他优秀的算法比如平行算法, 如果利用 C 或者 C++ 语言还有位域的方法, 不再一一列举.
- Reference:
- https://www.cnblogs.com/cotyb/p/5186461.html
来源: https://juejin.im/post/5bf563b4f265da616b105696