Bits - shifts/ manipulation/ tricks

Question

I have been trying to learn about bits and first place to learn about them is Wikipedia, so I read about it.

I have been preparing for the interviews where I see lot of questions which are solved with bit tricks/manipulations/shift

Few examples are

• if number is power of 2
• arithmetic operations without using arithmetic operators

There are also places where XOR is very useful. when is XOR useful?

I want to learn how can we apply such tricks in problem solving and what are the good signs when looking at the problem itself, one must say "it could be done with bits"

I worked mostly on Java/Python/Perl and hardly practiced them while writing code

But I want to learn it now .. better late than never :)

Answer 1

The ultimate source for this sort of thing is Bit Twiddling Hacks.

Answer 2

I would suggest first working on a solid understanding of when to use the different operations (not as a "trick" but as intended). This will help you understand the tricks better when you do come across them.

For XOR, consider you're writing a game and each character has a set of flags stored in a byte that describe their abilities (e.g. is_marksman, has_sword_training, etc. -- I know, I know, but it's an example, okay?). Now you have two characters who are about to fight each other, and you want to determine how they differ in abilities, because similar abilities will cancel each other out (I know, again, not the best example, but trying to keep it simple and illustrative). The quick way to do this would be to XOR their ability bytes.

A really fun "trick" with xor is in solving the Game of Nim

Answer 3

I recommend: http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know

Answer 4

I don't have a wider reference to bit tricks, but specifically in regards to your question about XOR:

XOR is useful, for example, when you want to tell if two bits are different (such as when a state changes, or comparing redundant inputs, say)

If you have binary numbers A = 101 and B = 011, A ^ B = 110 - thereby highlighting the bits that are different.

This leads to nifty tricks like exchanging two variables without needing any other memory:

A = 10100110
B = 01110100

A ^= B     ( A now is 11010010 )
B ^= A     ( B now is 10100110 )
A ^= B     ( A now is 01110100 )

As you can see, A and B switched!

In summary, bits are fun.

Answer 5

Outside of silly programming tricks (swap) that tend to obfiscate code, I use XOR in 3 places:

1. Flipping a bit on a state integer. Note, this is not a whole var with one state (a boolean), but an array of bool in an int if you will. And even here, there are better (boost) methods of handling this. This is rare.
2. When checking for Exclusive Or between 2 boolean values - Literally A or B, but not both. This is rare.
3. When coding in assembler. Even within assember, this is rare.

Did I mention that the need for xor/eor is extremely rare?