Bit Manipulation: Some sample questions

Practice Questions on Bit Manipulation.

Given two 32 bit numbers N, M and two-bit positions i, j. Set all the bits between i and j in N equal to M.

• Algorithm:
• Temp = ~0 //(all ones)
• left = temp - ((1<<j)-1) //(1<<j)-1 gives a number with j-1 continuous ones and rest zeros. This //This gives us a number left with all ones except last j-1 zeros.
• right = ((1<<i)-1)//this gives us a number with all zeros except last i-1 ones.
• mask = right|left //all ones except those between the ith and jth position.
• answer = (n&mask)|(m<<i) //n&mask clears all the places between ith and jth position by //placing zeros there. m<<i shifts m by i bits and taking or of these two completes the task.

Given an integer print the next largest number that have the same number of 1 bits in its binary representations.

• Algorithm:
• Traverser from right to left, and once you've passed a one turn the first 0 after it to 1. This makes us our number increase by $2^i$. Example: ******011100 now becomes ******111100.
• Turn the one just right to our current position to zero. Now it is bigger by $2^i - 2^j$ Where j=i-1. Example: ******111100 now becomes ******101100.
• Thus we are now ahead of our original number, but we are too ahead, we need to make this number close to the original number as much as possible. Make the number as small as possible by rearranging all the 1s to be as far right as possible.******101100 now becomes ******100011.

Here is the code:

bool getBit(int n, int index){
	return ((n & (1<<index)) > 0);
	} ///setting the bit what it does is crates a number with one only
	// at that index and all rest zero, and taking and with original gives answer
	int setBit(int n, int index, int to){
	if(to){
	return n|1<<index;
	}else{
	int mask = ~(1<<index);
	return n & mask;
	}
	}//setting bit at a number.
	int getNextLargest(int n){
	if(n<=0)
	return -1; //in casethe number is negative, we return -1 to denote error
	int index = 0;
	int countOnes = 0;
	while(!getBit(n, index)){ //go the location of first one
	index++;
	}
	while(getBit(n, index)){//now go to the location of first zero to left of this one. We keep count of the ones we have travelled
	index++;
	countOnes++;
	}
	n=setBit(n, index, 1); //set the zero we have reached to one
	index--; // decrement to previous location
	n = setBit(n, index, 0); //set this location to one.
	countOnGiven an integer print the next largest number that have the same number of 1 bits in their binary representations. es--; //decrement the number of ones as we have turned off a one in previous step.
	for(int i=index-1;i>=countOnes;i--){ //set all previous locations as zero except first countOnes we'll place ones there.
	n=setBit(n, i, 0);
	}
	for(int i=countOnes-1;i>=0;i--){//set all first countOnes locations as one.
	n = setBit(n, i, 1);
	}
	return n;// done return the number.

Given an integer print the number just smaller than it that have the same number of 1 bit in its binary representations.

The Algorithm is similar. Try to implement it on your own. A slight modification in the previous code will yield an answer to this problem.

• Algorithm:
• Traverser from right to left, and once you've passed a zero-turn the first 1 after it to 0.
• Turn the zero just right to our current position to one.
• Make the number as big as possible by shifting all the ones as far to the left as possible.

For code: A slight modification in getNextLargest will yield the code. Instead of tracking ones now, track for zeros and do the same things. If we were setting a bit to one, set it to zero and vice versa. Try it on your own.

Determine the number of bits required to convert integer A to integer B. Example Input: 31, 14; Output: 2.

This is a simple question, you can figure out which bits in two numbers are different by operation of xor. If a bit in the result is one that means the bits at that place in the numbers were zero.