位运算的常用技巧

1、找出一个没有重复的数

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。
这道题可能很多人会用一个哈希表来存储，每次存储的时候，记录 某个数出现的次数，最后再遍历哈希表，看看哪个数只出现了一次。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)了。

然而我想告诉你的是，采用位运算来做，绝对高逼格！

我们刚才说过，两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身，所以我们把这一组整型全部异或一下，例如这组数据是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出现了一次，其他都出现了两次，把他们全部异或一下，结果如下：

由于异或支持交换律和结合律，所以:

1^2^3^4^5^1^2^3^4 = （1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。

也就是说，那些出现了两次的数异或之后会变成0，那个出现一次的数，和 0 异或之后就等于它本身。就问这个解法牛不牛逼？所以代码如下

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

时间复杂度为 O(n)，空间复杂度为 O(1)，而且看起来很牛逼。

这里说明一下，这个方式适合一个数出现了奇数次，其他数都出现了偶数次
2、m的n次方

如果让你求解 2 的 n 次方，并且不能使用系统自带的 pow 函数，你会怎么做呢？这还不简单，连续让 n 个 m 相乘就行了，代码如下：

pow(int n){

    int tmp = 1;
    for(int i = 1; i <= n; i++) {
        tmp = tmp * m;
    }
    return tmp;
}

不过你要是这样做的话，我只能呵呵，时间复杂度为 O(n) 了，怕是小学生都会！如果让你用位运算来做，你会怎么做呢？

我举个例子吧，例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:

m^1101 = m^0001 * m^0100 * m^1000。

我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。直接看代码吧，反而容易理解：

int pow(int n){
int sum = 1;
int tmp = m;
while(n != 0){
if(n & 1 == 1){
sum *= tmp;
}
tmp *= tmp;
n = n >> 1;
}

return sum;

}
时间复杂度近为 O(logn)，而且看起来很牛逼。

3、交换两个数

交换两个数相信很多人天天写过，我也相信你每次都会使用一个额外来变量来辅助交换，例如，我们要交换 x 与 y 值，传统代码如下：

int tmp = x;
x = y;
y = tmp;
这样写有问题吗？没问题，通俗易懂，万一哪天有人要为难你，不允许你使用额外的辅助变量来完成交换呢？你还别说，有人面试确实被问过，这个时候，位运算装逼大法就来了。代码如下：

x = x ^ y // （1）
y = x ^ y // （2）
x = x ^ y // （3）
我靠，牛逼！三个都是 x ^ y，就莫名交换成功了。在此我解释下吧，我们知道，两个相同的数异或之后结果会等于 0，即 n ^ n = 0。并且任何数与 0 异或等于它本身，即 n ^ 0 = n。所以，解释如下：

把（1）中的 x 带入 （2）中的 x，有

y = x^y = (x^y)^y = x^(y^y) = x^0 = x。 x 的值成功赋给了 y。

对于（3）,推导如下：

x = x^y = (x^y)^x = (x^x)^y = 0^y = y。

这里解释一下，异或运算支持运算的交换律和结合律哦。
怎么样？有木觉得很多牛逼？

我在我的公众号：苦逼的码农，该公众号主要专注于写算法、计算机基础以及Java相关文章，也总结了很多算法技巧，欢迎大家的关注。

说到算法技巧，必须再给大家再讲一波好用的算法技巧，不信，你继续往下看

1. 巧用数组下标

数组的下标是一个隐含的很有用的数组，特别是在统计一些数字，或者判断一些整型数是否出现过的时候。例如，给你一串字母，让你判断这些字母出现的次数时，我们就可以把这些字母作为下标，在遍历的时候，如果字母a遍历到，则arr[a]就可以加1了，即 arr[a]++;

通过这种巧用下标的方法，我们不需要逐个字母去判断。

我再举个例子：

问题：给你n个无序的int整型数组arr，并且这些整数的取值范围都在0-20之间，要你在 O(n) 的时间复杂度中把这 n 个数按照从小到大的顺序打印出来。

对于这道题，如果你是先把这 n 个数先排序，再打印，是不可能O(n)的时间打印出来的。但是数值范围在 0-20。我们就可以巧用数组下标了。把对应的数值作为数组下标，如果这个数出现过，则对应的数组加1。 代码如下：

public void f(int arr[]) {

int[] temp = new int[21];
for (int i = 0; i < arr.length; i++) {
    temp[arr[i]]++;
}
//顺序打印
for (int i = 0; i < 21; i++) {
    for (int j = 0; j < temp[i]; j++) {
        System.out.println(i);
    }
}

}
利用数组下标的应用还有很多，大家以后在遇到某些题的时候可以考虑是否可以巧用数组下标来优化。

2. 巧用取余

有时候我们在遍历数组的时候，会进行越界判断，如果下标差不多要越界了，我们就把它置为0重新遍历。特别是在一些环形的数组中，例如用数组实现的队列。往往会写出这样的代码：

(int i

    if (pos < N) {
     //没有越界
     // 使用数组arr[pos]
     else {
       pos = 0;//置为0再使用数组
       //使用arr[pos]
      }
     pos++;
}

实际上我们可以通过取余的方法来简化代码

(int i

  //使用数组arr[pos]   (我们假设刚开始的时候pos < N)
  pos = (pos + 1) % N;
}

3. 巧用双指针

对于双指针，在做关于单链表的题是特别有用，比如“判断单链表是否有环”、“如何一次遍历就找到链表中间位置节点”、“单链表中倒数第 k 个节点”等问题。对于这种问题，我们就可以使用双指针了，会方便很多。我顺便说下这三个问题怎么用双指针解决吧。

例如对于第一个问题

我们就可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点，而快指针一次移动两个节点，如果该链表没有环，则快指针会先遍历完这个表，如果有环，则快指针会在第二次遍历时和慢指针相遇。

对于第二个问题

一样是设置一个快指针和慢指针。慢的一次移动一个节点，而快的两个。在遍历链表的时候，当快指针遍历完成时，慢指针刚好达到中点。

对于第三个问题

设置两个指针，其中一个指针先移动k个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候，第二个指针正好处于倒数第k个节点。

你看，采用双指针方便多了吧。所以以后在处理与链表相关的一些问题的时候，可以考虑双指针哦。

4. 设置哨兵位

在链表的相关问题中，我们经常会设置一个头指针，而且这个头指针是不存任何有效数据的，只是为了操作方便，这个头指针我们就可以称之为哨兵位了。

例如我们要删除头第一个节点是时候，如果没有设置一个哨兵位，那么在操作上，它会与删除第二个节点的操作有所不同。但是我们设置了哨兵，那么删除第一个节点和删除第二个节点那么在操作上就一样了，不用做额外的判断。当然，插入节点的时候也一样。

有时候我们在操作数组的时候，也是可以设置一个哨兵的，把arr[0]作为哨兵。例如，要判断两个相邻的元素是否相等时，设置了哨兵就不怕越界等问题了，可以直接arr[i] == arr[i-1]?了。不用怕i = 0时出现越界。

当然我这只是举一个例子，具体的应用还有很多，例如插入排序，环形链表等。

5、找出不大于N的最大的2的幂指数

传统的做法就是让 1 不断着乘以 2，代码如下：

int findN(int N){
int sum = 1;
while(true){
if(sum * 2 > N){
return sum;
}
sum = sum * 2;
}
}
这样做的话，时间复杂度是 O(logn)，那如果改成位运算，该怎么做呢？如果要弄成位运算的方式，很多时候我们把某个数拆成二进制，然后看看有哪些发现。这里我举个例子吧。

例如 N = 19，那么转换成二进制就是 00010011（这里为了方便，我采用8位的二进制来表示）。那么我们要找的数就是，把二进制中最左边的 1 保留，后面的 1 全部变为 0。即我们的目标数是 00010000。那么如何获得这个数呢？相应解法如下：

1、找到最左边的 1，然后把它右边的所有 0 变成 1

2、把得到的数值加 1，可以得到 00100000即 00011111 + 1 = 00100000。

3、把 得到的 00100000 向右移动一位，即可得到 00010000，即 00100000 >> 1 = 00010000。

那么问题来了，第一步中把最左边 1 中后面的 0 转化为 1 该怎么弄呢？我先给出代码再解释吧。下面这段代码就可以把最左边 1 中后面的 0 全部转化为 1，

n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
就是通过把 n 右移并且做或运算即可得到。我解释下吧，我们假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后，那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算，那么得到的结果中第 k 和 第 k + 1 位必定是 1;同样的道理，再次把 n 右移两位，那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算，那么就能得到第 k, k+1, k+2, k+3 都是 1，如此往复下去….

最终的代码如下

int findN(int n){
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8 ;
n |= n >> 16;// 整型一般是 32 位，上面我是假设 8 位。
return (n + 1) >> 1;
}
这种做法的时间复杂度是 O(log(logn))，重点是，高逼格。

6、找出两个没有重复的数

对于第一题【找出没有重复的数】

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。
有人问如果有2个数出现了一次，其他数都出现了一次，那还能用位运算来找出这两个数吗？

答是必须的，假如这两个出现一次的 数 分别为 A, B，则所有 数 异或后的结果为 A^B，这时我们遇到的问题是无法确定 A，B的值。

由于 A 和 B 是不一样的值，所以 A^B 的结果不为 0，也就是说，这个异或值的二进制中某一位为1。显然，A 和 B 中有且仅有一个数的相同位上也为 1。

这个时候，我们可以把所有 数 分为两类，一类在这个位上为 1，另一类为 0，那么对于这两类，一类会含有 A，另一类会含有 B。于是，我们可以分别计算这两类 数 的异或值，即可得到 A 和 B 的值。

举个例子吧：
1、假如那两个没有重复的数分别是 a, b。那么把所有数的异或之后，最终所得到的值为 a^b。我们令 result = a^b.
2、由于 a 和 b 的值不相等，所以 a^b 的值不为0，所以 result 的二进制位中一定存在某一个位为1（例如result = 5的二进制表达为00…00101，则第一位和第三位都是1）。我们假设第k位为1.
3、显然，由于 result 的第 k 位为1，则a和b的第k位一定是一个为1，一个为0。假设a的第k位为0，b为1.
4、我们把数组的所有元素进行分类，分成A, B两类，让A类的元素第k位有0，B类元素的第k类为1。
5、那么a存在于A类中，b存在于B类中，那么这个就简单了，问题变成了和文章的第一题一样，从A类中找出一个出现一次的元素，B类中找出一个出现一次的元素了。

1. 判断一个正整数数 N 是否为 2 的幂次方。

如果一个数是 2 的幂次方，意味着 N 的二进制表示中，只有一个位 是1，其他都是0。我举个例子，例如

2^0 = 0…..0001

2^1 = 0…..0010

2^2 = 0….0100

2^3 = 0..01000

…..

所以呢，我们只需要判断N中的二进制表示法中是否只存在一个 1 就可以了。不过我们可以用上面第5题中的做法找出不大于N的最大的2的幂指数 M，然后判断找处理的那个数M是否和N相等。这种做法，比一个一个着去统计N的二进制位中是否只有一个1快多了。

所以呢，可以写出如下的代码

boolean judge(int n){
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;// 我这里假设是32位的正整数
return (n + 1) >> 1 == n
}
然后，还有更加牛逼的解法，代码如下：

boolean judege(int n){
return n & (n - 1) == 0;//
}
卧槽，这也太牛逼了吧，一行代码解决，一行代码解决。这里我解释一下， n & (n - 1) 这个运算，会把 n 的二进制位表示法中最左边的 1 变成 0。所以呢，经过这个运算之后，如果 n & ( n - 1) 的结果是 0,说明 n 中只有一个 1。牛逼啊！

ACM中常使用二进制数1n位的0/1状态来表示一个由1n组成的集合，也就是第k位为1则代表数k在集合中，于是为了提高效率就有了各种花式枚举集合的方法：

1) 要求集合中不能有两个相邻的元素

if ((mask >> 1) & mask) continue;

2) 在限定必须不取某些元素的前提下枚举子集

// mask的第x位为0表示x必须不在子集中(原集合中不含这个元素)：

for (int mask1 = mask; mask1 >= 0; mask1 = (mask1 - 1) & mask)

3) 在限定必须取某些元素的前提下枚举子集

// mask的第x位为1表示x必须在子集中：

for (int mask1 = mask; mask1 < (1 << m); mask1 = (mask1 + 1) | mask)

4) 找出二进制中恰好含有 k个1的所有数

for (int mask = 0; mask < 1 << n; ) {

int tmp = mask & -mask;

mask = (mask + tmp) | (((mask ^ (mask + tmp)) >> 2) / tmp);

}