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

2. Swap bits

Question : Given a number and 2 indices return the number after swapping bits present at those indices.

Method-1 : Brute-Force
We can swap bits by following the given steps :-
1. Using bitmasks to extract the ith and jth bits.
2. Save the extracted bits to some local variables.
3. Write the jth  bit to the ith position and vice-versa.

int bitSwapBruteForce(int x, int i, int j){
	int temp1= ((x & (1<<i)) !=0);
	int temp2= ((x & (1<<j)) !=0);
	x = temp1==1 ? (x | ( temp1<<j) ) : (x & ~(1<<j));
	x = temp2==1 ? (x | ( temp2<<i) ) : (x & ~(1<<i));
	return x;
}

The Time Complexity : O(1), only a constant amount of operations are required.
The Space Complexity : O(1), only a constant amount of extra space required.

Method-2 : Oh! Its beauty.
Since a bit can take only two values we can do better, lets swap only when bits differ. We’ll use the magical XOR once again.


int bitSwapSuccinct(int num, int i, int j){
	if( ( ( num>>i ) & 1 ) != ( ( num>>j ) & 1 ) ){
		int bitMask = (1<<i) | (1<<j);
		num ^=bitMask;
	}
	return num;
}

As ith and jth bits of num differ, only 1 of them would be 1, resulting in bitMask having only one 1 in its bit representation. Now the XOR would swap the bits with help of bitMask.

For num=(1110)2, i=0, j=2;
bitMask=(1)2 | (100)2 = (101)2
num = (1110)2 XOR (0101)2 = (1011)2

The Time Complexity : O(1), only a constant amount of operations are required.
The Space Complexity : O(1), 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!:)