NVIDIA Interview Question for Software Engineer / Developers






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

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:

int input,result;
  result=((table[input&0xff]<<24)|(table[(input>>8)&0xff]<<16)|(table[(input>>16)&0xff]<<8)|(table[(input>>24)&0xff]));
  return result;

- hemantajay November 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

its an embedded system.. i dont think keeping a table in memory is a good idea.

- sid December 22, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

graphics.stanford.edu/~seander/bithacks.html

- Anonymous January 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

unsigned int v; // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{
r <<= 1;
r |= v & 1;
s--;
}
r <<= s; // shift when v's highest bits are zero

- isisme January 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int reverser (int in) {

    int out = 0;
    int m = 0x8000;
    int tmp = 0;

    for (int i=0; in!=0; i++) {
        tmp = in & m;
        in = in<<1;
        out = (tmp<<i) + out;
    }

    return out;
}

- Nitin February 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If 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

- Radz March 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sanjay July 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Keep in memory that size of int is not known.

Thanks,
NNS Chowdary (+91 959 1234 239)

- NNS Chowdary August 08, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*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 ;
}

- chetan May 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static uint Reverse(uint x)
{
uint y = 0;
for (int i = 0; i < 32; ++i)
{
y <<= 1;
y |= (x & 1);
x >>= 1;
}
return y;
}
for 32 bit OS

- viz December 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- CodeGeek January 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Anurag Singh January 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//assuming 32 bit no.
int reversebits(int n)
{
int temp=1<<31;
int right_shift=31;
int left_shift=0;
int rev=0;
while(temp)
{
int no=temp&n;
no>>right_shift;
no<<left_shift;
rev|=no;
right_shift--;
left_shift++;
temp>>1;
}
return rev;
}

- Andrew October 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- swapnilsj August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int reverse(int m){
  int n = 0;
  while(m !=0){
     if((m & 1) == 1) n = (n <<1) | 1;
    else n = n <<1;
   m = m >> 1;
  }
  return n;

}

- bharat April 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

xor the bits with ff.
example : 0000 0011
1111 1111
------------(XOR)
1111 1100

- Gopal November 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

xor the bits with ff.
example :

0000 0011
1111 1111
------------(XOR)
1111 1100

- Gopal (with clear example) November 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

question is about reversing and not inverting

- kim July 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous November 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it might be

int input,result;
  result=((table[input&0xff]<<24)|(table[(input>>8)&0xff]<<8)|(table[(input>>16)&0xff]>>8)|(table[(input>>24)&0xff]>>24));

return result;

- Franklin Fang January 04, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More