02_Python学习笔记之统计整数二进制中1的个数

光棍们对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：

• www.cnblogs.com/cotyb/p/518…

• www.cnblogs.com/graphics/ar…