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

## Code

// C++ implementation of the above algorithm //most significant bit //most significant bit |

Output:

value of X = 7 |

## 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

- 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!