Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Working with Bitwise Operators (http://www.go4expert.com/articles/bitwise-operators-t29233/)

Trinity 29Oct2012 17:40

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:

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, 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:

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 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)

grizlizli 4Jan2013 23:46

Re: Working with Bitwise Operators
 
Nice one...

Can you tell me where I may use bitwise operators except for multiplication/division by power of 2 or determining if integer is odd or even?
I mean in real life situation...

iranjit 5Jan2013 17:29

Re: Working with Bitwise Operators
 
I have only used bit-wise operators in programming of embedded system.

Trinity 6Jan2013 04:07

Re: Working with Bitwise Operators
 
Thanks.

Well, bitwise operations are the like blood in embedded programming, as one needs to account for every bit stored. Even in video/audio parsing, where raw data is being parsed and decoded, bitwise operations are of great help.
Hope that helps.

grizlizli 6Jan2013 18:20

Re: Working with Bitwise Operators
 
All right.

I have learn it in college but no one told us what's the use of bitwise operators in praxis.
Now I can get the idea. Thanks.

P.S. I would appreciate it if someone else shared his experience.


All times are GMT +5.5. The time now is 08:12.