Browse Categories  Minimum X (xor) A Malay Gain
Oct 27, 2021

Introduction

The ‘Minimum X (xor) A’ problem is one of the popular problems that can be solved using the concept of Bit Manipulation. Bit manipulation is one of the important topics for technical interviews.

Problem Statement

Given two integers A and B, we need to find an integer X such that (X XOR A) is minimum possible and the count of set bits in X is equal to the count of set bits in B.

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.

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).

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.

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

Happy learning! 