目录

zrlong 的个人博客

希望大家都能保护好自己身上的特质,无论是五年还是十年,永远善良,不服输,热爱你所热爱。在漫长岁月的变迁里,是这些让你永远迷人,富有生命力。

X

妙妙妙的分组位运算

写在前面的位运算知识点

与运算

按位与运算符(&)

参加运算的两个数,按二进制位进行“与”运算。

运算规则:只有两个数的二进制同时为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};
    }
}

标题:妙妙妙的分组位运算
作者:zrlong
地址:http://blog.zrlong.top/articles/2022/04/12/1649732849916.html