摘要：使用位运算数组只出现一次数字的数组得到最低的有效位，即两个数不同的那一位看完上面的解法，我脑海中只有问号的存在，啥意思啊下面就让我们简单了解一下位运算并解析一下这三道题目。另，负数按补码形式参加按位与运算。
你可做过这几道题？
在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目：
# 136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
我不禁眉头一皱，心说，这还不简单，三下五除二写下如下代码：
/**
* HashMap
*
* @param nums 数组
* @return 结果
*/
public int solution(int[] nums) {
Map map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.remove(num);
} else {
map.put(num, 1);
}
}
return map.entrySet().iterator().next().getKey();
}
接着，我看到了另外一道题目：
# 137. 只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
我不禁眉头又一皱，心说，好像是同样的套路，便写下了如下代码：
/**
* 使用Map，存储key以及出现次数
*
* @param nums 数组
* @return 出现一次的数字
*/
public int singleNumber(int[] nums) {
Map map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
for (Integer key : map.keySet()) {
if (map.get(key) == 1) {
return key;
}
}
return 0;
}
然后，就出现了终极题目：
# 260. 只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意：
1. 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
我不禁又皱了一下眉头，心说，嗯……接着便写下如下代码：
/**
* 使用Map，存储key以及出现次数
*
* @param nums 数组
* @return 出现一次的数字的数组
*/
public int[] singleNumber(int[] nums) {
int[] result = new int[2];
Map map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
int i = 0;
for (Integer key : map.keySet()) {
if (map.get(key) == 1) {
result[i] = key;
i++;
}
}
return result;
}
用几乎同一种思路做了三道题，不得不夸一下自己：
做完这三道题目，提交了答案之后，执行用时和内存消耗都只超过了 10% 的解题者。不由得眉头紧锁（终于知道自己为啥抬头纹这么深了），发现事情并没有这么简单……
之后我又找了一下其他解法，如下：
/**
* #136 根据题目描述，由于加上了时间复杂度必须是 O(n) ，并且空间复杂度为 O(1) 的条件，因此不能用排序方法，也不能使用 map 数据结构。答案是使用 位操作Bit Operation 来解此题。
* 将所有元素做异或运算，即a[1] ⊕ a[2] ⊕ a[3] ⊕ …⊕ a[n]，所得的结果就是那个只出现一次的数字，时间复杂度为O(n)。
* 根据异或的性质 任何一个数字异或它自己都等于 0
*
* @param nums 数组
* @return 结果
*/
private int solution(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
/**
* #137 嗯……这个我们下面再做详解
* 这里使用了异或、与、取反这些运算
*
* @param nums 数组
* @return 出现一次的数字
*/
public int singleNumber2(int[] nums) {
int a = 0, b = 0;
int mask;
for (int num : nums) {
b ^= a & num;
a ^= num;
mask = ~(a & b);
a &= mask;
b &= mask;
}
return a;
}
/**
* #260 在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。
* 然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0 ，另一个为 1 ，现在需要找到这一位。
* 根据异或的性质 任何一个数字异或它自己都等于 0 ，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。
* 再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。
* 1. 将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个
* 2. 将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。
* 这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。
*
* 使用位运算
*
* @param nums 数组
* @return 只出现一次数字的数组
*/
public int[] singleNumber2(int[] nums) {
int diff = 0;
for (int num : nums) {
diff ^= num;
}
// 得到最低的有效位，即两个数不同的那一位
diff &= -diff;
int[] result = new int[2];
for (int num : nums) {
if ((num & diff) == 0) {
result[0] ^= num;
} else {
result[1] ^= num;
}
}
return result;
}
看完上面的解法，我脑海中只有问号的存在，啥意思啊？！
下面就让我们简单了解一下位运算并解析一下这三道题目。
简单介绍一下位运算
异或逻辑的关系是：当AB不同时，输出P=1；当AB相同时，输出P=0。“⊕”是异或数学运算符号，异或逻辑也是与或非逻辑的组合，其逻辑表达式为：P=A⊕B。在计算机语言中，异或的符号为“ ^ ”。
异或运算 A ⊕ B 的真值表如下：
| A | B | ⊕ |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
所以我们从 #136 题解中了解，通过异或运算，两个相同的元素结果为 0，而 任何数 与 0 进行异或操作，结果都为其本身。
“与”运算是计算机中一种基本的逻辑运算方式，符号表示为 “&”，参加运算的两个数据，按二进制位进行“与”运算。运算规则：0&0=0；0&1=0；1&0=0；1&1=1；即：两位同时为“1”，结果才为“1”，否则为0。另，负数按补码形式参加按位与运算。
与运算 A & B 的真值表如下：
| A | B | & |
|---|---|---|
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
“与运算”的特殊用途：
清零。如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。
取一个数的指定位
方法：找一个数，对应X要取的位，该数的对应位为1，其余位为零，此数与X进行“与运算”可以得到X中的指定位。例：设 X=10101110，取X的低4位，用 X & 0000 1111 = 0000 1110 即可得到；还可用来取 X 的2、4、6位。
参加运算的两个对象，按二进制位进行“或”运算。运算规则：0|0=0； 0|1=1； 1|0=1； 1|1=1；即 ：参加运算的两个对象只要有一个为1，其值为1。另，负数按补码形式参加按位或运算。
或运算 A | B 的真值表如下：
| A | B | | |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
或运算”特殊作用：
常用来对一个数据的某些位置1。
方法：找到一个数，对应X要置1的位，该数的对应位为1，其余位为零。此数与X相或可使X中的某些位置1。
例：将 X=10100000 的低4位 置为1 ，用 X | 0000 1111 = 1010 1111 即可得到。
参加运算的一个数据，按二进制位进行“取反”运算。运算规则：~1=0； ~0=1；即：对一个二进制数按位取反，即将0变1，1变0。
使一个数的最低位为零，可以表示为：a&~1。~1 的值为 1111111111111110，再按“与”运算，最低位一定为0。因为“~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。
OK，截止到这儿，三道题目中使用的位运算介绍完毕，那么这里我们插入一下 #137 的详细题解。
public int singleNumber2(int[] nums) {
// 这里我们改一下变量名
// 用 one 记录到当前处理的元素为止，二进制1出现“1次”（mod 3 之后的 1）的有哪些二进制位；
// 用 two 记录到当前计算的变量为止，二进制1出现“2次”（mod 3 之后的 2）的有哪些二进制位。
int one = 0, two = 0;
int mask;
for (int num : nums) {
// 由于 two 要考虑，one 的已有状态，和当前是否继续出现。所以要先算
two ^= one & num;
// one 就是一个0,1的二值位，在两个状态间转换
one ^= num;
// 当 one 和 two 中的某一位同时为1时表示该二进制位上1出现了3次，此时需要清零。
mask = ~(one & two);
// 清零操作
one &= mask;
two &= mask;
}
// 即用 二进制 模拟 三进制 运算。最终 one 记录的是最终结果。
return one;
}
首先考虑一个相对简单的问题，加入输入数组里面只有 0 和 1，我们要统计 1 出现的次数，当遇到 1 就次数加 1，遇到 0 就不变，当次数达到 k 时，统计次数又回归到 0。我们可以用 m 位来做这个计数工作，即 xm, xm−1, …, x1，只需要确保 2m > k 即可，接下来我们要考虑的问题就是，在每一次check元素的时候，做什么操作可以满足上述的条件。在开始计数之前，每一个计数位都初始化位0，然后遍历nums，直到遇到第一个1，此时 x1 会变成1，继续遍历，直到遇到第二个1，此时 x1=0, x2=1，直到这里应该可以看出规律了。每遇到一个1，对于 xm, xm−1, …, x1，只有之前的所有位都为1的时候才需要改变自己的值，如果本来是1，就变成0，本来是0，就变成1 ，如果遇到的是0，就保持不变。搞清楚了这个逻辑，写出表达式就不难了。这里以 m = 3 为例给出 java 代码：
for(int num: nums) {
x3 ^= x2 & x1 & i;
x2 ^= x1 & i;
x1 ^= i;
// other operations
}
但是到这里还没有解决当 1 的次数到 k 时，计数值要重新返回到 0，也就是所有计数位都变成 0 这个问题。解决办法也是比较巧妙。
假设我们有一个标志变量，只有当计数值到 k 的时候这个标志变量才为 0，其余情况下都是 1，然后每一次check元素的时候都对每个计数位和标志变量做与操作，那么如果标志变量为 0，也就是计数值为 k 的时候，所有位都会变成 0， 反之，所有位都会保持不变，那么我们的目的也就达到了。
好，最后一个问题是怎么计算标志变量的值。将 k 转变为二进制，只有计数值达到 k，所有计数位才会和 k 的二进制一样，所以只需要将 k 的二进制位做 与操作 ，如果某个位为 0，就与该位 取反 之后的值做与操作。
以 k=3, m=2 为例，简要的 java 代码如下：
// where yj = xj if kj = 1,
// and yj = ~xj if kj = 0,
// k1, k2是 k 的二进制表示(j = 1 to 2).
mask = ~(y1 & y2);
x2 &= mask;
x1 &= mask;
将这两部分合起来就是解决这个问题的完整算法了。
将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。
例：a = a<< 2将a的二进制位左移2位，右补0，左移1位后a = a *2;
若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。
代码示例，本代码中的整数为32位整数，所以为负数的话，二进制表示其长度为32：
/**
* << 表示左移，如果该数为正，则低位补0，若为负数，则低位补1。如：5<<2的意思为5的二进制位往左挪两位，右边补0，5的二进制位是0000 0101 ， 就是把有效值101往左挪两位就是0001 0100
*/
@Test
public void leftShiftTest() {
int number1 = 5;
System.out.println("左移前的十进制数为：" + number1);
System.out.println("左移前的二进制数为：" + Integer.toBinaryString(number1));
int number2 = number1 << 2;
System.out.println("左移后的十进制数为：" + number2);
System.out.println("左移后的二进制数为：" + Integer.toBinaryString(number2));
System.out.println();
int number3 = -5;
System.out.println("左移前的十进制数为：" + number3);
System.out.println("左移前的二进制数为：" + Integer.toBinaryString(number3));
int number4 = number3 << 2;
System.out.println("左移后的十进制数为：" + number4);
System.out.println("左移后的二进制数为：" + Integer.toBinaryString(number4));
}
结果如下：
左移前的十进制数为：5
左移前的二进制数为：101
左移后的十进制数为：20
左移后的二进制数为：10100
左移前的十进制数为：-5
左移前的二进制数为：11111111111111111111111111111011
左移后的十进制数为：-20
左移后的二进制数为：11111111111111111111111111101100
>> 表示右移，表示将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。操作数每右移一位，相当于该数除以2。
>>> 表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0。
例如：a = a >> 2 将a的二进制位右移2位，左补0 or 补1得看被移数是正还是负。
代码示例，本代码中的整数为32位整数，所以为负数的话，二进制表示其长度为32：
@Test
public void rightShift() {
int number1 = 10;
System.out.println("右移前的十进制数为：" + number1);
System.out.println("右移前的二进制数为：" + Integer.toBinaryString(number1));
int number2 = number1 >> 2;
System.out.println("右移后的十进制数为：" + number2);
System.out.println("右移后的二进制数为：" + Integer.toBinaryString(number2));
System.out.println();
int number3 = -10;
System.out.println("右移前的十进制数为：" + number3);
System.out.println("右移前的二进制数为：" + Integer.toBinaryString(number3));
int number4 = number3 >> 2;
System.out.println("右移后的十进制数为：" + number4);
System.out.println("右移后的二进制数为：" + Integer.toBinaryString(number4));
System.out.println("***********************逻辑右移**********************");
int a = 15;
System.out.println("逻辑右移前的十进制数为：" + a);
System.out.println("逻辑右移前的二进制数为：" + Integer.toBinaryString(a));
int b = a >>> 2;
System.out.println("逻辑右移后的十进制数为：" + b);
System.out.println("逻辑右移后的二进制数为：" + Integer.toBinaryString(b));
System.out.println();
int c = -15;
System.out.println("逻辑右移前的十进制数为：" + c);
System.out.println("逻辑右移前的二进制数为：" + Integer.toBinaryString(c));
int d = c >>> 2;
System.out.println("逻辑右移后的十进制数为：" + d);
System.out.println("逻辑右移后的二进制数为：" + Integer.toBinaryString(d));
}
结果如下：
右移前的十进制数为：10
右移前的二进制数为：1010
右移后的十进制数为：2
右移后的二进制数为：10
右移前的十进制数为：-10
右移前的二进制数为：11111111111111111111111111110110
右移后的十进制数为：-3
右移后的二进制数为：11111111111111111111111111111101
***********************逻辑右移**********************
逻辑右移前的十进制数为：15
逻辑右移前的二进制数为：1111
逻辑右移后的十进制数为：3
逻辑右移后的二进制数为：11
逻辑右移前的十进制数为：-15
逻辑右移前的二进制数为：11111111111111111111111111110001
逻辑右移后的十进制数为：1073741820
逻辑右移后的二进制数为：111111111111111111111111111100
总结
以上就是我们常见的几种位运算了，其中左移、右移等操作，在 HashMap的源码中也会经常看到，理解了这些位操作，对于理解源码也是有一定帮助的，当然也会帮助我们写出执行效率更高的代码。
从上面的部分示例中可以看出，位运算通常用来降低包含排列，计数等复杂度比较高的操作，当然也可以用来代替乘 2 除 2，判断素数，偶数，倍数等基本操作，但是我认为其意义在于前者，即用计数器来降低设计到排列或者计数的问题的复杂度。
最后一点，三道算法题中，#136 、#260 理解起来倒还好，#137 Single Number II 的题解可能需要费一点功夫，至少我还没有完全理解，但不能轻易放弃对不对，继续啃啊！
以上便是我个人的简单总结，如果有纰漏或者错误，欢迎进行指出及纠正。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/6636.html
摘要：简单介绍一下位运算异或运算异或逻辑的关系是当不同时，输出当相同时，输出。另，负数按补码形式参加按位与运算。使一个数的最低位为零，可以表示为。，截止到这儿，三道题目中使用的位运算介绍完毕，那么这里我们插入一下的详细题解。你可做过这几道题？ 在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字 给定一个非空整数数组，除了某个元素只...
摘要：题目二答案会报错未定义这段代码中混合了函数声明和函数表达式的形式，而函数实际上是绑定到了上而不是。除此之外函数声明与函数表达式的语法其实是等价的。因此，在外层函数函数体内的两个函数声明，都会提升到之前执行。 这是我在Javascript微信公众号上看到的一篇文章，觉得挺有意思的，所以转载过来跟大家分享一下，同时，对这些题目也加上了一些我个人的理解，如果有不对的地方，请大家指正。 题目...
摘要：如果不存在公共前缀，返回空字符串。示例输入输出示例输入输出解释输入不存在公共前缀。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住...
摘要：先实现栈操作遍历链表，把每个节点都进中然后再遍历链表，同时节点依次出栈，二者进行比较。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无...
阅读 1082·2021-10-14 09:43
阅读 1107·2021-10-11 11:07
阅读 3099·2021-08-18 10:23
阅读 1461·2019-08-29 16:18
阅读 984·2019-08-28 18:21
阅读 1454·2019-08-26 12:12
阅读 3731·2019-08-26 10:11
阅读 2482·2019-08-23 18:04
