NVIDIA Interview Question
Software Engineer / Developerslong long rot32(long long x)
{
x = ((x& 0x0000FFFF)<<16)|((x& 0xFFFF0000)>>16);
x = ((x& 0x00FF00FF)<<8)|((x& 0xFF00FF00)>>8);
x = ((x& 0x0000FFFF)<<4)|((x& 0xFFFF0000)>>4);
x = ((x& 0x0000FFFF)<<2)|((x& 0xFFFF0000)>>2);
x = ((x& 0x0000FFFF)<<1)|((x& 0xFFFF0000)>>1);
}
oops..
long long rot32(long long x)
{
x = ((x & 0x0000FFFF)<<16)|((x & 0xFFFF0000)>>16);
x = ((x & 0x00FF00FF)<<8)|((x & 0xFF00FF00)>>8);
x = ((x & 0x0F0F0F0F)<<4)|((x & 0xF0F0F0F0)>>4);
x = ((x & 0x33333333)<<2)|((x & 0xCCCCCCCC)>>2);
x = ((x & 0x55555555)<<1)|((x & 0xAAAAAaAA)>>1);
return x;
}
I believe strezh posted the implementation for bit reversal, not rotation as described at: hxxp://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c
Although the question does not state which rotation direction is required I've posted my left rotate solution:
Basically does a left-rotate using a shift. The main problem with a shift is that truncated bits are not rotated into the other "side". Therefore we use bitwise-OR to set the otherwise truncated bits after shifting them down into position.
- drivehappy March 18, 2011A right rotate implementation should be straightforward with an alteration of the shift operators.
The only gotcha is that the right-shift operation will propagate the signed bit into vacated bit positions as described here: hxxp://msdn.microsoft.com/en-us/library/336xbhcz(v=VS.100).aspx - hence why I use an (unsigned int) cast.