As it is said, great things are in small ones. Its someway true in C as well. Working on bits rather than bytes, and other bigger data structures leverage implementations in speed and space efficiency. With really high end computers coming up these days, bitwise operations may not be that useful in terms of space efficiency. However, certain bitwise operators do pace up the speed of the implementation. Moreover, considering embedded systems programming, memory is really a paramount factor in optimisations. Hence, bitwise operators and operations are really helpful in such embedded systems programming environment.
To get a know how of the basics, lets understand basic bitwise operators and how they work. First of all, one should be aware of the binary representation of numbers and two’s complement.
AND (&) Operator
The AND operator works on two 1bit operands such that, only if both are 1, it results as 1, else it results as 0.
For Example:
OR () Operator
The OR Operator works on 1bit operands such that, if any of the two is 1, it results as 1, else it results as 0.
For Example:
XOR (^) Operator
The XOR operator works on 1bit operands such that, if both are 1 or of both are 0, it results as 0, else if any of them is 1 and other is 0, it results as 1.
For Example:
Left Shift(<<) Operator
It is a one operand operator. The Left shift operator works on a set of bits i.e a number represented by ‘n’ bits, and when shifted by an operand ‘k’, it shifts its ‘k’ bits towards left by ‘k’ replacing the trailing bits with zeros.
For Example:
Right Shift(>>) Operator
It is a one operand operator. The Right shift operator works on a set of bits i.e a number represented by ‘n’ bits, and when shifted by an operand ‘k’, it shifts its ‘k’ bits towards right by ‘k’ bits replacing front bits with zeros.
For Example:
Not (~) Operator
The Not Operator is a one operand operator, which just toggles every bit of the nbits number.
For Example:
To summarize all the bitwise operators in a table:
Some common scenarios to use bitwise operators
There are many cases and scenarios where bitwise operators are really helpful. It is not that, bitwise operators are needed to be used, its only because they make the implementation efficient, hence they are preferred. Worth mentioning, for all such scenarios, it works for negative numbers as well, which are represented in the two’s complement in the binary representation. However, the two’s complement representation itself takes care of it. So, most of the bitwise operations and tricks work fine for negative numbers as well.
Multiply or divide by two
Consider a multiplication operation, it involves reading registers, and then applying the multiplier to the two registers at the low level. Division is even more expensive operation. However, when the multiplication or division is by a number which is power of 2, it can be much optimized using shift operators. Shift bitwise operations are much efficient at low levels.
For example:
Code:
//In Binary,
00000001 << 1 = 00000010
// In decimal
1<<1 = 2
The above computation simply multiplies the number by 2, which shifted by 1. Hence, every left shift of ‘k’ bits, multiplies the number by 2 raise to the power k. Similarly, every right shift by ‘k’ bits divides the number by 2 raise to the power k.
This is a very common optimization trick used in bitwise operations
Determine if a number is power of 2
Here we have a problem, where we need to devise an algorithm to determine if the inputted number is a power of 2 or not. To start with an example, like 2, 4, 8, etc.
There may be a number of solutions to it using loops, conditionals. Lets just think about it at bit level. Write down the binary representation of positive result values, and observe the pattern
Code:
2 > 00000010
4 > 00000100
8 > 00001000
Note, in all the numbers which are power of 2, it consists of just one 1, which is followed by all trailing zeros. One solution to think of could be, count the number of 1’s in the binary representation and if this count equals to 1, then the number is a power of 2.
Still, this solution would include a loop, to count the number of 1’s in the number. There could be a better way out, as we just need to check if number has just one 1.
Understanding binary representations, and its patterns in which they increment, note how 2, 4 or 8 are reached.
Code:
00000000
00000001
00000010
00000011
00000100
00000101
00000110
00000111
00001000
Note, starting from the least significant bit, it starts incrementing the bits i.e. from 0 to 1. Once, it reached 1, it increments the next least significant bit and starts the loop for it with all exhausted (following bits) bits as 0. Therefore, for all, exhausted sets of bits, the next following number would be, one 1 at next least significant bit with all trailing zero’s. Hence, just one 1. To understand the other way round, for all numbers, which are a power of 2, the next decremented number would be all 1’s following least significant bits. As in,
Code:
00000001 > 00000010
00000011 > 00000100
00000111 > 00001000
Therefore, ANDing a number x with one lesser, i.e. (x1), if that results in a zero, that means the number is a power of 2. This solution looks quite efficient and elegant as well.
Programmatically,
Code:
if (x & (x1))
{
printf(“The number is not a power of two\n”);
}
else
{
printf(“The number is a power of two\n”);
}
Determine if integer is odd or even
Most of the efficient bit manipulation algorithms comes through observing the binary representation patterns. Lets do the same here. Lets observe the binary pattern for odds and even numbers. First the even numbers:
Code:
00000000
00000010
00000100
00000110
00001000
00001010
00001100
00001110
Lets write down the first few odd numbers in binary. First the even numbers:
Code:
00000001
00000011
00000101
00000111
00001001
00001011
00001101
00001111
Did you note? Yes, for even numbers, it always ends with a 0, while an odd number always ends with a 1. To determine, the ending bit is 1 or 0, we just need to AND our number with the number 1, and if it results with a 1, that means it was an odd. However, if ANDing with 1 results in zero, then it means the ending bit of the number was 0, and hence it is an even number.
For example. Lets take any even number of 1 byte. We are keeping first 7 bits as ‘x’ that is as don’t care. The ending bit i.e. the least significant bit is 0.
Code:
xxxxxxx0
&
0000001

00000000

Now, lets confirm our solution algorithm with an odd number of 1 byte. Again, we’ll keep most significant 7 bits as ‘x’ i.e. don’t care, and the least significant bit as 1.
Code:
xxxxxxx1
&
0000001

00000001

The solution code would look like
Code:
if (num & 1)
{
printf(“The number is ODD\n”);
}
else
{
printf(“The number is EVEN\n”);
}
Set/Unset kth Bit
To set a bit, we just need to OR it with 1, and to unset a bit, we can AND it with 0. What about in a 1byte or 4byte number, we want to set/unset the kth bit. We need to compute the operand with which we need to OR or AND the number.
Here is a way to do that.
To set the 3rd bit, lets take our number with all bits as don’t care except 3rd
Code:
x x x x x 0 x x x

0 0 00 0 1 0 0 0

x x x x x 1 x x x

Now, to unset the 3rd bit, lets take our number with all bits as don’t care except 3rd
Code:
x x x x x 1 x x x
&
1 1 11 1 0 1 1 1

x x x x x 0 x x x

In a program, it looks like, To set the kth bit,
Code:
res = num  (1<<k);
To unset the kth bit,
Code:
res = num & ~(1<<k)