Count Number of Bits to Flip to Convert A to B

Given two integers a and b, your task is to determine how many bits need to be flipped in a to convert it into b. Each flip changes a bit from 0 to 1 or from 1 to 0.

The goal is to count the number of differing bits between their binary representations.

Understanding the Problem

We are given two integers a and b. Our task is to find out how many bits are different between their binary representations. In other words, we need to count how many bits we need to flip in a so that it becomes equal to b.

Each bit can be either 0 or 1. A bit flip means changing a 0 to a 1, or a 1 to a 0. This problem is a great exercise in using bitwise operations, especially XOR, to compare bits.

Step-by-Step Solution with Example

Step 1: Understand XOR (Exclusive OR)

XOR is a bitwise operation that compares each corresponding bit of two numbers. It returns 1 if the bits are different and 0 if they are the same.

For example:

a = 10  -> binary: 1010
b = 20  -> binary: 10100

To make bit lengths equal:
a = 01010
b = 10100

XOR:
    01010
  ^ 10100
  --------
    11110

The result is 11110 in binary, which is 30 in decimal. This result has 4 bits set to 1, which means we need to flip 4 bits in a to get b.

Step 2: Initialize a counter

We’ll use a counter variable, initially set to 0, to keep track of how many 1’s are in the XOR result.

Step 3: Loop through each bit of the XOR result

We check the last bit of the XOR result using xor & 1. If it’s 1, we increment the counter. Then we right shift the number using xor >>= 1 to move to the next bit. We continue until the XOR result becomes 0.

Step 4: Return the counter

The counter now holds the number of differing bits between a and b.

Edge Cases

• When a and b are equal: XOR result will be 0. Hence, 0 bits need to be flipped.
• When either a or b is 0: The number of flips is equal to the number of 1's in the other number's binary representation.
• Very large numbers: The algorithm still works efficiently as it only processes the number of bits set in the XOR result.

Final Thoughts

This problem is a classic use of the XOR operation to compare bit patterns. It helps build intuition around binary representation and how bitwise operations work. It’s also efficient, as it doesn’t need to convert numbers to strings or use arrays — everything is done using bitwise math.

Understanding how binary numbers differ and using simple looping allows us to solve this problem in a clean and optimized way, which is essential for both interviews and real-world programming.

1. Compute the XOR of a and b. This highlights all bit positions where the bits differ.
2. Initialize a counter to 0.
3. Loop while the XOR result is greater than 0:
• Increment the counter if the least significant bit (LSB) is 1 (i.e., xor & 1).
• Right shift the XOR result by 1 to move to the next bit.
4. Return the counter as the final answer.

#include <stdio.h>

int countBitsToFlip(int a, int b) {
    int xor = a ^ b;
    int count = 0;
    while (xor) {
        count += (xor & 1);
        xor >>= 1;
    }
    return count;
}

int main() {
    int a = 29;  // Example value
    int b = 15;  // Example value
    printf("Number of bits to flip from %d to %d is: %d\n", a, b, countBitsToFlip(a, b));
    return 0;
}

#include <iostream>
using namespace std;

int countBitsToFlip(int a, int b) {
    int xorVal = a ^ b;
    int count = 0;
    while (xorVal) {
        count += (xorVal & 1);
        xorVal >>= 1;
    }
    return count;
}

int main() {
    int a = 29;  // Example value
    int b = 15;  // Example value
    cout << "Number of bits to flip from " << a << " to " << b << " is: " << countBitsToFlip(a, b) << endl;
    return 0;
}

def count_bits_to_flip(a: int, b: int) -> int:
    xor = a ^ b
    count = 0
    while xor:
        count += xor & 1
        xor >>= 1
    return count

# Example usage
if __name__ == "__main__":
    a = 29  # Example value
    b = 15  # Example value
    print(f"Number of bits to flip from {a} to {b} is: {count_bits_to_flip(a, b)}")

public class BitFlipCounter {
    public static int countBitsToFlip(int a, int b) {
        int xor = a ^ b;
        int count = 0;
        while (xor != 0) {
            count += (xor & 1);
            xor >>= 1;
        }
        return count;
    }

    public static void main(String[] args) {
        int a = 29;  // Example value
        int b = 15;  // Example value
        System.out.println("Number of bits to flip from " + a + " to " + b + " is: " + countBitsToFlip(a, b));
    }
}

function countBitsToFlip(a, b) {
  let xor = a ^ b;
  let count = 0;
  while (xor !== 0) {
    count += xor & 1;
    xor >>>= 1; // unsigned right shift
  }
  return count;
}

// Example usage
const a = 29;  // Example value
const b = 15;  // Example value
console.log(`Number of bits to flip from ${a} to ${b} is: ${countBitsToFlip(a, b)}`);

package main

import "fmt"

func countBitsToFlip(a, b int) int {
    xor := a ^ b
    count := 0
    for xor != 0 {
        count += xor & 1
        xor >>= 1
    }
    return count
}

func main() {
    a := 29 // Example value
    b := 15 // Example value
    fmt.Printf("Number of bits to flip from %d to %d is: %d\n", a, b, countBitsToFlip(a, b))
}

fn count_bits_to_flip(a: u32, b: u32) -> u32 {
    let mut xor = a ^ b;
    let mut count = 0;
    while xor != 0 {
        count += xor & 1;
        xor >>= 1;
    }
    count
}

fn main() {
    let a = 29; // Example value
    let b = 15; // Example value
    println!("Number of bits to flip from {} to {} is: {}", a, b, count_bits_to_flip(a, b));
}

fun countBitsToFlip(a: Int, b: Int): Int {
    var xor = a xor b
    var count = 0
    while (xor != 0) {
        count += xor and 1
        xor = xor ushr 1
    }
    return count
}

fun main() {
    val a = 29 // Example value
    val b = 15 // Example value
    println("Number of bits to flip from $a to $b is: ${countBitsToFlip(a, b)}")
}

func countBitsToFlip(_ a: Int, _ b: Int) -> Int {
    var xor = a ^ b
    var count = 0
    while xor != 0 {
        count += xor & 1
        xor >>= 1
    }
    return count
}

let a = 29 // Example value
let b = 15 // Example value
print("Number of bits to flip from \(a) to \(b) is: \(countBitsToFlip(a, b))")

function countBitsToFlip(a: number, b: number): number {
  let xor = a ^ b;
  let count = 0;
  while (xor !== 0) {
    count += xor & 1;
    xor >>>= 1; // unsigned right shift
  }
  return count;
}

// Example usage
const a = 29; // Example value
const b = 15; // Example value
console.log(`Number of bits to flip from ${a} to ${b} is: ${countBitsToFlip(a, b)}`);

Time complexity

Space complexity

O(1)

Only a constant amount of extra space is used: a counter and the XOR value. No additional space is required proportional to the input size.