Microsoft Interview Question Software Engineer / Developers
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
For each bit--- B to G
G[i] = XOR(B[i+1], B[i])
For each bit --- G to B
B[i] = XOR(B[i+1],G[i])
Comment hidden because of low score. Click to expand.
0
of 0 votes
the idea is that applying n-1 times gray code function to an n-bit integer gives the inverse gray code,
note also that: applying gray code 2 times is: x ^ (x >> 2), this can be easily verified: y = x ^ (x >> 1), z = y ^ (y >> 1) = (x ^ (x >> 1)) ^ ((x ^ (x >> 1)) >> 1) = x ^ (x >> 1) ^ (x >> 1) ^ (x >> 2) = x ^ (x >> 2).
That is, to apply gray code n-1 times we do the following (for 32-bit ints):
inverse_gray_code(int x) {
x ^= (x >> 1);
x ^= (x >> 2);
x ^= (x >> 4);
x ^= (x >> 8);
x ^= (x >> 16);
return x;
}
Gray Code --- Binary Code -- decimal equivalent
- Sunaina May 29, 20070000 0000 0
0001 0001 1
0011 0010 2
0010 0011 3
0110 0100 4
0111 0101 5
0101 0110 6
0100 0111 7
1100 1000 8
1101 1001 9
1111 1010 10
1110 1011 11
1010 1100 12
1011 1101 13
1001 1110 14
1000 1111 15