techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

bit operators problem

Write a function that rotates (NOT shifts) to the right by n bit positions the bits of an unsigned char x.ie no bits are lost in this process.

For eg: -
x = 10100111 (binary)
x rotated by 3 = 11110100 (binary)
Rainmaker
Monday, March 27, 2006
 
 
while( 0 != n-- )
{
  x = ( x << 7 ) || ( x >> 1 )
}
Abdel Said Send private email
Monday, March 27, 2006
 
 
2 changes to my previous post:
while( 0 < n-- )
{
  x = ( x << 7 ) | ( x >> 1 )
}
Abdel Said Send private email
Monday, March 27, 2006
 
 
I suppose this will wrk the same

x = (x <<((8 * (sizeof char)) - n)) | (x >> n)

In case of int, it wld be size of int.
Shikha Sharma Send private email
Tuesday, March 28, 2006
 
 
No, It will not work.
for x = 11110000
    n = 10
x = (x <<((8 * (sizeof char)) - n)) | (x >> n)
  = (x <<(( 8 * 1 ) - 10)) | ( x >> 10 )
  = ( x << -2 ) | ( 0000.0000 )
  = ????
Abdel Said Send private email
Tuesday, March 28, 2006
 
 
I think small modification of Shikha Sharma's solution will work:

bits = sizeof(x)*8;
x = (x <<(bits - (n%bits)) | (x >> n%bits)

assume x is unsigned.
laios
Tuesday, March 28, 2006
 
 
laios's algorithm is faster and clean than the one I suggested.
Abdel Said Send private email
Wednesday, March 29, 2006
 
 
I think below given little protection will prevent the unnecessary shifting when bits=n
bits = sizeof(x)*8;
if(n%bits>)
x = (x <<(bits - (n%bits)) | (x >> n%bits)
Nagesh Ayyagari Send private email
Monday, May 22, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz