前置知识

本节最重要的一个算法 Brain Kernighan算法
大致内容如下 :
如何提取出来一个数的最右侧的1
n = n & (~n + 1)
因为 (~n + 1) == -n
所以该算法也可以写成
n = n & (-n)

1. 交换两个数

因为我们的异或运算遵循的交换律和结合律, 所以我们可以写出下面的这一段代码

public void swap(int[] arr, int i, int j) {//注意这里的 i != jarr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}

请注意这里面的 i != j 因为如果相等的话, 会直接把这一块区域置为0

2. 比较两个数的大小

尝试不用任何的比较操作就比较出来两个数的大小关系, 我们写出来的代码如下

/*** 不包含比较相关的逻辑运算符来得到两个数当中的最大值*///flip意为反转 --> 此时传入的n保证为 1 / 0 --> 如果是1, 就转化为0 , 如果是0, 就转化为1private int flip(int n) {return n ^ 1;}//获取一下某个数字的符号,如果是非负的数字就返回一个1, 如果是负数就返回0private int sign(int n) {return flip(n >>> 31);}//下面我们给出两种判断的方法 --> 第一种有可能会溢出, 第二种不会溢出//核心的逻辑就是设置 returnA , returnB 来规定什么时候返回a, 什么时候返回b(两个return一定是互斥的才可以)public int getMax1(int a, int b) {//c可能会溢出int c = a - b;int returnA = sign(c);int returnB = flip(returnA);return a * returnA + b * returnB;}

解释一下我们的代码 :
sign方法是为了获取到某一个数的符号, 如果是非负数就返回1, 如果是负数就返回0, flip方法是为了把翻转数字,保证传入的数字一定是0或1, 其实这段代码的本质逻辑就是定义了两个returnA和returnB变量, 这两个变量一定是互斥的(一个1,一个0), 在必要的条件下就返回值
举例:
比如 a == 5, b == 3, c == 2, returnA为获取一下c的符号是非负也就是1, 那么returnB就是相反的0, 所以最后return的结果就是returnA * a == a
思考 : 上述代码是不是有问题呢?
其实, 当我们的c是有可能发生溢出的, 比如a = Integer.MAX_VALUE;
b = Integer.MIN_VALUE, 显然我们的c是溢出的, 所以我们的代码是有问题的, 我们的改动如下(flip和sign方法是不变的)

//下面的这个方法是不会溢出的public int getMax2(int a, int b) {//c依然可能会溢出int c = a - b;//下面判断一下a b c的符号int signA = sign(a);int signB = sign(b);int signC = sign(c);//判断a b 符号是不是相同的int diffAB = signA ^ signB; //不同返回1int sameAB = flip(diffAB); //相同返回1//什么时候进行a的返回 //--> 1. ab不同号且a为非负//--> 2. ab同号(此时不可能会溢出)且signC == 1int returnA = diffAB * signA + sameAB * signC;int returnB = flip(returnA);return a * returnA + b * returnB;}

上述的代码逻辑和之前的那个其实是一致的
就是加入了一些是否越界的判断(到底什么时候returnA)

3. leetcode268 寻找缺失的数字

前置知识
假设一堆数字异或的结果我们记为异或和 : ans
这一堆数字的部分数字的结果我们记作 : eor1
另一部分记作 : eor2
显然有 eor1 ^ eor2 = ans
两边同时 ^ eor1
可以得到 eor2 = ans ^ eor1
有了上面的结论的铺垫, 写这个题应该是十分的容易, 代码实现如下

class Solution {public int missingNumber(int[] nums) {//说白了这个题就是异或运算的性质int eor = 0;for(int elem : nums){eor ^= elem;}int eorN = 0;for(int i = 0; i <= nums.length; ++i){eorN ^= i;}return eorN ^eor;}
}

4. leetcode136 只出现一次的数字

这个问题可以抽象为下面的这个问题
给你一个数组, 其中一种数字出现了奇数次, 另外的数字都出现了偶数次
比较简单好想的思路是创建一个Set集合对元素进行去重操作(略)
这里我们用异或运算来写
思考 : 由于异或运算满足交换律, 不管多少个偶数个相同数字异或的结果一定是0
所以只要异或一轮就是那个结果, 代码实现如下

class Solution {public int singleNumber(int[] nums) {int eor = 0;for(int element : nums){eor = eor ^ element;}return eor;}
}

5. leetcode260 只出现一次的数字|||

该问题与上面的问题类似, 我们把该问题抽象出来就是, 给了一组数字, 其中有两个元素出现了奇数次, 其他的所有元素出现了偶数次, 求出来两个元素
思路分析 :
先把所有的元素异或起来得到一个异或和 eor , 该异或和的结果就是那两个数字(我们简介为m,n)
也就是 m ^ n == eor , 然后通过Brain Kernighan算法, 得到了最右侧的1, 因为我们的异或运算也可以等同于无进位相加, 所以这个1必定来源于m和n的其中一个, 所以我们定义一个eorN,让这个eorN只异或该位为1的数字, 得到的eorN就是m/n的其中一个,问题得解

class Solution {public int[] singleNumber(int[] nums) {int eor = 0;for(int elem : nums){eor ^= elem;}int n = eor & (~eor + 1);int eorN = 0;for(int elem : nums){if((elem & n) == 0){eorN ^= elem;}}return new int[]{eorN, eor ^ eorN};}
}

6. leetcode137 只出现一次的数字||

把该问题抽象出来, 就是一组数字, 其中一个数字出现次数小于m次, 其他的所有数字都出现了m次, 求出来这个数字是多少
思路分析 :
我们通过分位操作, 同意每一位上出现的1的个数, 遍历这个数组, 如果是hash[i] % m != 0, 就证明该数字这一位是1, 问题得解
代码实现如下

class Solution {public int singleNumber(int[] nums) {//首先进行的是统计每一个数位上的1的个数int[] hash = new int[32];for(int elem : nums){for(int i = 0; i < 32; ++i){hash[i] = hash[i] + ((elem >>> i) & 1);}}//统计1的分位个数完毕, 开始还原数字int ans = 0;for(int i = 0; i < 32; ++i){if(hash[i] % 3 != 0){ans = ans | (1 << i);}}return ans;}
}

7. 2/3的幂

给一个数判断是不是2的幂, 这个没什么可说的, 直接用Brain Kernighan算法

class Solution {/*** 判断一个数字是不是2的幂* @param n* @return*/public boolean isPowerOfTwo(int n){return n > 0 && (n & (~n + 1)) == n;}/*** 判断一个数字是不是3的幂(直接找到int范围内3的最大的幂是多少* @param n* @return*/public boolean isPowerOfThree(int n){return n > 0 && 1162261467 % n == 0;}}

8. 大于等于该数字的最小2的幂

已知n是非负数, 请返回大于等于n的最小的2的幂
思路分析 :
假如数字的二进制序列是 : …0010100110 , 那么此时大于等于该数的最小的2的幂就是最左侧1的一个位置
假如数字的二进制序列是 : …0001000000 , 那么此时大于等于该数的最小的2的幂就是该数本身
假设有一种方案可以把 最左侧的1后面的所有二进制位都刷成1 , 那么+1以后的结果就是答案
为什么要先进行 n-- , 是为了满足n正好是2的幂的情况
下面的几行代码的作用就是将最左侧的1的右面的二进制位全部刷成1
代码实现如下

class Solution{public int nearTwoPower(int n){if(n <= 1){return 1;}n--;n = n | (n >>> 1);n = n | (n >>> 2);n = n | (n >>> 4);n = n | (n >>> 8);n = n | (n >>> 16);return n + 1;}
}

9. leetcode201 数字范围按位与

暴力算法肯定是不可取的, 所以我们要采取更加好的算法
指定区间按位与(肯定是不能暴力解法)
思考 : 假设我们的left == right, 那么我们最终的与的结果就是left / right
如果 left != right, 那么此时我让right减小一点, 也就是(right - 1) & left
那么从 m ~ right的所有数字与起来的结果是不变的都是m, 因为前缀不变, 后缀全是0
循环下去, 直到 left >= right (中间的过程用的是Brain Kernighan算法)
代码实现如下

class Solution{public int rangeBitswiseAnd(int left,int right){while (left < right) {right = right - (right & (~right + 1));}return right;}
}

10. 位运算中分治法举例

我们给出来两道题, 第一道题就是逆序二进制数位, 第二道题就是汉明距离(统计二进制中的1的个数) , leetcode的题号 190 . 461
这个自己慢慢悟吧, 下面给出来代码实现(让我自己懂的)

class Solution{/*** 翻转二进制的状态* 比如一个数的二进制位是 : 0001101101010010 --reverse--> 010010101011000* 分析 : 正常的解法就是定义一个ans, 看到哪一位上有i你就或上去一个1就行了, 这里我们不在多说, 有点简单*       我们重点说一下位运算分治的思路(从两个一组翻转 --> 四个一组 --> 八个一组.....)*       假如有一个序列  a b c d e f g h*       我们翻转的过程: 1. b a d c f e h g (1v1翻转)*                    2. d c b a h g f e (2v2翻转)*                    3. h g f e d c b a (4v4翻转)*       下面推广到代码上 :*                   1. a b c d e f g h & 0 1 0 1 0 1 0 1  ==> 0 b 0 d 0 f 0 h (1)*                      a b c d e f g h & 1 0 1 0 1 0 1 0 ==>  a 0 c 0 e 0 g 0 (2)*                      (1) << 1 | (2) >>> 1  ==> b a d c f e h g*       下面的过程以此类推* @param n* @return*/public int reverseBits(int n){n = ((n & 0x55555555) << 1) | ((n & 0xaaaaaaaa) >>> 1);n = ((n & 0x33333333) << 2) | ((n & 0xcccccccc) >>> 2);n = ((n & 0x0f0f0f0f) << 4) | ((n & 0xf0f0f0f0) >>> 4);n = ((n & 0x00ff00ff) << 8) | ((n & 0xff00ff00) >>> 8);n = ((n & 0x0000ffff) << 16) | ((n & 0xffff0000) >>> 16);return n;}/*** 计算一个数字的二进制位中有几个1* 还是用的位运算分治的方法*   思路分析 : 假如数字的二进制位是  1 0 1 1 0 1 0 1** @param n* @return*/public int cntOnes(int n){n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);return n;}
}