数字的位运算

问题描述（一）

  输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

问题分析

正向分析

  负数用补码表示本来就是计算机存储的一般特征，这里单独强调，说明本题的解决思路本来就是涉及位操作的。所以我们这个时候开始就把所有的位操作的相关特征进行筛选。

• 首先是与操作，同1则1其余为0，可以帮我们把数字中指定为上的1筛选出来，举个例子，要把一个数二进制后四位的1提取出来，则构造一个数，这个数后四位是1，那就是(1111)b，然后拿构造出来的数去与，把与的结果就是提取的结果。但是无法直接用作计数。
• 或操作和与操作类似，同0则0其余为1，可以帮我们把数字中指定位上的0筛选出来，这里也排除。
• 异或，两数相同则为0，相异则为1，在排除重复的数字上有点用，这里也不考虑。同或，相同则为1，相异则为0。
• 取反，只在判断的时候有用，或者配合其他操作。
• 移位，左移可以代替乘法，右移可以代替除法。
    分析完这些位操作的功能，大致可以根据这些功能去构造算法了。与操作可以把指定位的1提取出来，如果我们要来计数，可以考虑每一次提取一个1然后去计数。
    这里会遇到一个问题，就是直接去判断每一位的话，相当于为了提取每一位与的数字都不一样，不便操作，我们可以把与操作和移位操作结合起来的方式。每一次把要提取的位移位到最低位就行了，这样一下就将问题统一起来。（这里还可以采用循环遍历，每次把数右移一位，然后提取新的最低位，但是代码更为复杂）。
    统计多少个1，最后将提取出来的1求和就行了。

python代码

  分析完之后，就会发现这个思路其实很简单，一个循环就够了，因为使用的是python，代码写出来很简洁。这里的限制是数的表示是32位，如果是64位，则要统计64次。

def NumberOf1(n):
	return sum([(n>>i & 1) for i in range(0,32)])

扩展分析

  因为这个分析全部是基于位操作的，整个过程没有和负数用补码相背。很多人看到这个问题可能会想到将对应的二进制数字转为字符串然后去统计，这种思路也是可以的，但是负数就需要和正数分开处理了。需要对负数做一个处理，这里不详细解释。
  还有人想到我们上面的分析设计到&1的位操作，这个操作可以被替换为%2，涉及到移位的位操作，我们可以把这个操作换成 $/2^n$。但是这一个操作的替换有一个前提是这个数得是正数，第二个操作的替换虽然没有正数的限制，但是会使得负数移位后计数变得非常困难。
  关于本题，我在《剑指offer》看到一种解法，特来补充一下，在位操作里，还有一种骚操作，$n\&(n-1)$就可以把一个数字最右边的1给去掉，大致证明就是$2^n\&(2^n-1)=0$，这也是这种解法中最核心的东西。建议大家记下来，以备将来解题之用。根据这种操作，每一次可以删掉数字最右边的一位1，然后直到整个数字为0。这种算法中的循环就不需要执行固定的次数，而数字中有多少个1循环执行多少次。

C++代码

  这里解释一下，这个算法是不好写成python代码的，因为python里的int类型是不会溢出的，高位不停的会有1补齐下来，所以负数又得单独处理了。

int  NumberOf1(int n) {
	int count = 0;
	while (n)
	{
		count++;
		n &= n - 1;
	}
	return count;
}

问题描述（二）

  一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

题目分析

暴力求解

  暴力解法就是构建一个哈希表，统计一下每个数出现的次数，最后把只出现一次的数给找出来。在暴力法的基础上，我们可以做一些空间的优化，判断一个值是否在这个哈希表里，如果在，就把它删除，如果不在则把它加入，这样可以更加的节省空间，但是并没有降低空间复杂度。暴力法的代码略略略。

位运算求解

  上面我们提到过异或可以排除重复的数字，这个排除的次数必须是偶数次。直接说数字帮助理解，$n\oplus n=0，n\oplus n\oplus n=n$，而这个认识就是做这道题的基础。根据这个性质有一个推论，如果一个数组里全是重复两次的数，那么对这个数组所有的数字执行异或，最终的结果就是0。在此基础上，如果一个数组中，只有一个数字出现了一次，其他的所有数字都出现了两次，那么这个数组异或的结果就是这个数字。所以如果数组满足这个条件，从数组中把这个数字找出来，采用异或的复杂度是$O(n)$，而哈希表只能做到理论上的$O(n)$，并且利用了额外空间。
  有了以上对于异或操作的理解，做这道算法题，还是很难啊，因为两个数，虽然得到了这个两个数的异或结果，但是无法得到这两个数啊。接下来就想有没有什么策略了。
  一个很巧妙的分析是：如果这两个数不同，则异或结果一定不为0，则必有一位异或的结果是1。我们找到这个异或结果为1的位，显然说明一个问题，这两个数的二进制数在这个位上一定一个是1，一个是0。$(10{)}_b\oplus (11{)}_b=(01{)}_b$，最低位为1，说明两个数最低位不同，一定一个是1，一个是0。我们把这个数组分为两组，就根据这个位数上1还是0。这样划分的结果就是，这两个数肯定不在同一个组里，相同的数肯定在同一个组里。所以就把一个数组分成了两个，只有一个数字出现了一次，其他数字出现了两次的数组。这个问题我们会解决，那就是对所有的数字异或即可。

python代码

  我写代码一直都比较短，最开始只写了四行，不便于理解，这里给大家写一个长一点的版本。

from functools import reduce # py3需要导入，py2内置reduce函数
def FindNumsAppearOnce(self, array):
    def FindNumsAppearOnce(array):
    tmp = 0
    list1 = []
    list2 = []
    for i in array:
        tmp ^=  i
    index_ = bin(tmp).replace('0b', '')[::-1].index('1') # 找出异或结果为1的最低位
    for i in array:
        if i>>index_&1==1:
            list1.append(i)
        else:
            list2.append(i)
    tmp1 = 0
    tmp2 = 0
    for i in list1:
         tmp1 ^= i
    for i in list2:
        tmp2 ^= i
    return tmp1, tmp2

总结

  数字的位操作作为一种有效的策略在数字判断的很多地方起到了出乎意料的作用，但是基础是关键，需要熟练了解各种位操作的特点，然后将其嵌入到算法题的求解过程中，使用得当，大家一定会事半功倍。

最后

以上就是落后电灯胆为你收集整理的数字的位运算的全部内容，希望文章能够帮你解决数字的位运算所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。