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);
		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!:)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s