妙妙妙的分组位运算
写在前面的位运算知识点
与运算
按位与运算符(&)
参加运算的两个数,按二进制位进行“与”运算。
运算规则:只有两个数的二进制同时为1,结果才为1,否则为0。(负数按补码形式参加按位与运算)
即 0 & 0= 0 ,0 & 1= 0,1 & 0= 0, 1 & 1= 1。
例:3 &5 即 00000011 & 00000101 = 00000001 ,所以 3 & 5的值为1。
或运算
按位或运算符(|)
参加运算的两个数,按二进制位进行“或”运算。
运算规则:参加运算的两个数只要两个数中的一个为1,结果就为1。
即 0 | 0= 0 , 1 | 0= 1 , 0 | 1= 1 , 1 | 1= 1 。
例:2 | 4 即 00000010 | 00000100 = 00000110 ,所以2 | 4的值为 6 。
异或运算
异或运算符(^)
参加运算的两个数,按二进制位进行“异或”运算。
运算规则:参加运算的两个数,如果两个相应位为“异”(值不同),则该位结果为1,否则为0。
即 0 ^ 0=0 , 0 ^ 1= 1 , 1 ^ 0= 1 , 1 ^ 1= 0 。
例: 2 ^ 4 即 00000010 ^ 00000100 =00000110 ,所以 2 ^ 4 的值为6 。
大家都做过这种题吧,在数组每个数都出现两次,但是有一个数出现了一次,让我们去找到这个数。当然我们可以遍历数组计数。但是更简单的是异或运算,我们只需从头到尾遍历数组,全部做异或运算,最后的结果就是我们要找的数。
题目
剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣(LeetCode) (leetcode-cn.com)
今天做到了另一道题,还是跟上述的题目差不多,但是数组中有两个出现了一次的数,我们怎么找到呢?而且题目要求时间复杂度是O(n),空间复杂度是O(1)。因此我们不能再简单的使用遍历计数,那我们就应该想到位运算。那么问题来了,位运算到最后结果是两个数相异或的结果,我们怎么把他们拆开呢?
4 ^ 1 ^ 4 ^ 6 => 1 ^ 6
6 对应的二进制: 110
1 对应的二进制: 001
1 ^ 6 二进制: 111
思路
我们无法把111拆分为110和001,我们可以把数组分成两组进行异或,每组的结果就是答案。
- 对重复的数我们进行分组是很简单的,指定一个分组规则就可以把相同的数分为一组。因为数字是重复的,必然会分到一组。
- 难点在于如何将两个不同的数分到不同的组中。异或的特点就是不同为1,在数组异或一遍之后结果就是我们要找的两个数的异或结果,那么这个数中至少存在一位上为1。那么我们就可以根据这个数1上的任意一位1来进行分组。这个操作是什么呢?就是&1。数组中&1结果为0的分为一组,不为0的是另一组,分别异或,我们就能得到结果了。为了方便,我们直接选取最低为的1即可。
代码
class Solution {
public int[] singleNumbers(int[] nums) {
//用于将所有的数异或起来
int k = 0;
for(int num: nums) {
k ^= num;
}
//获得k中最低位的1
int mask = 1;
//mask = k & (-k) 这种方法也可以得到mask,具体原因百度 哈哈哈哈哈
while((k & mask) == 0) {
mask <<= 1;
}
int a = 0;
int b = 0;
for(int num: nums) {
if((num & mask) == 0) {
a ^= num;
} else {
b ^= num;
}
}
return new int[]{a, b};
}
}