Basic Bit Manipulation Algorithms
I assume that you are familiar with bit-wise operators in your favorite programming language. They usually look useless at first glance but when used properly they can become quite handy. 😉
In this article we will talk about common bit manipulation algorithms using bit-wise operators. In case you are not familiar with bit-wise operators, you can quickly take a look at basics of bit manipulation at HackerEarth.
Odd and Even Numbers
You probably know the traditional way of checking if a number is odd or even. You simply check if the number is divisible by 2 or not:
if (num % 2 == 0) {
// even number
} else {
// odd number
}Since we are learning bit manipulation, let’s see how we can check it by using bit-wise operators. In this case you just need to follow one simple rule: in binary representation of a number, if the last bit is zero, it is even, if the last bit is one, it is odd. So all we need to do is to check last bit of a number; how can we do that?
Just bit-wise AND the number with 1:
if (num & 1 == 0) {
// even number
} else {
// odd number
}If you write it on a paper, you will see that it is always correct. For example, to see if 5 is even or odd, you will do something like this:
Getting, Setting and Clearing the ith Bit
Often times we might need to check if ith bit is set or not: meaning that if a bit in particular position (ith position) is 1 or 0. Or we might want to change that bit from 0 to 1 or vice versa. We can also achieve this using bit-wise operators.
Note: we start counting from 0 and from right to left in these examples. In any other cases you can just play with the number i.
Getting ith Bit
To check the last bit of a number we AND-ed it with a number that has all zeroes but a single 1 at the end. Similarly, if we had a number that has 1 at some specific position and all other bits are zeroes, then we can AND it with any number and get that number’s bit at that position.
To get such number we need left shift operator. For example, if you have 0001 and you left shift it by 2 positions it will be 0100.
Let’s say we want to get 2nd bit of the number 5:
In the picture above, the resulting number is 100 in binary form; if result is greater than zero we can confidently say that 2nd bit is one, else the 2nd bit is zero. The code to do this will look like this:
int getIthBit(int n, int i) {
int mask = (1 << i);
int result = n & mask;
if (result > 0) {
return 1;
}
return 0;
}Setting ith Bit
Setting a bit means changing a bit to one. Setting the ith bit is almost same with the getting ith bit, but here we are going to use bitwise OR operator. If we get a number that we called mask last time, all we need to do is apply OR operator to the mask and the number:
void setIthBit(int &n, int i) {
int mask = (1 << i);
n = (n | mask);
}Again, you can try it with pen and paper on your own. Let’s see how it looks when we want to set 1st bit of the number 5:
Clearing ith Bit
Clearing a bit means changing it to zero. As we saw previously, we used left shift operator to get a number that has all zeroes but has single 1 at position i. Now we need a number that has all ones but has single 0 at position i. How can we do that? Simple. Just negate the number we found previously — use bit-wise NOT operator.
After we find our mask, all we need to do is to and the mask and the number:
void clearIthBit(int &n, int i) {
int mask = ~(1 << i);
n = (n & mask);
}I am leaving the pen and paper stuff to you now 😅
Modifying range of bits in a number
Now that we know how to play with bits at a specific index, let’s learn how to manipulate range of bits in a number.
Clear Last i Bits
Suppose that we want to make last i bits of a number zero. We already saw that when clearing a bit we made a mask that has all ones and a single zero. Recall that we created that mask by shifting 1 to left by i places and then negating it: ~(1 << i) .
To clear last i bits, we need to create a mask that has all ones but zeroes at first i positions; so something like this: 11111111000. This is a number that has all ones but first 3 bits are zeroes. If we bit-wise AND this with any number we will clear last 3 bits of that number.
To get such number we need to left shift 11111111111 by 3 places: 11111111111 << 3 . But what is the number that has all ones? If we are talking about the signed integers, then the answer is -1 . To understand why -1 is all ones in binary form you need to understand how signed integers are represented in memory.
Finally, our function will look like this:
void clearLastIBits(int &n, int i) {
int mask = (-1 << i);
n = (n & mask);
}Clear Range of Bits
We already know that, to clear a bit we need to AND that number with a mask which has zero at that particular index. And to clear first i bits, we created a mask that has i number of zeroes at the beginning.
Clearing range of bits might be a bit more complicated. We need a mask that has zeroes starting from ith position and ending at jth position; something like this: 111110000111.
This number can also be written as 111110000000 | 000000000111 . Let’s illustrate it below, so it is much clear for you:
Finding first number is fairly easy, because we have seen it before, right? Let’s call first number a, then int a = (-1 << j + 1) and second number will be just two to the power of i minus one, which we can simply write as int b = (1 << i) - 1.
Now that we know first and second numbers, the mask will be OR of these two numbers:
void clearRangeOfBits(int &n, int i, int j) {
int a = (-1 << j + 1);
int b = (1 << i) - 1;
int mask = (a | b);
n = (n & mask);
}Checking If a Number is Power of Two
If a number is power of two, the most significant bit of its binary representation will be 1 and the other bits will be zero.
For example, 16₁₀ = 10000₂
The interesting property of such numbers is that if you subtract 1 from such number, the most significant bit will be zero and all other bits will be one.
For example, 15₁₀ = 01111₂
Now, if you bit-wise AND 15 and 16, it will give you zero. Finally, our function will look like this:
bool isPowerOfTwo(int n) {
return (n & (n - 1)) == 0;
}Counting Number of 1 Bits in a Number
Counting number of 1 bits in a number is fairly easy problem. All we need to do is right shift number by 1 place and check the last bit if it is one or zero. And we’ll continue doing as long as the number is greater than zero:
int numberOfOneBits(int n) {
int count = 0;
while (n > 0) {
int lastBit = (n & 1);
count = count + lastBit;
n = n >> 1;
}
return count;
}And if you want to know the complexity of this algorithm, it is O(log n), because by right shifting n each time, we’re dividing it by two each time. It is not so bad, but we can do a bit better.
There is a faster method to count number of 1 bits. I am putting solution here, and I leave it to you to figure out why it works and why it is faster:
int numberOfOneBits(int n) {
int count = 0;
while (n > 0) {
n = (n & (n - 1));
count++;
}
return count;
}You can check this article about Brian Kerninghan’s algorithm if you need a clear explanation.
Conclusion
This is it about basic bit manipulation algorithms. I hope you enjoyed and learnt something new. If you want to learn more about algorithms related to competitive programming check out Competitive Programming Essentials, Master Algorithms 2022 course on Udemy.
