**Question : Write a program that takes a 64-bit word, output the reverse of that word.**

I would urge you to minimize the window and try to solve this question on your own first.

**Method – 1 Brute Force Solution**

Simply apply the bitswap method we used earlier on all the extreme bits.

int bitSwap(int num, int i, int j){
if( ( ( num>>i ) & 1 ) != ( ( num>>j ) & 1 ) ){
int bitMask = (1<<i) | (1<<j);
num ^=bitMask;
}
return num;
}
int reverseBits(int num){
if(num!=0){
int noOfBits=log2(num)+1;
for(int i=0, j=noOfBits-1; i<j ; i++,j--){
num=bitSwap(num,i,j);
}
}
return num;
}

**Time Complexity : O(k), where k is the number of bits in the number.**

** Space Complexity : O(1).**

**Method -2 Cache!**

Just like the parity bit solution we can cache the solution of smaller bits (say 16) and combine the results.

void precompute (void){
for (int i=0;i<=int(pow(2,(sizeOfInt/4))-1);i++){
Table[i]=reverseBits(i);
// cout<<i<<' '<<Table[i]<<endl;
}
return ;
}

int reverseBitsUsingTable(int reverseOf, int wordSize, int bitMask){
if(reverseOf<(1<<sizeOfInt/4))
return Table[reverseOf];
if(reverseOf<(1<<2*sizeOfInt/4)) return Table[(reverseOf >> (wordSize))&bitMask] |
Table[(reverseOf & bitMask)]<<(wordSize);
if(reverseOf<(1<<3*sizeOfInt/4)) return Table[(reverseOf >> (2*wordSize))&bitMask] |
Table[(reverseOf >> (wordSize))&bitMask]<<(wordSize) |
Table[(reverseOf & bitMask)]<<(2*wordSize); return Table[((reverseOf >> (3*wordSize)))&bitMask] |
Table[(reverseOf >> (2*wordSize))&bitMask]<<(wordSize) | Table[(reverseOf >> (wordSize))&bitMask]<<(2*wordSize) |
Table[(reverseOf & bitMask)]<<(3*wordSize);
}

**The Time Complexity : O(n/L + 2^L)**, where n is the number of bits in the word and L is the width of the word for which we cache the results. 2^L time will be taken to prepare the table, if L is known beforehand we can remove it from the notation, as we only talk about the growth of function in Big-Oh Notation.

**The Space Complexity : O(2^L)**, only a constant amount of extra space required.

The full working code is available at Github, you can star the repository to get updates. You can also follow this blog for more such posts. Comment in your queries, report bugs, discuss!

### Like this:

Like Loading...