Application of XOR. (extract the rightmost 1 in the number, which is often used in interviews)

We all know , In computer system , All numbers are stored in binary , Then we need to extract the rightmost of the numbers 1 What to do ？

One 、 background

The application of XOR is very important . For example, when we interview , The interviewer asked a question ： In a bunch of numbers , Only two numbers appear an odd number of times , Other numbers appear an even number of times , Ask for odd numbers a and b, Time complexity required O（N）, Extra space complexity O（1）.

Two 、 Their thinking

First , We need an XOR array , The result is a^b, And then what ？
then a^b Definitely not for 0 Of , We need to know a perhaps b The result can be calculated by the value of , So how do you know a perhaps b Well ？
a and b In the form of computer storage, it is stored in binary form , Again because a It must not be equal to b, So we know a and b One of them is definitely different . Take advantage of this feature , Suppose we find a different bit on the far right （ That is to say a The digit of is 0, and b The digit of is 1, Or vice versa ）, How do we find the rightmost 1 Well ？

right_one = arr & (~arr + 1)  #  Extract the rightmost 1

This line of code is a good way to find the rightmost 1, Let me explain , First arr The value is a^b Result , So let's reverse the result , Then add 1, At this time arr Rightmost of 1 That's the answer. .
such as arr The result is 000111001100. After taking the reverse, it is 111000110011, add 1 For after 111000110100, Then the rightmost 1 Is the final answer .
After finding it , We can use this to iterate through the array again , The result is a perhaps b, Then let the result XOR arr, So you get two numbers .

3、 ... and 、 Complete code

nums = [10, 10, 10, 5, 6, 6, 7, 7, 8, 8, 9, 9, 55, 55, 66, 66, 33, 33, 5, 888, 888, 888]
arr = 0
for i in range(len(nums)):
    arr ^= nums[i]   #  At this time arr by a^b

right_one = arr & (~arr + 1)  #  Extract the rightmost 1
eor = 0
for i in range(len(nums)):
    if nums[i] & right_one == 0:
        eor ^= nums[i]
print(f' The two numbers are {
      eor} and {
      arr^eor}')

Output ：

 The two numbers are 888 and 10