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

The problem, simply

You get two whole numbers, A and B. Write both in bits. A flip changes one bit, from 0 to 1 or from 1 to 0.

How many flips does it take to turn A into B? That is the number of places where their bits do not match.

A story to remember it

Picture it

Examples

Way 1: the simple way

Compare the two numbers one bit at a time, from the right.

1. Look at the last bit of each: A & 1 and B & 1.
2. If they differ, add 1 to the count.
3. Slide both numbers one place right with >>> and repeat until both are 0.

class Solution {
    public static int countFlips(int a, int b) {
        int count = 0;
        while (a != 0 || b != 0) {
            if ((a & 1) != (b & 1)) {
                count++;               // this pair of bits does not match
            }
            a >>>= 1;                  // >>> pulls in 0s, so negatives finish too
            b >>>= 1;
        }
        return count;
    }
}

How long it takes: one round per bit of the bigger number, O(log max(A, B)), at most 32 rounds. Extra room: O(1).

Way 2: the clever way

Two tricks, one after the other.

1. XOR finds the differences. A ^ B has a 1 exactly where A and B disagree. So the answer is the number of 1s in A ^ B.
2. To count 1s fast, use x & (x - 1). Taking 1 away from x turns its lowest 1 into a 0 and the 0s under it into 1s. ANDing with x wipes out that lowest 1 and nothing else.
3. Repeat until x is 0. The number of rounds is the number of 1s.

class Solution {
    public static int countFlips(int a, int b) {
        int x = a ^ b;                 // 1 wherever a and b disagree
        int count = 0;
        while (x != 0) {               // != 0, not > 0, so negatives work
            x &= x - 1;                // wipe out the lowest 1
            count++;
        }
        return count;
    }
}

How long it takes: one round per differing bit. If k bits differ, that is O(k) rounds, never more than 32. Extra room: O(1).

Watch out for

• Comparing the numbers in decimal digits. Flips are about bits, so 10 and 20 need 4 flips, not 1.
• Java has Integer.bitCount(a ^ b) built in. Mention it, but be ready to write the loop yourself.
• Equal numbers give A ^ B = 0, so the loop never runs and the answer is 0.

What interviewers ask next

• What is this number called? The Hamming distance between A and B.
• Sum of Hamming distances over every pair in an array? Do it per bit: if c numbers have bit i on and n - c have it off, that bit adds c * (n - c). Total O(32 n), not O(n^2).
• Why does x & (x - 1) drop the lowest 1? Everything above the lowest 1 is the same in x and x - 1. The lowest 1 and everything below it are opposite, so AND gives 0 there.
• Can you count 1s in constant steps? Yes, with a 256 entry table looked up once per byte, or with the add-in-pairs trick that Integer.bitCount uses.

Remember this

Grown-up words: the see-through sheet is XOR, the glowing spots are set bits, the count is the Hamming distance, and the sticker trick is Brian Kernighan's way of counting set bits.