Bitwise XOR

A bitwise XOR is a binary operation. The result in each position is 1 if only one of the bits is 1, and 0 if both are 0 or 1.

var a = 0b100;
var b = 0b101;
var c = a ^ b;
/**
 * 100
 * 101 =
 * 001
 * */
console.log(c.toString(2));  // "001"

A few related feature should be noted when using bitwise oxr:

a^0 = a
a^a = 0
x^y = y^x (Commutativity)
(x^y)^z = x^(y^z) (Associativity)

Single Number

Let's use xor to solve the leetcode single number problem.

Say we have an array [1,1,2,2,3], we need to find the unique number.

Do an xor operation for all numbers to see how it goes.

1 ^ 1 ^ 2 ^ 2 ^ 3 =>
(1^1) ^ (2^2) ^ 3 =>
0 ^ 0 ^ 3 =>
3

As you can see, it's so simple to solve this problem by bitwise xor, no need a map to store number's count.

Let's code the process.

function singleNumber(nums: number[]): number {
    let res = 0;
    for (const num of nums) {
        res ^= num;
    }
    return res;
};

To make it more concise, use reduce function.

function singleNumber(nums: number[]): number {
    return nums.reduce((pre, num) => pre ^ num, 0);
};

Now the problem becomes to find two unique numbers. We already know how to use xor to find one uniqe number, but how to find two unique numbers? We need to find a way to break the problem of finding two unqiue numbers into two problems, each for finding one unique number.

Let's walk through the process by using an example. Say we have a nums array [1,1,2,2,3,4]. We can see the answer should be [3,4].

First xor all numbers in the array 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 5. Clearly, because equal numbers should cancel each other, so the result should be 3 ^ 5. Let's see them in binary form to see if we can find some patterns.

3   => 011
4   => 101
xor => 110

As you can see, the xor result is 110. Take any bit with value 1, say the left first bit. According to xor's feather, we know that is one bit of xor's result is 1, them two values should have different value for that same bit. So this means that we can use this to break these two unique numbers into two groups. After break them into two groups, we can just follow the same algorithm of finding one unique in each group.

function singleNumber(nums: number[]): number[] {
    // xor for all numbers
    const xy = nums.reduce((pre, num) => pre ^ num, 0);

    // find right most bit with value 1
    let rightMostBitSet = 1;
    while((xy & rightMostBitSet) === 0) {
        rightMostBitSet <<= 1;
    }

    let n1 = 0; // group1
    let n2 = 0; // group2
    for (const num of nums) {
        // test bit value to break two unique numbers into two group
        if ((num & rightMostBitSet) !== 0) {
            n1 ^= num;
        } else {
            n2 ^= num;
        }
    }
    return [n1, n2]
};

Now you may ask, Yes, we have break the two unique number, but how about other numbers? How to ensure them to be assigned equally in two groups? Well, the answer is we do not. We do not need to ensure other numbers to be assigned equally. Because each other number should have two same ones, the same ones will be assigned into the same group, so they will cancel each other. So even if all other number get to be assigned into one group, we get the same result.

yaox023's blog

yaox023's blog

Bitwise XOR

Bitwise XOR

Single Number

Single Number III