Bitwise XOR

[xiedaxia1hao]

XOR

XOR是一个逻辑操作符，当两个bit是相同的时候，会返回0，当两个bit不同的时候，会返回1。

XOR的一些重要性质：

1. 一个数XOR自己返回0, e.g.,
   • 1 ^ 1 = 0
   • 29 ^ 29 = 0
2. 0和任何的数XOR都等于该数本身，e.g.,
   • 1 ^ 0 = 1
   • 31 ^ 0 = 31
3. XOR的运算是associative和commutative的，e.g.,
   • (a ^ b) ^ c = a ^ (b ^ c)
   • a ^ b = b ^ c

我们可以根据XOR的这些性质，帮助我们解决很多道题目。

WHY XOR?

268. Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

对于这道题来说，在我们之前的专题里可以知道，我们可以尝试用cyclic sort来解。如果题目没有限制条件，我们可以用一个hashset来解。

但是最直接的方法，可能是把所有0-n的数都加起来，然后减掉the given array，这样我们就得到了那个被遗漏的数字。但是这种做法可能会在n很大的时候造成overflow，得不到我们想要的答案。

所以我们可以尝试用xor来解这道题，同时可以避免overflow，写法上也比cyclic sort更简单。

class Solution {
    public int missingNumber(int[] nums) {
        int allNumXOR = 0;
        for(int i = 0; i <= nums.length; i++) {
            allNumXOR ^= i;
        }

        for(int num : nums) {
            allNumXOR ^= num;
        }

        return allNumXOR; // i.e., the missing number
    }
}

[xiedaxia1hao]

136. Single Number

In a non-empty array of integers, every number appears twice except for one, find that single number.

这道题可以说是xor的模版题了。题目说该array中只有一个数字是出现一次的，其他数字均出现了两次。我们可以尝试把array中所有的数字都给xor起来。根据xor的性质，所有出现两次的数字和自己xor了之后，都会变成0，那剩下的只出现一次的数字就会是我们想要的结果，直接return就好。

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

[xiedaxia1hao]

260. Single Number III

In a non-empty array of numbers, every number appears exactly twice except two numbers that appear only once. Find the two numbers that appear only once.

这道题和上面的那题不同是，这道题出现了2个只出现1次的数字，那我们应该如何用xor的性质把它俩找出来呢？

我们用这个array来举个例子：[1, 4, 2, 1, 3, 5, 6, 2, 3, 5]

我们把所有数字都给xor了之后，出现2次的数字都会被xor成0，剩下我们得到的是4 xor 6的值。

• 4的二进制是：0100
• 6的二进制是：0110

因为这两个数肯定是不一样的数字，那他们xor了之后，结果肯定不是0，换句话说，num1和num2肯定至少有一个bit是不同的。我们可以利用这个性质把原先数组中的数字分成两类：

我们把右数第二位的bit当作我们的区分bit，所有数字中右数第二位数字为1的，我们分到一组，所有数字中右数第二位数字为0的，我们分到另一组。然后对他们各组内的数字再全部进行xor，最后得到的两个数字就是我们的答案。

通过我们上面的思路，我们把右数第二位的bit当作区分bit后，我们可以把该array的数字分成以下两组：

• [1, 4, 1, 5, 5]
• [2, 3, 6, 2, 3]

对各自组里的数字全部进行xor了之后，我们就得到了我们要的num1和num2，也就是[4, 6]。

class Solution {
    public int[] singleNumber(int[] nums) {
        int n1XORn2 = 0;
        for(int num : nums) {
            n1XORn2 ^= num;            
        }

        int rightmostBitOne = 1;
        while((rightmostBitOne & n1XORn2) == 0) {
            rightmostBitOne = rightmostBitOne << 1;
        }

        int num1 = 0, num2 = 0;
        for(int num : nums) {
            if((num & rightmostBitOne) == 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }

        return new int[] {num1, num2};
    }
}

---

137. Single Number II

这题还有一种follow up，就是如果所有的数字都出现3次，只有一个数字出现了1次，我们该怎么把这个数字给找到呢？

这道题直接用xor不太方便，但是我们可以思考一下，如果每个数字都出现了3次，那我们把每个位的bit加起来，最后%3，都会变成0，但是那个多出来的数字，%3后每个bit并不会改变，这样我们就可以找出来我们缺失的那个数字了。

https://leetcode.com/problems/single-number-ii/discuss/43297/Java-O(n)-easy-to-understand-solution-easily-extended-to-any-times-of-occurance/42226

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < 32; i++) {
            int sum = 0;
            for(int num : nums) {
                if((num >> i & 1) == 1) {
                    sum++;
                }
            }
            sum %= 3;
            res |= sum << i;
        }

        return res;
    }
}

[xiedaxia1hao]

476. Number Complement & 1009. Complement of Base 10 Integer

Given a positive integer num, output its complement number. The complement strategy is to flip the bits of its binary representation.

这道题的做法和之前的一样，也可以用xor来做。

我们可以观察一下，5的二进制是101，它的complement就是010，这两个complement的xor一下就是111，也就是5这个数的所有bit位都为1的数字。

我们可以知道，如果我们知道了一个数的表示位数，并把它所有bit都设为1，和该数xor一下，就能得到该数的complement。

所以这题来说，我们先求num一共的位数，然后把所有位数置为1的数给算出来，即2^bitCount-1。 然后把2^bitCount-1和num这两个数相互xor一下，就得到了num的complement。代码如下：

class Solution {
    public int findComplement(int num) {
        if(num == 0) {
            return 1;
        }

        int bitCount = 0;
        int n = num;

        while(n > 0) {
            bitCount++;
            n = n >> 1;
        }

        int allBitsSet = (int)(Math.pow(2, bitCount)-1);
        return allBitsSet ^ num;
    }
}

[xiedaxia1hao]

832. Flipping an Image

Given a binary matrix representing an image, we want to flip the image horizontally, then invert it.
To flip an image horizontally means that each row of the image is reversed. For example, flipping [0, 1, 1] horizontally results in [1, 1, 0].
To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [1, 1, 0] results in [0, 0, 1].

这道题我们要做的就是2步，先flip，再invert。

• Flip: 我们仅需要把每一行的i-th数和该行的(col-i-1)-th的数交换即可。
• Invert: 把该image上的数的0和1相互交换位置，即把该数和1xor一下即可。

class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int row = image.length;
        int col = image[0].length;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j <= (col-1)/2; j++) {
                int temp = image[i][j] ^ 1;
                image[i][j] = image[i][col-j-1] ^ 1;
                image[i][col-j-1] = temp;
            }
        }

        return image;
    }
}