Bit Manipulation (Overview)
“What? That title isn’t a question like you promised.” – Yep, it isn’t. I just wanted to give a short introduction of Bit Manipulation so that it might be easier for you to understand the term when I have used it in the future. An application of bit manipulation was already shown in the previous post (Find the only element in array which does not have a duplicate).
So if you don’t know it yet, all bit manipulation is about is playing around with bits to get the desired result. The most used operators for such manipulations are  (bitwise OR), & (bitwise AND), ^ (XOR), >> (right shift), << (left shift).
Hopefully, everyone will be familiar with the operation of the first 3 operators. I’ll just explain the way shift operators function.
2<<3 would give you 16. Why? In binary 2=10, shifting it right by 3 bits, we get 10000 which equals 16. Simple as that. So right shift multiplies your number by 2 raised to the number of bits you shift.
On the other hand. 16>>3 gives two. The logic is exactly opposite to the one for right shit. Thus, left shift ends up dividing a number by 2 raised to the number of bits you shift. Easypeasy!
You will be amazed to see the applications of such bitmanipulations to problems. Some problems are rendered so easy with the use of these operators that it would almost make you laugh. Other problems (like finding ‘a*7’ for a given ‘a’ without using *,/,+) necessarily require the use of bit manipulations. We will soon discuss more applications where bit manipulations make your life easier. 🙂
PS: The solution for the question in bold is –
b=a<<3; print ba; //in essence, multiplying number by 8 and then subtracting it once from the result of the shifting 😉
More cool stuff follows soon.

October 14, 2011 at 7:25 pmCounting number of valid zeros in binary representation of a number « All About Algorithms