Find the total number of bits needed to be flipped

Find the total number of bits needed to be flipped to convert a given integer to another.

For example,

Input:

x = 65 (which is 01000001 in binary)
y = 80 (which is 01010000 in binary)

Output: The total number of bits to be flipped is 2

Practice this problem

The idea is to take XOR of the given two integers. After calculating the XOR, the problem will reduce to counting set bits in the XOR output.

Following is the C++, Java, and Python implementation of the idea:

C++

#include <iostream>

#include <bitset>

using namespace std;

// Find the total number of bits needed to be flipped to convert `x` to `y`

int findBits(int x, int y)

{

// take XOR of `x` and `y` and store in `n`

int n = x ^ y;

// Using Brian Kernighan’s algorithm to count set bits

// `count` stores the total bits set in `n`

int count = 0;

while (n)

{

n = n & (n - 1); // clear the least significant bit set

count++;

}

return count;

}

int main()

{

int x = 65;

int y = 80;

cout << x << " in binary is " << bitset<8>(x) << endl;

cout << y << " in binary is " << bitset<8>(y) << endl;

cout << "\nThe total number of bits to be flipped is " << findBits(x, y);

return 0;

}

Download Run Code

Output:

65 in binary is 01000001
80 in binary is 01010000

The total number of bits to be flipped is 2

Java

class Main

{

// Find the total number of bits needed to be flipped to convert `x` to `y`

public static int findBits(int x, int y)

{

// take XOR of `x` and `y` and store in `n`

int n = x ^ y;

// Using Brian Kernighan’s algorithm to count set bits

// `count` stores the total bits set in `n`

int count = 0;

while (n != 0)

{

n = n & (n - 1); // clear the least significant bit set

count++;

}

return count;

}

public static void main(String[] args)

{

int x = 65;

int y = 80;

System.out.println(x + " in binary is " + Integer.toBinaryString(x));

System.out.println(y + " in binary is " + Integer.toBinaryString(y));

System.out.println("\nThe total number of bits to be flipped is " + findBits(x, y));

}

Download Run Code

Output:

65 in binary is 1000001
80 in binary is 1010000

The total number of bits to be flipped is 2

Python

# Find the total number of bits needed to be flipped to convert `x` to `y`

def findBits(x, y):

# take XOR of `x` and `y` and store in `n`

n = x ^ y

# Using Brian Kernighan’s algorithm to count set bits

# `count` stores the total bits set in `n`

count = 0

while n:

n = n & (n - 1) # clear the least significant bit set

count = count + 1

return count

if __name__ == '__main__':

x = 65

y = 80

print(f'{x} in binary is {bin(x)}')

print(f'{y} in binary is {bin(y)}')

print('\nThe total number of bits to be flipped is', findBits(x, y))

Download Run Code

Output:

65 in binary is 0b1000001
80 in binary is 0b1010000

The total number of bits to be flipped is 2