# 3. Reverse Bits

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

if(reverseOf<(1<<3*sizeOfInt/4)) 		return Table[(reverseOf >> (2*wordSize))&bitMask] |
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! 