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.

Bit Manipulation: Left Shift And Right Shift Operators.

Left Shift:

The '<<' operator is used to perform Left Shift Operations.

'x<<y' means x shifted by y bits to the left. Like $00101<<2=10100$.

If you start shifting and you run out of space, the bits just drop off. Here are some more examples:

\[00011001<<2=01100100\]

\[00011001<<4=10010000\]

Right Shift:

The '>>' operator is used to perform the Right Shift Operations.

'x>>y' means x is shifted by y bits to the left. Like $00101>>2 = 00001$. If you start shifting and you run out of space, the bits just drop off the end. Here are some more examples:

\[00011001>>2=00000110\]

\[00011001>>4=00000001\]

Bit Manipulation: AND, OR, XOR operations.

AND Operation:

AND operations on bit is represented by '&'. These are the rules for an '&' operation on bits:

• 0&0=0
• 1&0=0
• 0&1=0
• 1&1=0

When applying AND operation on binary with multiple bits, the only thing you have to do is to apply AND bit-wise. Apply AND to each corresponding pair of bits. Here are examples:

• 1010 & 0101=0000
• 1111 & 0000=0000
• 1110 & 1010 = 1010

OR operation:

Or operation on bits is represented by '|'. These are the rules for a '|' operation on bits:

• $0|0=0$
• $1|0=1$
• $0|1=1$
• $1|1=1$

When applying OR operation on binary with multiple bits, the only thing you have to do is to apply OR bit-wise. Apply OR to each corresponding pair of bits.

• $1010 | 0101=1111$
• $1111 | 0000=1111$
• $1110 | 1010 = 1110$

XOR operation:

Or operation on bits is represented by '^'. These are the rules for a '^' operation on bits:

• $0^0=0$
• $1^0=1$
• $0^1=1$
• $1^1=0$

When applying OR operation on binary with multiple bits, the only thing you have to do is to apply OR bit-wise. Apply OR to each corresponding pair of bits.

• $1010 | 0101=1111$
• $1111 | 0000=1111$
• $1110 | 1010 = 0100$

Bit Manipulation: Adding and Subtracting two bits.

Adding and Subtracting two bits:

Adding two bits:

Adding two binary is easy. And is similar to adding a decimal number. Here are the rules for adding binaries:

• When adding two ones $1 + 1 = 1 0$. The1 is carried to the bit at left.
• When adding zero and one: $1+0=1$ similarly $0+1=1$
• When adding two zeros: $0+0=0$

Thus when adding $1010 + 0110$ these steps are to be followed:

• Add the least significant bits/last bits first. It gives $0+0=0$.Thus the last bit of result is going to be zero.
• Second last bits: $1+1=0$ and 1 is left as a carry for the third last bit.
• The third last bit is summing a zero, a one and a carry of one from previous steps. Thus $1+ 0 + 1 = 0$ and 1 is left as a carry for our first bit.
• Finally, for the first bit, we have to add a one from the carry, a one and a zero. That is: $1 + 1 +0 = 10$ This is written as it is. 
• The result is thus: $10000$

Try your hand at the following sums:

1. $10110110 + 10101000 = 101011110$
2. $100110 + 101 = 101011$
3. $101101 + 1110 = 111011$

Subtracting two bits:

Subtracting two bits is fairly similar to decimal subtraction. Here are the basic rules for bit subtraction.

1. $1-0=1$
2. $1-1=0$
3. $0-0=1$
4. $0-1=1$ with a carry of one. This step needs explanation. 

Let us take an example of $1010-0001$ This is $10-1$ in decimal notation.

1. We start with the last binaries: which is $0-1$ Now this is something which can't be done normally. We look at the binary at the left of the greater binary which is here, 1010. The bit at the left of last bit is a one. We cut it replace it with a zero and place two ones over the last bit. What we have done is, written the last two bits as a sum: $10 = 1+1$. Thus the last bit becomes $1 + 1 + 0$ Now subtraction can be done. We have to subtract one from it. Thus $1 + 1 + 0 - 1 = 1$.
2. Now, coming to the second last bits. Now the second last bit of 1010 is turned into a 0 and we have to subtract a zero from it. It is easy, add a zero at the left of your answer from the previous step.
3. The second bit is again zero minus zero. Add a zero at the left of your answer.
4. Now, we finally have one minus zero. Add one to your answer. Your answer now, it: 1001.

Let us try a different number: $1000 - 0001$.

1. The last bits are zero and one, can not subtract normally.
2. the left bit of 0 in 1000 is a zero. Can not carry normally.
3. Again a zero bit as the second bit in 1000.
4. Finally, we have one. We cut it replace it with a zero and place two ones at the second bit in 1000. Thus the second bit is : $1 + 1 + 0$. What we have done essentially is replaced 1000(8) with a sum of two fours. We now take one of these ones, cut it to make this bit as $0 + 1 + 0$and add two ones at the second last bit. Which is now, $1 + 1 + 0$. This time we have replaced a four with two twos. Again we take one of these ones. And place two ones on the last bits. Here we replaced a one with two ones. The last bit is now $1 +1 + 0$.
5. Now our last bit is $1 + 1 + 0$. Second Last bit is $0 + 1 + 0$. Second bit is $0 +1+0$. And the first bit is : $0$.
6. We can subtract 0001 now easily. The last bit of our answer is $1+1+0-1=1$. The second last bit is 1, the second bit is 1 again and the first bit is 0, The answer is $0111$.

Binary Search Tree: Implementation in C++

Binary Search Tree:

Before going ahead: I hope you've read all that is required about trees. If you haven't you can read it here: https://rishabhjainiitbhu.blogspot.com/2019/07/introduction-to-trees-c-data-structures.html
Further reading, basics about Binary trees is also suggested, you can do it here:
https://rishabhjainiitbhu.blogspot.com/2019/07/binary-trees-c-trees.html


Binary Search Trees(BSTs) are balanced binary trees, such that for each node in the tree value of all the nodes in the left subtree are smaller or equal than the parent node, and the value of all the nodes in the right subtree are larger than the parent node.

Thus the above-given graph is a binary search tree.

Binary search tree lets you do search, Insertion, and removal of all elements in order of $O(log n)$

Here is the code for insertion and searching in a BST.

The Code:

Here is the code for representing each node. We have used structures to represent it.

	struct Node{
	int data;
	Node* left;
	Node* right;
	};

Each Node contains a link to a right and a left sub-tree besides the data field.

Here is the class BST

class BST{
	private:
	Node* root;
	public:
	BST(){
	root = NULL;
	}
	void add(int data, Node** n){
	Node* parent = *n;
	if(parent == NULL){
	Node* new_node = new Node;
	new_node->data = data;
	*n = new_node;
	return;
	}
	if(parent->data>data){
	add(data, &(parent->left));
	}else{
	add(data, &(parent->right));
	}
	}
	bool search(int data, Node** n){
	Node* parent = *n;
	if(parent == NULL){
	return false;
	}
	if(parent->data == data)
	return true;
	if(data > parent->data){
	return search(data, &(parent->right));
	}else{
	return search(data, &(parent->left));
	}
	}
	Node* getRoot(){
	return root;
	}
	};

Let us break it piece by piece. Here is the insertion function:

void add(int data, Node** n){
	Node* parent = *n;
	if(parent == NULL){
	Node* new_node = new Node;
	new_node->data = data;
	*n = new_node;
	return;
	}
	if(parent->data>data){
	add(data, &(parent->left));
	}else{
	add(data, &(parent->right));
	}
	}

We pass have used recurrsion to add the data. At each node we check if the node is null, in that case we assign it a new node. If not, we check if the given data is greater than the data in the node and proceed accordingly. The process of insertion takes $O(log n)$

Note here, we have used double pointers to pass the root node by reference.

Here is the search function:

bool search(int data, Node** n){
	Node* parent = *n;
	if(parent == NULL){
	return false;
	}
	if(parent->data == data)
	return true;
	if(data > parent->data){
	return search(data, &(parent->right));
	}else{
	return search(data, &(parent->left));
	}
	}

The code is simple if you've got the process of insertion. Again we have used recursion to search elements and it takes $O(log n)$ to search elements.