Minimum X (xor) A

Example

Input: A=5, B=7

Output: X=7

(5)2 = 101   

(7)2 = 111 

xor will be minimum when X=7, i.e. (7 xor 5)=2

Method

We need to find the minimum xor of two numbers. The minimum possible value of xor is 0, and it is achieved when two numbers are equal. So X can be equal to A, but in that case, A should have the same number of set bits as B. So, we should try to generate X’s binary representation as close to A as possible.

We will start traversing from the most significant bit in A to the least significant bit, and if a bit is set(i.e., 1) at the current position, then this bit also needs to be set bit in the required number X in order to minimize the value of XOR, but the number of bits set has to be equal to the number of set bits in B and to satisfy this condition, we need to handle three cases. 

Case 1

when the count of set bits in the required number X has reached the count of set bits in B, then the rest bits of X will be 0. 

Case 2

It is also  possible that the count of set bits in B is more than the number of set bits in A. In that case, start filling the unset bits of X to set bits from the least significant bit of X to the most significant bit of X.

Case 3

 If the number of set bits is still not equal to B, add the remaining number of set bits to the left of the most significant bit of X to make set bits of X equal to the set bits of B.

Code

Output:

Complexity analysis

Time complexity: Here, every loop runs at most bits in the binary representation of A or B, i.e., log(N) times. So, it is O(logN).

Space complexity: A stack and a vector are used whose size is nothing but the number of bits in the binary representation of A or X. So, Space complexity is also O(logN).

Also see, Euclid GCD Algorithm

FAQs

1. What is the xor of the same numbers?

As (1 xor 1)=0 ,(0 xor 0)=0; xor of the same numbers is 0.

2. How to swap two numbers using xor?

Let two numbers a and b.

a=a xor b 

b=a xor b // a xor b xor b = a….value of a stored in b

a=a xor b // a xor b xor a=b ….value of b stored in a

3. What are the bitwise operators?

There are 6 types of bitwise operators. These are

AND(&), OR(|), NOT(~), XOR(^), Left Shift(<<), Right Shift(>>)

Key Takeaways

This article covered the method of finding minimum X (xor) A using the concept of bit manipulation.

Side by side, we should also learn about applications of other bitwise operators.

Check out this problem - XOR Queries On Tree

Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning!