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 1bit operands such that, only if both are 1, it results as 1, else it results as 0. For Example: Code:
101 & 110 = 100 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: Code:
101 & 110 = 111 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: Code:
101 & 110 = 011 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 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 The Not Operator is a one operand operator, which just toggles every bit of the nbits number. For Example: Code:
~(010) = 101 http://imgs.g4estatic.com/bitwiseop...le_bitwise.png Some common scenarios to use bitwise operatorsThere 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, 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 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 Code:
00000001 > 00000010 Programmatically, Code:
if (x & (x1)) 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 Code:
00000001 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 Code:
xxxxxxx1 Code:
if (num & 1) 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 Code:
x x x x x 1 x x x Code:
res = num  (1<<k); Code:
res = num & ~(1<<k) 
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... 
Re: Working with Bitwise Operators
I have only used bitwise operators in programming of embedded system.

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. 
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 01:11. 