Recently I came across a question from Interview Cake and it could be solved gracefully by bitwise operator XOR which arouse my interest. I will show you the question and the answer at the end of the post. Now let's learn some basic knowledge of bitwise operators.
When you saw symbols like &, |, ^, ~, >> or << they represent bitwise operators.
They operate on numbers (normally), but instead of treating that number as if it were a single value, they treat it as if it were a string of bits, written in twos-complement binary.
But wait! What's two's complement binary?
Two's complement binary
A two's complement binary is same as the classical binary representation for positve integers but is slightly different for negative numbers. Negative numbers are represented by performing the two's complement operation on their absolute value.
Negative numbers are written with a leading one instead of a leading zero. So if you are using only 8 bits for your twos-complement numbers, then you treat patterns from "00000000" to "01111111" as the whole numbers from 0 to 127, and reserve "1xxxxxxx" for writing negative numbers.
Let's assume there are totally 8 bits and there is a positive number 118. How can we get two's complement binary of -118?
- Make the positive number minus one:
118 - 1 // 117 - Convert the result to its binary format using JavaScript:
117..toString(2) // 01110101 - Perform complement (switched from 1 to 0 or 0 to 1, actually it's a Bitwise NOT operation):
01110101 => 10001010
On the contrary if we got a two's complement binary 10001010 how can we calculate its positive number?
- Perform complement (Bitwise NOT):
10001010 => 01110101 - Plus one:
01110101 + 1 = 01110110 - Convert to decimal using JavaScript:
parseInt('01110110', 2) // output 118
A question about two's complement
In two's complement positive and negative depend on the leading bit. It seems we must have limited bits otherwise we don't know which bit is the leftmost symbol bit. Some languages use this solution like JavaScript. In JavaScript only 32 bits will be preserved to guarantee bitwise operations.
It turns out that there is another sulution and it's totally oppsite direction. In Python there is no limit number of bits but an INFINITE number of bits. So -5 will be implemented as ...11111111111111011. To be honest I favor this one.
The operators
With two's complement in head the operators are quite easy.
Logical operators
Let's see three of the operators first: & (Bitwise AND), | (Bitwise OR) and ^ (Bitwise XOR).
| a | b | a & b | a | b | a ^ b |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
And the operator ~ (Bitwise NOT):
| a | ~ a |
|---|---|
| 0 | 1 |
| 1 | 0 |
Shift operators
<< and >> are the two symbols used to shift bits on a two's complement binary.
- a << b means shift a's bits to the left by b places. New bits on the right will be 0.
- a >> b means shift a's bits to the right by b places. New bits on the left will be the same as original leftmost bit.
Some formulas
a & 0 = 0
a & -1 = -1
a | 0 = a
a | -1 = -1
a ^ 0 = a
a ^ -1 = ~a
-a = ~(a - 1) = ~a + 1 => ~a = -(a + 1)
a << b = a * 2 ** b
a >> b = a / 2 ** b
The question
There is an array composed of number pair except one which is isolate. Number pair means two numbers with same value. The question is how can you find the isolate number in a most efficient way. You should consider both time complexity and space complexity.
With Bitwise XOR we can solve this problem gracefully.
const a = [23, 34, 53, 64, 64, 34, 53];
let isolate = 0;
for (let i = 0; i < a.length; i++) {
isolate ^= a[i];
}
Time complexity is O(n) and thanks to Bitwise XOR space complexity is just O(1).