Minimum bitwise operations to convert given a into b.

0 0 7 minutes read

Given two positive integer a and b you have to change a to b by applying any of the three operations on binary form of a. You can select ai and aj (any two bits where i!=j) from binary form of a and then perform operation as:

AND operation as : temp = ai & aj, ai = temp & ai, aj = temp & aj
OR operation as : temp = ai | aj, ai = temp | ai, aj = temp | aj
XOR operation as : temp = ai ^ aj, ai = temp ^ ai, aj = temp ^ aj

where & = bitwise AND, | = bitwise OR and ^ = bitwise XOR.
Find the minimum operation required for conversion of a to b. Also, if conversion of a to b is not possible then print -1.
Examples:

Input : a = 12 (1100), b = 10 (1010)
Output : 1
Explanation : select a2 and a3 and perform XOR 

Input : a = 15 (1111), b = 10 (1010)
Output : -1
Explanation : Conversion from a to b is not possible

Explanation : First of all let’s understand the working of all three operation.

AND operation as : temp = ai & aj, ai = temp & ai, aj = temp & aj If any of ai or aj is 0 then it makes both as 0 otherwise no effect on ai and aj.
OR operation as : temp = ai | aj, ai = temp | ai, aj = temp | aj If any of ai or aj is 1 then it makes both as 1 otherwise no effect on ai and aj.
XOR operation as : temp = ai ^ aj, ai = temp ^ ai, aj = temp ^ aj Simply interchange value of ai and aj.

Some conclusion on basis of working of operations :

If all bits of a are 1 or 0 then we can not change value of a.
If a equals to b then no operation required.
Let n be number of indices i, where ai = 0 and bi = 1.
Let m be number of indices i, where ai = 1 and bi = 0.
Let us think about the n elements, where ai = 0 and bi = 1. We have to change all of these zeros into ones. Note that this will require at least n operations.
Similarly for all the m elements, where ai = 1 and bi = 0. We have to change all of these ones into zeros. Note that this will require at least m operations.
Let res = max(n, m). We can make the a and b equal in res operations as follows.
Let n >= m. Take m 1’s and n 0’s in A and apply the XOR operation to swap 0’s with 1’s. After that you will be left with total n-m zeros elements to change to one. That you can do by taking each of these zeros with some single one and applying the OR operation.
Let m >= n. Take m 1’s and n 0’s in A and apply the XOR operation to swap 0’s with 1’s. After that you will be left with total m-n ones elements to change to zero. That you can do by taking each of these ones with some single zero and applying the OR operation.

CPP

// Cpp program to find min operation to convert a to
 
#include <bits/stdc++.h>
 
using namespace std;
 
// function to return min operation
int minOp(bitset<32> a1, bitset<32> b1)
{
    // if a1 == b1 return 0
    if (a1 == b1)
        return 0;
    // if all bits of a = 0
    if (a1 == 0)
        return -1;
    // if all bits of a =1
    // first convert a1 to int and then call a1 & a1+1
    if (((int)a1.to_ulong() & ((int)a1.to_ulong() + 1))
        == 0)
        return -1;
    // convert a and b to binary string
    string a = a1.to_string();
    string b = b1.to_string();
    // check where ai and bi are different
    // and count n where ai = 1 and m where ai = 0
    int n = 0, m = 0;
    for (int i = 0; i < b.size(); i++) {
        if (b[i] != a[i]) {
            if (a[i] == '1')
                n++;
            else
                m++;
        }
    }
    // return result
    return max(n, m);
}
// driver program
int main()
{
    bitset<32> a = 14, b = 1;
    cout << minOp(a, b);
    return 0;
}

Java

// Java program to find min operation to convert a to
import java.util.*;
 
class GFG {
  static String leftPad(String input, int length,
                        String fill)
  {
    String pad = String.format("%" + length + "s", "")
      .replace(" ", fill)
      + input.trim();
    return pad.substring(pad.length() - length,
                         pad.length());
  }
  // Function to return min operation
  static int minOp(int a, int b)
  {
    String a1
      = leftPad((Integer.toBinaryString(a)), 32, "0");
    String b1
      = leftPad((Integer.toBinaryString(b)), 32, "0");
 
    // if a1 == b1 return 0
    if (a1 == b1)
      return 0;
    // if all bits of a = 0
    if (Integer.parseInt(a1, 2) == 0)
      return -1;
 
    // if all bits of a =1
    // first convert a1 to int and then call a1 &
    // a1+1
    if ((Integer.parseInt(a1, 2)
         & (Integer.parseInt(a1, 2) + 1))
        == 0)
      return -1;
 
    // convert a and b to binary string
 
    // check where ai and bi are different
    // and count n where ai = 1 and m where ai = 0
    int n = 0;
    int m = 0;
    for (int i = 0; i < b1.length(); i++) {
      if (b1.charAt(i) != a1.charAt(i)) {
        if (a1.charAt(i) == '1')
          n += 1;
        else
          m += 1;
      }
    }
 
    // return result
    return Math.max(n, m);
  }
 
  // Driver program
  public static void main(String[] args)
  {
    int a = 14;
    int b = 1;
    System.out.print(minOp(a, b));
  }
}
 
// This code is contributed by phasing17

Python3

#Python3 program to find min operation to convert a to 
 
# function to return min operation 
def minOp(a1, b1): 
    a1 = bin(a1)[2::].zfill(32)
    b1 = bin(b1)[2::].zfill(32)
    # if a1 == b1 return 0 
    if (a1 == b1): 
        return 0
    # if all bits of a = 0 
    if (int(a1) == 0): 
        return -1
    # if all bits of a =1 
    # first convert a1 to int and then call a1 & a1+1 
    if (int(a1) & (int(a1) + 1)) == 0:
        return -1
         
    # convert a and b to binary string 
 
  
    # check where ai and bi are different 
    # and count n where ai = 1 and m where ai = 0 
    n = 0
    m = 0
    for i in range(len(b1)):
        if b1[i] != a1[i]:
            if a1[i] == '1':
                n += 1
            else:
                m += 1
 
    # return result 
    return max(n, m)
 
# Driver program
a = 14
b = 1
print(minOp(a, b))
 
 
#This code is contributed by phasing17

C#

// C# program to find min operation to convert a to
using System;
 
class GFG {
 
  // Function to return min operation
  static int minOp(int a, int b)
  {
    string a1 = Convert.ToString(a, 2).PadLeft(32, '0');
    string b1 = Convert.ToString(b, 2).PadLeft(32, '0');
 
    // if a1 == b1 return 0
    if (a1 == b1)
      return 0;
    // if all bits of a = 0
    if (Convert.ToInt32(a1) == 0)
      return -1;
 
    // if all bits of a =1
    // first convert a1 to int and then call a1 & a1+1
    if ((Convert.ToInt32(a1)
         & (Convert.ToInt32(a1) + 1))
        == 0)
      return -1;
 
    // convert a and b to binary string
 
    // check where ai and bi are different
    // and count n where ai = 1 and m where ai = 0
    var n = 0;
    var m = 0;
    for (var i = 0; i < b1.Length; i++) {
      if (b1[i] != a1[i]) {
        if (a1[i] == '1')
          n += 1;
        else
          m += 1;
      }
    }
 
    // return result
    return Math.Max(n, m);
  }
 
  // Driver program
  public static void Main(String[] args)
  {
    int a = 14;
    int b = 1;
    Console.Write(minOp(a, b));
  }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript program to find min operation to convert a to 
 
// function to return min operation 
function minOp(a1, b1)
{
    a1 = a1.toString(2).padStart(32, '0');
    b1 = b1.toString(2).padStart(32, '0');
 
    // if a1 == b1 return 0 
    if (a1 == b1)
        return 0;
    // if all bits of a = 0 
    if (parseInt(a1) == 0)
        return -1;
     
    // if all bits of a =1 
    // first convert a1 to int and then call a1 & a1+1 
    if ((parseInt(a1) & (parseInt(a1) + 1)) == 0)
        return -1 ;
         
    // convert a and b to binary string 
 
    // check where ai and bi are different 
    // and count n where ai = 1 and m where ai = 0 
    let n = 0;
    let m = 0;
    for (var i = 0; i < b1.length; i++)
    {
        if (b1[i] != a1[i])
        {
            if (a1[i] == '1')
                n += 1;
            else
                m += 1;
        }
    }
 
    // return result 
    return Math.max(n, m);
}
 
// Driver program
let a = 14;
let b = 1;
console.log(minOp(a, b));
 
// This code is contributed by phasing17

Output:

Time Complexity – O(K)

Space Complexity – O(K)

Here, K is a constant.

This article is contributed by Shivam Pradhan (anuj_charm). If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!