Bitmask and Bit Manipulation
Get started
জয় শ্রী রাম
🕉A Bitmask is data that is used for bitwise operations, particularly in a bit field. Using a bitmask, multiple bits in a byte can be set either turned on (i.e, 1), off (i.e, 0) or inverted from on to off (or vice versa) in a single bitwise operation.
Let's discuss some bit manipulation operations often done on bitmasks to solve different problems:
Setting A Bit
Setting a bit means setting that bit to 1. The opposite operation is called resetting a bit or clearing a bit which involves making a bit zero.The bit that we set is always one irrespective of whether it was one or zero before. No changes occur to any other bits. How can we achieve this ? Remember that in OR operation 0 | 1 = 1 and 1 | 1 = 1. We get 1 on a bitwise OR for bot 0 and 1. So an easy and effective solution would be to take a binary number which has 1 at the bit we want to set, and 0 in all other bits, and then OR it with the number we are trying to operate on. So if we want to set the 0 at 3rd bit from right (zero based index) of 1110111 then we would need to do an OR with 0001000.
e can get the number with which we need to do OR as follows:
Remember that 1 is represented as 00000001. If you want to set, say, bit at position 3 from right, then K should be equal to 00001000. We can get 00001000 by shifting 1 three positions towards left. 00001000 = 00000001 << 3 = 1 << 3.
It is very important that we understand the above concept very well. The rest of the discussion will be based on this discussion.
Let's look at the code how to set ith bit from right:
public int setBit(int inputNumber, int bitPositionFromLeft) {
int binaryNumberWithOneAtTheRequiredPositionAndZeroEverywhereElse = 1 << bitPositionFromLeft;
return inputNumber | binaryNumberWithOneAtTheRequiredPositionAndZeroEverywhereElse;
}
Notice that (0001)2 = (20)10 = (1)10, (0010)2 = (21)10 = (2)10, (0100)2 = (22)10 = (4)10 and so on. ()2 indicates number in binary and ()10 indicates number in decimal.
Clearing/Resetting A Bit:
Clearing or Resetting a bit will make that bit equal to 0. So, if we have understood the core of the concept described above, we would quickly know that we need an operation that gives you 0 for both 1 and 0. AND with Zero fits perfect here because 0 & 0 = 0 and 1 & 0 = 0.So if we want to reset 3rd bit from left (0 based index) we would need 11110111. How can we get this ? Look that it is complement of 00001000. 11110111 = ~00001000. So we can just compute 00001000 and flip all the bits.
public int resetBit(int inputNumber, int bitPositionFromLeft) {
int binaryNumberWithOneAtTheRequiredPositionAndZeroEverywhereElse = 1 << bitPositionFromLeft;
return inputNumber & ~binaryNumberWithOneAtTheRequiredPositionAndZeroEverywhereElse;
}
Get Bit:
What Get Bit does is returns if the it at ith position is 0 or 1.We know ANDing a number with 1 gives back the same number, since 0 & 1 = 1 and 1 & 1 = 1.
What we can do is: if we are interested in knowing what ith is, we can form a number that has 1 at ith bit and 0 in all other bits. Now, if the number has 0 in ith bit then the number AND one will give you ZERO. If the ith bit is 1 then we will get a non-Zero number.
public int getBit(int inputNumber, int i) {
int k = 1 << i;
return (inputNumber & k == 0) ? 0 : 1;
}
Flipping Bit
Here we are interested in flipping ith bit (from right) from 0 to 1 or vice versa.So, for the ith bit we are interested in finding an operation either with 0 or 1 that would give us the flipped bit.
So, what we are trying to accomplish is expressed in below two expressions:
0 < some operation > < either 0 or 1 > = 1
1 < some operation > < either 0 or 1 > = 0
Or, more explicitly,
0 < some operation > 0 = 1
and
1 < some operation > 0 = 0
OR,
0 < some operation > 1 = 1
and,
1 < some operation > 1 = 0
We see that the expressions 0 < some operation > 1 = 1, and, 1 < some operation > 1 = 0 holds true for XOR.
Since, 0 XOR 1 = 1 and 1 XOR 1 = 0.
We also know that, XOR'ing a number with 0 returns the same number since 0 XOR 0 = 0 and 1 XOR 0 = 1.
So to flip ith bit we should use a number that has 1 at the ith bit and 0 in all other bits for XOR'ing.
In Java, we use ^ for XOR.
public int flip(int inputNumber, int i) {
int k = 1 << i;
return inputNumber ^ k;
}
Flipping All Bits
Flipping all bits changes all 1s to 0 and all 0s to 1 in a binary number. We achieve this by~ sign.
num = ~num flips all bits of variable num.
ARITHMETIC Right Shift (>>) vs. LOGICAL Right Shift (>>>)
>>
In most common cases we use ARITHMETIC Right Shift or >>.>> does exact opposite of <<
>> shifts bits towards right. Doing >> each time is equivalent to dividing by 2. Which means, M >> N always gives you M / 2N. M can be positive or negative. M > 0 or M >= 0.
According to the discussion above if we do (-75) >> 1, we should get floor((-75) / 21) = floor(-37.5) = -38.
Now let's see if this is what actually happens when we do >> operation:
(-75)10 = (10110101)2
Please note that the 1 in the Most Significant Digit (the first 1 in 10110101) is sign bit. It is 1 because it is a negative number. It would have been 0 if it were a positive number.
(..) is used to indicate a sign bit.
(1) 0 1 1 0 1 0 1
\ \ \ \ \ \ \
\ \ \ \ \ \ \
\ \ \ \ \ \ \
\ \ \ \ \ \ \
_\| _\| _\| _\| _\| _\| _\|
(1) 1 0 1 1 0 1 0
So what we got is 11011010 which is indeed -38 since (11011010)2 = (-38)10
It is important to note that if we right shift N times i.e, if we do (>> N) operation the first N bits (from left to right) will be the bit equal to the sign bit, i.e, for negative numbers we would have N trailing 1s and for positive numbers we'd have N trailing 0s. Just do the shifting operation shown in above diagram quite a few time (i.e, >> 2, then >> 3 and so on) and see yourself how the sign bit propagates.