Microsoft Interview Question
Software Engineer / DevelopersTeam: MS Office Platform
Country: India
Interview Type: In-Person
SORRY Above code will not work
A big bug resolved below
unsigned int reverse_bits(unsigned int num)
{
num = (num<<16)|(num>>16);//every 16
num = (num & 0xFF00FF00)>>8 | (num & 0x00FF00FF)<<8;//every 8
num = (num & 0xF0F0F0F0)>>4 | (num & 0x0F0F0F0F)<<4;//every 4
num = (num & 0xCCCCCCCC)>>2 | (num & 0x33333333)<<2;//every 2
num = (num & 0xAAAAAAAA)>>1 | (num & 0x55555555)<<1;//every 1
return num;
}
Sorry, Above has a bug
Solved in below.
unsigned int reverse_bits(unsigned int num)
{
num = (num<<16)|(num>>16);//every 16
num = (num & 0xFF00FF00)>>8 | (num & 0x00FF00FF)<<8;//every 8
num = (num & 0xF0F0F0F0)>>4 | (num & 0x0F0F0F0F)<<4;//every 4
num = (num & 0xCCCCCCCC)>>2 | (num & 0x33333333)<<2;//every 2
num = (num & 0xAAAAAAAA)>>1 | (num & 0x55555555)<<1;//every 1
return num;
}
unsigned int reverseBits(unsigned int num)
{
unsigned int NO_OF_BITS = sizeof(num) * 8;
unsigned int reverse_num = 0;
int i;
for (i = 0; i < NO_OF_BITS; i++)
{
if((num & (1 << i)))
reverse_num |= 1 << ((NO_OF_BITS - 1) - i);
}
return reverse_num;
}
Time Complexity: O(log n)
Space Complexity: O(1)
#define reverse_nibble(x) (((x & 0x01) << 3) | ((x & 0x02) << 1) | ((x & 0x04) >> 1) | ((x & 0x08) >> 3))
#define reverse_byte(x) ((reverse_nibble((x >> 4) & 0x0F)) | ((reverse_nibble(x & 0x0F) << 4)))
#define reverse_word(x) ((reverse_byte(x) << 8) | (reverse_byte(((x >> 8) & 0xFF))))
#define reverse_dword(x) ((reverse_word(x) << 16) | (reverse_word(((x >> 16) & 0xFFFF))))
I assume we're talking about reversing bits. Either way, here're code which does bits reversal and number as a whole reversal:
typedef unsigned int uint;
uint ReverseBitsOfUInt(uint number)
{
uint reversedNumber = 0;
uint count = 32;
if (number)
{
while (number)
{
reversedNumber <<= 1;
reversedNumber |= number & 1;
number >>= 1;
count--;
}
reversedNumber <<= count;
}
return reversedNumber;
}
uint ReverseNumber(uint number)
{
uint reversedNumber = 0;
if (number)
{
while (number)
{
reversedNumber = reversedNumber * 10 + number % 10;
number /= 10;
}
}
return reversedNumber;
}
- Sugarcane_farmer May 28, 2014