Minimum X (xor) A

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
#include <bits/stdc++.h>
using namespace std;

// function to return the value of X such that (X xor A) is minimum
// and the number of set bits in X is equal to the number
// of set bits in B
int minXOR(int A, int B) {

  int setBits = 0, ans = 0;


setBits = __builtin_popcount(B); // number of set bits in B

  // creating the binary representation of A in stack s
  stack<short int> s;
  while(A>0)
{
s.push(A%2);
A=A/2;
}


  // decrease the count of setBits as in the required number set bits has to be
  // equal to the count of set bits in B
  // Creating the nearest possible number in X in binary form.
  // Using vector as the number in binary for can be large.
  vector<short int> X;

  // handling case 1
  while(!s.empty())
{
  if(s.top()==1 && setBits>0)
{
X.push_back(1);
setBits--;
}
  else
{
X.push_back(0);
}
s.pop();
}

  // handling case 2
  //Filling the unset bits from the least significant bit to the

        //most significant bit
  //if the setBits are not equal to zero
  for(int i=X.size()-1;i>=0 && setBits>0;i--)
{
  if(X[i]==0)
{
X[i]=1;
setBits--;
}
}


  int mask;
  for(int i=X.size()-1;i>=0;i--)
{
mask=1<<(X.size()-i-1);

ans+=X[i]*mask;
}
  int n=X.size();


  // handling case 3

  //if the number of setBits is still not equal to zero
  //adding the remaining number of set bits to the left of the

        //most significant bit
  //to make set bits of X equal to the set bits of B.

  while(setBits>0)
{
ans+=1<<n;
n++;
setBits--;
}

  return ans;
}

// Driver code
int main()
{
  int A = 5, B = 7;

cout <<"value of X = "<<minXOR(A, B);

  return 0;
}

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!