How to Determine the Number of Bits Required to Convert One Integer to Another?

This is another classic interview question: You are asked to write a function (in C/C++) that determines the number of bits required to convert one integer to another. The integers do not have to be 32-bit necessary. It could be 64-bit as well.

For example, given input 31 and 14, your function should output 2.

Bit Manipulation

If two bits are different, the XOR (exclusive or) will return 1. This makes it easier to determine if we should change bits. We compare bits one by one. This can be just accomplished using three lines of code, in the following C/C++ function.

1
2
3
4
5

int bitsRequired(int a, int b) {
    int r = 0;
    for (int c = a ^ b; c != 0; c = c >> 1) r += c & 1;
    return r;
}

int bitsRequired(int a, int b) {
    int r = 0;
    for (int c = a ^ b; c != 0; c = c >> 1) r += c & 1;
    return r;
}

We initialize variable c to be the exclusive-or of both integers. At each iteration, we check the LSB (Least Significant Bit), increment the answer if it is 1. Shift one position (abandon LSB) at each iteration until the variable becomes zero (finished checking all bits).

–EOF (The Ultimate Computing & Technology Blog) —