Bitwise Operators

Bitwise Operators : NOT, AND and XOR

Intuition

Now let's discuss O(1)O(1) space solution by using three bitwise operators

∼xthat meansbitwise NOT∼xthat meansbitwise NOT

x&ythat meansbitwise ANDx&ythat meansbitwise AND

x⊕ythat meansbitwise XORx⊕ythat meansbitwise XOR

XOR

Let's start from XOR operator which could be used to detect the bit which appears odd number of times: 1, 3, 5, etc.

XOR of zero and a bit results in that bit

0⊕x=x0⊕x=x

XOR of two equal bits (even if they are zeros) results in a zero

x⊕x=0x⊕x=0

and so on and so forth, i.e. one could see the bit in a bitmask only if it appears odd number of times.

That's already great, so one could detect the bit which appears once, and the bit which appears three times. The problem is to distinguish between these two situations.

AND and NOT

To separate number that appears once from a number that appears three times let's use two bitmasks instead of one: seen_once and seen_twice.

The idea is to

• change seen_once only if seen_twice is unchanged

• change seen_twice only if seen_once is unchanged

This way bitmask seen_once will keep only the number which appears once and not the numbers which appear three times.