Lintcode: Flip Bits

Determine the number of bits required to flip if you want to convert integer n to integer m.

Have you met this question in a real interview? 

Yes

Example

Given n = 31 (11111), m = 14 (01110), return 2.

Note

Both n and m are 32-bit integers.

Tags Expand 

Cracking The Coding Interview Bit Manipulation

http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/
Great Paragraph to introduce bit operations.

The key is to use bit>>n to get n bit of an integer.
<way 1> compare nth bit of a and b
<way 2> count how many bits are set for a ^ b(^ -- bitwise xor)

Both Time: O(32) Space: O(1)

way1:

class Solution {
public:
    /**
     *@param a, b: Two integer
     *return: An integer
     */
    int bitSwapRequired(int a, int b) {
        // write your code here
        int num = 0;
        for(int i = 0; i < 32; i++){
            if((a & 1<<i) != (b & 1<<i)) num++;
        }
        return num;
    }
};

way2:

class Solution {
public:
    /**
     *@param a, b: Two integer
     *return: An integer
     */
    int bitSwapRequired(int a, int b) {
        // write your code here
        int c = a ^ b;
        int num = 0;
        for(int i = 0; i < 32; i++){
            if(c & 1<<i) num++;
        }
        return num;
    }
};