转载

由统计整数二进制中1的个数来窥算法之美妙

原文发表在我的博客主页，转载请注明出处

前言

我一直是一个比较喜欢算法的人，觉得算法真的是相当美妙和神奇！！！趁春节有时间看看算法书，体会思想和技术沉淀下来的美妙，今天看到了统计二进制中1的个数这个原本很简单的题目，之前也看过，不过这次看书加深入思考之后发现里面的水还是很深的，特别是用python的程序猿更应该明白，闲话少说，开始正题。

题目

实现一个函数，输入一个整数，输出该数二进制表示中1的个数

题目分析

拿到这个题目，所有人肯定立马有了思路，几个关键词立马在脑海中显现：“循环”，“右移”，“与”。然后很快写出了函数，随便输入几个数验证，没问题。。。但是这个题目需要注意的首先是整数，包括正整数和负整数，其次在python中，数据位数是一个比较模糊的概念，在程序中基本不存在，因为越位之后他会自动将int转为为long类型，所以对python程序员来说，需要提前搞明白整数的位数，或者在python语言中调用C语言，下面来列举其中的集中解法。

技巧：python中的左移和右移与其他C/C++等的定义和结果都是不一样的，大家可以自行做实验，python中的定义：右移n位定义为除以pow(2,n)，左移n位定义为乘以pow(2,n)，而且没有溢出（移除的int会升级为long类型）

解法

上面题目分析的时候说过每个人看见题目心中都会涌现出最naive但是不对的解法（不论用什么语言）：

def count(num):     cnt = 0     while num:         if num & 1 == 1:             cnt += 1         num = num >> 1     return cnt

为什么说他不对呢，大家可以输入一个负整数看看，程序会陷入死循环，因为在其他语言中，负数在计算机中是用补码表示的，最高位是1，在右移的过程中，高位都是用1来填补的，所以 while num 这个条件一直为真；在python中，根据右移的定义就可以自行推断出来。既然现在右移num不行，那我们可以左移1，在32的整数中，最多左移32位，1就会变为零，所以这可以作为判断条件，这在C语言中可以写出和上面类似的代码，但是在python中，我们一起可以左移下去（到虚拟内存大小的位数），所以这里我用到了python中的库 ctypes ，在python中使用C语言，代码如下：

from ctypes import * def count(num):     cnt = 0     flag = 1     while c_int(flag).value:         if c_int(num & flag).value:             cnt += 1         flag = flag << 1     return cnt

上面的代码不论输入正数负数还是零，都可以得到正确的答案，但是对于所有的整数都需要循环32次才能得到结果，继续改进。看一个简单的例子，整数12的二进制表示为1100，将其减一变为1011，将得到的结果和原树进行按位与，得到1000，所以发现规律没有？把一个整数减去1之后再和原来的整数做按位与，得到的结果相当于是把整数的二进制表示中最右边的一个1变成0，按照这个规律进行遍历，则函数的循环次数为二进制中一的个数次。代码如下：

from ctypes import * def count(num):     cnt = 0     while c_int(num).value:         cnt += 1         num = (num -1) & num     return cnt

技巧：把一个整数减去1之后再和原来的整数做按位与，得到的结果相当于是把整数的二进制表示中最右边的一个1变成0

以上都是各种语言通用的方法，只不过是以python作为例子而已，那么在python中语言中可以利用他的库函数很容易的解决这个问题，代码如下：

    def num_of_one(self, n):         '''         count the num of "one" in num n         bin():convert the num to binary string         :param n: num n         :return: the num of "one" in n         '''         if n >= 0:             nbin = bin(n)             return nbin.count('1')         else:             n = abs(n)             nbin = bin(n-1)             return 32 - nbin.count('1')