Tags: #<Tag:0x00007f181c6060e0>

#1

Can anyone explain the bitmask solution more clearly? Preferably with an example.

#2

The code works in similar line with the question of â€śfinding the element which appears once in an array - containing other elements each appearing twiceâ€ť. Solution is to XOR all the elements and you get the answer.

Basically, it makes use of the fact that x^x = 0. So all paired elements get XORâ€™d and vanish leaving the lonely element.
Since XOR operation is associative, commutativeâ€¦ it does not matter in what fashion elements appear in array, we still get the answer.

Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want.
To rectify this mistake, the code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared â€śonlyâ€ť once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared â€śonlyâ€ť twice.

So if at any point time,

1. A new number appears - It gets XORâ€™d to the variable â€śonesâ€ť.
2. A number gets repeated(appears twice) - It is removed from â€śonesâ€ť and XORâ€™d to the
variable â€śtwiceâ€ť.
3. A number appears for the third time - It gets removed from both â€śonesâ€ť and â€śtwiceâ€ť.

The final answer we want is the value present in â€śonesâ€ť - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes

All it does is, common 1â€™s between â€śonesâ€ť and â€śtwosâ€ť are converted to zero.

## For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order). Explanation for step 1

Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - â€śonesâ€ť and â€śtwosâ€ť has not recorded â€śxâ€ť.

Observe the statement â€śtwos| = ones & xâ€ť.
Since bit representation of â€śxâ€ť is not present in â€śonesâ€ť, AND condition yields nothing. So â€śtwosâ€ť does not get bit representation of â€śxâ€ť.
But, in next step â€śones ^= xâ€ť - â€śonesâ€ť ends up adding bits of â€śxâ€ť. Thus new element gets recorded in â€śonesâ€ť but not in â€śtwosâ€ť.

The last 3 lines of code as explained already, converts common 1â€™s b/w â€śonesâ€ť and â€śtwosâ€ť to zeros.
Since as of now, only â€śonesâ€ť has â€śxâ€ť and not â€śtwosâ€ť - last 3 lines does nothing.

## Explanation for step 2.

Lets say an element(x) appears twice.
CURRENT SITUATION - â€śonesâ€ť has recorded â€śxâ€ť but not â€śtwosâ€ť.

Now due to the statement, â€śtwos| = ones & xâ€ť - â€śtwosâ€ť ends up getting bits of x.
But due to the statement, â€śones ^ = xâ€ť - â€śonesâ€ť removes â€śxâ€ť from its binary representation.

## Again, last 3 lines of code does nothing. So ultimately, â€śtwosâ€ť ends up getting bits of â€śxâ€ť and â€śonesâ€ť ends up losing bits of â€śxâ€ť. Explanation for step 3.

Lets say an element(x) appears for the third time.
CURRENT SITUATION - â€śonesâ€ť does not have bit representation of â€śxâ€ť but â€śtwosâ€ť has.

Though â€śones & xâ€ť does not yield nothing â€¦ â€śtwosâ€ť by itself has bit representation of â€śxâ€ť. So after this statement, â€śtwoâ€ť has bit representation of â€śxâ€ť.
Due to â€śones^=xâ€ť, after this step, â€śoneâ€ť also ends up getting bit representation of â€śxâ€ť.

## Now last 3 lines of code removes common 1â€™s of â€śonesâ€ť and â€śtwosâ€ť - which is the bit representation of â€śxâ€ť. Thus both â€śonesâ€ť and â€śtwosâ€ť ends up losing bit representation of â€śxâ€ť. 1st example

2, 2, 2, 4

After first iteration,
ones = 2, twos = 0
After second iteration,
ones = 0, twos = 2
After third iteration,
ones = 0, twos = 0
After fourth iteration,
ones = 4, twos = 0

## 2nd example

4, 2, 2, 2

After first iteration,
ones = 4, twos = 0
After second iteration,
ones = 6, twos = 0
After third iteration,
ones = 4, twos = 2
After fourth iteration,
ones = 4, twos = 0

Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer.

#3

rajneesh-kumar - a wonderful explanation, thank you! I wonder if this approach could be extrapolated to a diverse number of repeated items in the row? Iâ€™m thinking something of:

``````for i = n-1 to 1
M[i] |= M[i-1] & x

M[0] ^= x

for i = 1 to n-1
NotM[i] = ~(M[0] & M[i])

for i = 1 to n-1
M[0] &= NotM[i]
M[i] &= NotM[i]
``````

But I havenâ€™t analyzed this approach yet.

#4

Insane! By far one of the best tutorials Iâ€™ve ever read!
Kudos!

#5

Thanks for explaining this! Much appreciated! @rajneesh-kumar

#6

Thanks man! It is indeed a very good explanation.