Algorithm

LintCode/Flip Bits

Problem Summary

Determine the number of bits to flip when converting integer n to integer m.

Solution

The answer is how many bits of (n xor m) are 1.

I think there are some relevant skills about bit manipulation that we need to know.

Binary Value Sample Meaning
x 00101100 the original x value
x and -x 00000100 extract lowest bit set
x or -x 11111100 create mask for lowest-set-bit & bits to its left
x xor -x 11111000 create mask bits to left of lowest bit set
x and (x-1) 00101000 strip off lowest bit set ( useful to process words in O(bits set), instead of O(nbits in a word))
x or (x-1) 00101111 fill in all bits below lowest bit set
x xor (x-1) 00000111 create mask for lowest-set-bit & bits to its right
~x and (x-1) 00000011 create mask for bits to right of lowest bit set
x or (x+1) 00101101 toggle lowest zero bit
x / (x and -x) 00001011 shift number right so lowest set bit is at bit 0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    /*
     * @param a: An integer
     * @param b: An integer
     * @return: An integer
     */
    int bitSwapRequired(int a, int b) {
        a ^= b;
        int ans = 0;
        
        while (a) {
            ans++;
            a &= (a-1);
        }
        return ans;
    }
};