题目描述：
光棍们对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：
