Bit Manipulation
A Binary digit(Bit) is a computer's simplest form of data storage. Each bit can only be in one of two possible states(0 and 1).
Before proceeding with manipulations of bits, it is always best to learn how to get the Binary representation of a given number and vice versa.
Decimal to Binary Conversion:
Most Significant is always Sign bit.MSB is 0 in the case of positive numbers and 1 in the case of negative numbers. Negative numbers are represented in 2’s complement in the computer.
In the example below, I am just considering the last 4 bits of a number. If we take 32 bits, then take all 32 bits for a positive number and do 2’s complement to get a representation of the corresponding negative number.
The representation of -13 is nothing but two’s complement of 13 in its binary representation. Two’s complement is calculated by adding 1 to one’s complement.
Example: The last four bits in the representation of -13 is 0011.
One’s complement of 13 is 0010. Adding one to it gives 0010(13) gives 0011
For better knowledge of the representation of negative numbers, please refer to https://www.geeksforgeeks.org/representation-of-negative-binary-numbers/
Each byte can be represented with 8 bits. So, an Integer that occupies 4 bytes of memory will have 32(4*8) bits.
Binary to Decimal Conversion:
For a binary number with n digits: dn-1 … d3 d2 d1 d0. The decimal number is equal to d0×2⁰ + d1×2¹ + d2×2² + ….
Example:
The decimal representation of (11011) is 1*16+1*8+0*4+1*2+1*1 =27
Bitwise Operators:
AND(&): The & operator takes two operands and performs a bitwise AND operation on each digit of two numbers. The result of the & operator is 1 if both bits have the value 1.
OR(|): The | operator takes two operands and performs a bitwise OR operation on each digit of two numbers. The result of the | operator is 0 if both bits have the value 0.
XOR(^): The ^ operator takes two operands and performs a bitwise OR operation on each digit of two numbers. The result of the ^ operator is 0 if both bits have the same value.
NOT(~): The ~ operator takes one operand and flips every bit of that operand.
Left Shift(<<): Left shift operator takes two operands and shifts bits of the first operand to the left. The number of bits to be shifted is decided by the second operator.
Example: 9 << 1 → 1001<<1 → 10010(18)
Right Shift(>>): Right shift operator takes two operands and shifts the bits of the first operand to the right. The number of bits to be shifted is decided by the second operator.
Example: 9 >> 1 → 1001>>1 → 0100(4)
Main Bit Manipulation Techniques used in Coding Questions:
1. Compute and return 2 power N
Solution:
2 power N is nothing but setting a bit in the N th position of a number.
Example: Binary representation of 4 is (100), which can be calculated by (1<<2).
2. Checking if bit i is set in a number N
Solution1:
To check whether a bit i is set in a number or not, we can do the ‘and’ operation of that number with another number containing only a bit i as 1 and the remaining bits as 0.
To generate a number with the only bit i as 1 can be done with 1>>i. After finding the number with bit i set, we can do the ‘and ’operation with n.
(N & (1 << i)) != 0
Solution2:
Similar to the above approach, we can also check the bit i by shifting i th bit in N to the least significant bit position and then doing bitwise and operation with 1.
Shifting bit i to Least significant position is done with N>>i operation.
((N>>i) & 1) != 0
3. Given two positions, x and y, return the number with x and y bits set.
A bit x can be set in a number by doing 1<<x.
So, the solution for setting x and y bits is (1<<x) | (1<<y). (OR operation sets the bit ‘i’ if bit i is set in either of its two operands)
4. Check if two given signed integers x and y are of the same sign.
For signed integers, the most significant bit indicates the sign of the number. If MSB is 1, it suggests that the number is negative. A positive number will have MSB as 0.
To know whether two integers are of the same sign or not, we can perform the xor operation. As MSB indicates sign, if both integers have the same sign, the xor will give a positive number.
(x ^ y) ≥ 0
5. How to calculate the number of set bits in a number
Approach1: Check whether every bit is set or not in an integer by using the approach in the second question above.
Approach 2:
From the above image, it is clear that N&N-1 will only clear the least significant bit of N, and the remaining bits remain unchanged. So we can use this concept to calculate the number of set bits in a given number.
6. Compute pow(int a, int N)
Example: The calculation of power is shown in the below image.
7. Construct a number with x set bits, followed by y unset bits, for 1≤ x,y ≤10
Solution: ((1 << x) -1)<<y (or) (1<<(x+y)) — (1<<y)
Example:
x = 3, y = 5 => (11100000)2
x = 2, y = 1 => (110)2
8. Given an array with size n, which contains elements from range 1 to n. One number is repeated, and one number is missing. Find these two elements.
Solution:
Using XOR
i. Let a and b be the two numbers to be found.
ii. XOR the given array with the numbers 1…n, call it X.
iii. You have: X = a ^ b.
iv. Extract any set bit from X. The bit position indicates that this bit is different in a and b.
v. Based on this bit position, separate the array into two parts — One having numbers with this bit set and the other having numbers with this bit unset. Call this SetA-0 and SetA-1.
vi. Do step(v) for the numbers in the range 1…n and call them SetB-0 and SetB-1.
vii. a = SetA-0 ^ SetB-0; b = SetA-1 ^ SetB-1;
viii. Check which is missing and which is repeated, using the array.
More practice Questions on Bit Manipulation:
