Go4Expert - Working with Bitwise Operators

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 1-bit operands such that, only if both are 1, it results as 1, else it results as 0.

For Example:

Code:

101 & 110 = 100

OR (|) Operator

The OR Operator works on 1-bit operands such that, if any of the two is 1, it results as 1, else it results as 0.

For Example:

Code:

101 & 110 = 111

XOR (^) Operator

The XOR operator works on 1-bit 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:

Code:

101 & 110 = 011

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:

Code:

001<<1 = 010

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:

Code:

010>>1 = 001

Not (~) Operator

The Not Operator is a one operand operator, which just toggles every bit of the n-bits number.

For Example:

Code:

~(010) = 101

To summarize all the bitwise operators in a table:

http://imgs.g4estatic.com/bitwise-op...le_bitwise.png

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:

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, AND-ing a number x with one lesser, i.e. (x-1), 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 & (x-1))

{

    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:

Lets write down the first few odd numbers in binary. First the even numbers:

Code:

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 1-byte or 4-byte 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)