Count number of bits to be flipped to convert A to B

Problem Statement

Given two integers A and B, find the number of bits that need to be flipped to convert A to B.

Example:

Noob-Friendly Explanation

Think of two rows of colored blocks — one row for number A and one for number B. Each block is either RED (1) or BLUE (0).

A "flip" means changing a RED block to BLUE or a BLUE block to RED. We need to count how many blocks are different between the two rows.

Here's the trick: if we XOR the two numbers, we get a number where each 1-bit represents a position where A and B differ. So the answer is just: count the number of 1s in A XOR B.

Approach 1: Brute Force (Compare Bit by Bit)

Intuition

XOR A and B to find positions where they differ. Then check each bit of the XOR result one by one using right shift.

Algorithm

1. Compute xor = A ^ B
2. While xor > 0, check last bit
3. If last bit is 1, increment count
4. Right shift xor

class Solution {
    public static int countFlips(int a, int b) {
        int xor = a ^ b;
        int count = 0;

        while (xor > 0) {
            // Check if last bit is 1 (a difference)
            if ((xor & 1) == 1) {
                count++;
            }
            xor = xor >> 1;
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println(countFlips(10, 20)); // 4
        System.out.println(countFlips(7, 10));  // 3
        System.out.println(countFlips(5, 5));   // 0
    }
}

Complexity Analysis

• Time Complexity: O(log(max(A,B))) — We check every bit of the XOR result
• Space Complexity: O(1) — Only using a few variables

Approach 2: Optimal (Brian Kernighan's Algorithm)

Intuition

After XORing A and B, instead of checking every bit, use n & (n-1) to directly jump to each set bit. This way we only loop as many times as there are differing bits.

Algorithm

1. Compute xor = A ^ B
2. While xor > 0:
   • xor = xor & (xor - 1) — removes the lowest set bit
   • Increment count
3. Return count

class Solution {
    public static int countFlips(int a, int b) {
        int xor = a ^ b;
        int count = 0;

        while (xor > 0) {
            xor = xor & (xor - 1); // remove lowest set bit
            count++;
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println(countFlips(10, 20)); // 4
        System.out.println(countFlips(7, 10));  // 3
        System.out.println(countFlips(5, 5));   // 0
        System.out.println(countFlips(0, 15));  // 4 (0000 → 1111)
    }
}

Complexity Analysis

• Time Complexity: O(K) — Where K is the number of bits that differ between A and B
• Space Complexity: O(1) — Only using a few variables

Key Takeaways

1. XOR finds differences: A ^ B gives 1 at every position where A and B differ
2. Count set bits of XOR = answer: The number of flips equals the number of set bits in A ^ B
3. Brian Kernighan's trick: n & (n-1) removes the lowest set bit, making counting more efficient
4. Same numbers → 0 flips: If A == B, their XOR is 0, so count is 0