Number of Bit Changes to Make Two Integers Equal

Number of Bit Changes to Make Two Integers Equal

What is this problem about?

The Number of Bit Changes to Make Two Integers Equal problem asks: given two integers n and k, find the minimum number of bit changes (flipping a bit from 1 to 0 or 0 to 1) needed to make n equal to k. If it's impossible (because k has a 1 where n has a 0 — you can't set bits, only clear them in some variants), return -1. This easy coding problem tests XOR and bit counting.

Why is this asked in interviews?

ThoughtWorks asks this to test basic bit manipulation — specifically XOR to find differing bits and popcount to count them. The bit manipulation interview pattern is demonstrated cleanly here, and the edge case where transformation is impossible adds practical reasoning.

Algorithmic pattern used

XOR + popcount with feasibility check. diff = n XOR k. If any bit position has n=0 and k=1 (k has a 1 where n has a 0), transformation is impossible — check (n | k) != n (i.e., k has bits not in n). Otherwise, the number of changes = number of set bits in diff = bin(n ^ k).count('1').

Example explanation

n=13 (1101), k=4 (0100). n | k = 1101 | 0100 = 1101 = 13 = n. So feasible. n XOR k = 1101 XOR 0100 = 1001 = 9. Bits in 9: 2. Changes = 2 (flip bit 0 from 1 to 0, flip bit 3 from 1 to 0).

n=4 (0100), k=13 (1101): n | k = 1101 ≠ 0100 = n. k has bits not in n → -1 (impossible).

Common mistakes candidates make

• Not checking feasibility (returning a bit count even when transformation is impossible).
• Using n XOR k without verifying (n | k) == n first.
• Forgetting that "flip 0 to 1" may or may not be allowed depending on the problem variant.
• Confusing Hamming distance (both directions allowed) with this one-directional variant.

Interview preparation tip

Bit change problems have two variants: bidirectional (XOR and count set bits — Hamming distance) and unidirectional (can only clear bits). Always identify which variant applies. For unidirectional, use (n | k) == n as the feasibility check (k must be a "submask" of n). Practice both Hamming distance and unidirectional bit clearing problems — they test the same XOR mechanics but with different feasibility conditions.