## NVIDIA Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
8
of 8 vote

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:

``````// Rotate an integer n left by k
int rotLeft32(int n, int k)
{
return (n << k) | ((unsigned int)n >> (32 - k));
}``````

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.

A 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.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

i think you should also check whether k and n are > 0

Comment hidden because of low score. Click to expand.
0

i think you should also check whether k and n are > 0

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

why is a cast (unsigned int) required

Thanks

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````long 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);

}``````

Comment hidden because of low score. Click to expand.
0

at least test your code before you copy paste !

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

I think there are 2 bugs in this function:
- it's 32 bits rotation on 64 bits 'long long'
- since x is NOT unsigned long, the >> will cary the sign bit over to the right and the result of (x & 0xFF00FF00) is not the same as for 'unsigned long' or DWORD.

Please correct me if I'm wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

plz explain

Comment hidden because of low score. Click to expand.
0
of 0 vote

For rotation of the bits we have to rotate the bits by 32 so, we will follow the code given below
Implementation:

``````return (n << a) | (n >> (32 - a)); or
return (n >> a) | (n << (32 - a));``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.