# 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] |