算法：位运算

前言

数据结构和算法是一个程序员的必过的两道门槛，前面我们把常见的数据结构进行了详细的介绍和实现。本专栏将进行学习常见的算法！

本期内容介绍

位运算常见的操作总结

位运算在OJ中的使用解析

位运算常见的操作总结

位运算基础

<<  左移：左边抛弃，右边补0

>> 右移：右边抛弃，左边补符号位

~ 按位取反：将每一位的数字都变为相反（0变1,1变0）

& 按位与：对应位全是1就是1，否则就是0

|  按位或：对应位全是0就是0，否则就是1

^  按位异或：对应位相同为0，相异位1

注意：这里的异或的三个性质：

1、和0异或是本身：n ^ 0 = n

2、和本身异或是0 ：n ^ n = 0

3、a ^ b ^ c = (a ^ c) ^ b

OK，这些位运算符在C语言专栏里面就是非常详细的介绍过的，这里不在多哔哔了；如果有问题的，同学请点击C语言操作符详解

常见的位运算操作总结

1、判断数n的第x位是0还是1 ：（n >> x） & 1

2、将数n的x位修改为1：n |=（1<<x）

3、将数n的x位修改为0：n &= ( ~(1 << x))

4、提取数n的二进制的左右侧的1：n & -n

5、删掉数n最右侧的1：n & (n-1)

OK，理论就这么多，下面直接来看看实践中如何使用！

位运算在OJ中的使用解析

191.位1的个数

思路一：遍历这个数的32个比特位，计数1的位的个数

思路二：利用上面的结论4，每次判断完之后将最低的1的位给丢弃

338.比特位计数

这道题就是让你统计一下0~n之间每个数i的的二进制数目！和上一道题几乎一样！直接上代码：

461.汉明距离

实现思路：异或后求1的个数！

477.汉明距离总和

思路一（超时）：这道题是求一个数组中的任意两个数汉明距离，所以可以暴力枚举数组中的所有两个数，然后利用上一题的思路逐一统计即可！

思路二：统计出数组中所有元素的每一位的 0和1的个数！将他们相乘的结果就是该位置的两两数不同的组合数！例如：有3个是1,2个是0则，两两组合且位值的不同情况是2 * 3 = 6；如下图：

136.只出现一次的数字

实现思路：如果没有常量级别的空间限制的话，可以用哈希表！这里常量的空间的话就是用位运算了，按照上述介绍的异或的性质1和2即可

137.只出现一次的数字2

实现思路：因为只有一个数出现了一次，其他数都出现了三次。所以统计数组中的每个元素的第i位，如果该位置的1的个数是3的倍数则说明就是出现三次的元素的1，如果不是则就说明该位置有4个元素，一个必定是单独的那个的1，将返回值的该位置设置为1即可！

260.只出现一次的数字3

实现思路：将所有的元素异或，就得到了只出现一次的那两个元素的异或值！然后找出异或值的是1的位置pos，按照pos位置进行对整个数组的元素进行异或到两个数字里面，左后这两个数字就是只出现一次的那两个数字！

371.两整数之和

看到这个题目，一开始以为是梦开始的第一道题~结果一看o.0

实现思路：利用异或的无进位相加，求出没有进位的和，在求出进位；然后将进位（左偏移一位）和刚刚求出的无进位的和在进行重复上述的操作，直到进位为0即可！

如何获取无进位相加的和：a ^ b；如何求进位: a & b

这个题可以有两种写法即循环和递归！

递归：

循环：

消失的两个数字

这道题虽然是困难题，但是如果你是把上面的位运算的基本操作全部理解了并把上述的题目理解的情况下这道题其实是可以做出来的！下面我们用两种方法介绍一下这道题：

实现思路一：先将1~n的所有数字全部异或到sum里面，然后再将数组的所有元素也异或到sum；此时就转换成了上麦刚做的只出现一次的数字3，按照上面介绍的思路做即可！

实现思路二：数学；

先将1到n的所有元素之和求出sum，sum在减去数组的所有元素，此时身下的就是丢失的量元素的和！因为是1-n中的数丢失的两个，所以这两个数是不可能重复！所以这两个数一个必定小于sum / 2一个一定大于sum / 2；所以此时就转化成了，从sum / 2为界限的两个区间中中找丢失的那个数字！用1到sum/2的和减去数组中的小于sum / 2的那些元素，剩下的就是前半个区间丢失的那个，用sum - 前半个区间丢失的数就是后半区间的那个数！