NVIDIA Interview Question
Software Engineer / DevelopersIf you don't wanna use a table in memory, there is one more way to do this.
void reverse(int x)
{
// assume 32-bit number
m = 0x55555555; // 1-bit swap
x = ((x & m) << 1) | ((x & ~m) >> 1);
m = 0x33333333; // 2-bits swap
x = ((x & m) << 2) | ((x & ~m) >> 2);
m = 0x0f0f0f0f; // 4-bits swap
x = ((x & m) << 4) | ((x & ~m) >> 4);
m = 0x00ff00ff; // 8-bits swap
x = ((x & m) << 8) | ((x & ~m) >> 8);
x = (x << 16) | (x >> 16); // 16-bits swap
}
Source from stanford/bithacks.html
Recursive version:
int maskarr[] = { 0x55555555, 0x33333333, 0x0f0f0f0f, 0x00ff00ff };
int RecursiveReverse(int x, int i) {
int m;
int p = 1 << i;
if ( i == 4 ) {
return ( x << p ) | ( x >> p);
}
m = maskarr[ i ];
x = ((x & m) << p) | ((x & ~m) >> p);
return RecursiveReverse(x, ++i);
}
/*swapping function for byte data type. The logic here is Iam extracting two bits at the same time and swapping them,then oring them and storing them in char variable res
*/
void swap_bits ( int no ) {
char up,lo,res ;
char and = 0x01 ;
for ( int i = 0 ; i < 8 ; i++ ) {
lo = val & and ;
and = shift_bits_lo ( and, 7 - i ) ;
up = val & and ;
and = shift_bits_hi ( and, 7 - i ) ;
for ( int j = 7 - i ; j > 0 ; j++ ) {
up = up >> j ;
lo = lo << j ;
}
res = up | lo ;
}
no = res ;
}
char shift_bits_lo ( char no , int shift) {
while ( shift > 0 )
no = no << shift ;
return no ;
}
char shift_bits_hi ( char no , int shift ) {
while ( shift > 0 )
no = no >> shift ;
return no ;
}
Hey poor folks,..you solution is not at all suited for embedded systems with limited stack...
@ VIZ - you had almost neat solution but it can still be optimized for many aspects.
1. For x=0, you do not want to reverse bits at all and just return uint y directly..
2. Inside for loop, you can combine step 1: y<<=1; and step 2: y |= (x & 1) both into a single step. It will avoid creation of temporary variable on stack for step 1. See my solution below..it will avoid temp var creation and encourage usage of general purpose CPU registers for quick computations.
3. For loop requires usage of temp var i to control number of loops.. it is not at all needed.. it is replaced by while loop as shown below.. this avoids significant stack usage and speed up every iteration.. (++i an i<32 checks consume time)
here is the code that is used for this reverse operation in many embedded system software design..
uint reverse(uint x)
{
uint num=0;
while(x>0)
{
num = num<<1 + (x& 0x01);
x >>= 1;
}
return num;
}
x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); //Only this line if 2 bits can represent the integer
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2); //This and all above if 4 (or less) bits can represent the integer
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4); //This and all above if 8 (or less) bits can represent the integer
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8); //This and all above if 16 (or less) bits can represent the integer
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16); //This and all above if 32 (or less) bits can represent the integer
So all above four lines can be used for any integer (32 bit integer)
unsigned int reverseBits(unsigned int x){
x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4);
x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8);
x = (x << 16) | (x >> 16);
return x;
}
the question is to reverse the bits i.e. input 11110000 output : 00001111
the solution provided above is a toggle which can be done with operator ~
int toggle (int x) { return ~x;)
use lookup table to store reversed bits of every possible combination in a 8-bit field, so your lookup table is O(1) in memory with 256 elements. then:
- hemantajay November 19, 2009