Practical applications of bit shifting

Question

I totally understand how to shift bits. I've worked through numerous examples on paper and in code and don't need any help there.

I'm trying to come up with some real world examples of how bit shifting is used. Here are some examples I've been able to come up with:

• Perhaps the most important example I could conceptualize had to do with endianness. In big endian systems, least significant bits are stored from the left, and in little endian systems, least significant bits are stored from the right. I imagine that for files and networking transmissions between systems which use opposite endian strategies, certain conversions must be made.

• It seems certain optimizations could be made by compilers and processors when dealing with any multiplications that are n^2, n^4, etc. The bits are just being shifted to the left. (Conversly, I suppose the same would apply for division, n/2, n/4, etc.)

• In encryption algorithms. Ie using a series of bit shifts, reverses and combinations to obfuscate something.

Are all of these accurate examples? Is there anything you would add? I've spent quite a bit of time learning about how to implement bit shifting / reordering / byte swapping and I want to know how it can be practically applied = )

Answer 1

One common use is to use an int/long as a series of flag values, that can be checked, set, and cleared by bitwise operators.

Not really widely used, but in (some) chess games the board and moves are represented with 64 bit integer values (called bitboards) so evaluating legal moves, making moves, etc. is done with bitwise operators. Lots of explanations of this on the net, but this one seems like a pretty good explanation: http://www.frayn.net/beowulf/theory.html#bitboards.

And finally, you might find that you need to count the number of bits that are set in an int/long, in some technical interviews!

Answer 2

I would not agree that the most important example is endianness but it is useful. Your examples are valid.

Hash functions often use bitshifts as a way to get a chaotic behavior; not dissimilar to your cryptographic algorithms.

Answer 3

The most common example of bitwise shift usage I know is for setting and clearing bits.

uint8_t bla = INIT_VALUE;

bla |= (1U << N);   // Set N-th bit
bla &= ~(1U << N);  // Clear N-th bit

Answer 4

1. Quick multiplication and division by a power of 2 - Especially important in embedded applications
2. CRC computation - Handy for networks e.g. Ethernet
3. Mathematical calculations that requires very large numbers

Just a couple off the top of my head