1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2008
Posts
9
Rep Power
0

#### Bit Shifting

In computer architecture, why do we shift bits? More specifically, why do shift the bits in registers?

Is it so we can store multiple numbers for different purposes in the same register, and then just shift the bits around to get/put a number?
2. No Profile Picture
Lost in code
Devshed Supreme Being (6500+ posts)

Join Date
Dec 2004
Posts
8,304
Rep Power
7174
In computer architecture, why do we shift bits? More specifically, why do shift the bits in registers?
Because shifting bits is fast as hell, especially when the bits are (already) stored in a register.

Left shifting is equivalent to multiplying by 2, that's the most prominent arithmetic use of bit shifting.

It's also a very fast way of extracting a portion of a word. Wrapping multiple pieces of data into a single word is more efficient both space-wise and speed-wise if the data is less than one word. Space-wise it's more efficient because you don't have to waste the extra storage space for the unused bits of the word, and speed-wise because you can load multiple pieces of data using a single load instruction rather than having to issue a load instruction for each piece of data.

Unless you're programming in assembly I don't recommend storing multiple pieces of data in a single variable though. Even if you're programming in assembly, I don't recommend doing it unless you have to.
3. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
Jul 2005
Location
Bay Area, California
Posts
841
Rep Power
1685
Its fast. Really, really, really fast. By understanding how to use binary effectively you can solve problems extremely quickly. Lets take a few examples.

First, a recent Java forum question was how to calculate the power of two greater than the given number. The general advise was to use either an O(n) loop to calculate all powers until found, or to use log2 arithmetic. A simpler and fast answer is to take advantage of the binary representation. After finding the highest 1 bit, a left shift's property of being a multiple of two was used to find the next power.

Another simple example is to generate a powerset. An easy implementation is to use a bit per element and an integer as a counter. For each permutation, increment the counter and evaluate each bit field to determine membership in the output set. The shift operator is used to create the bit mask to zero out all of the other bit fields.

This use as a bit mask has a lot of power. For example, a bloom filter is a very compact data structure that provides a probabilistic Set. It uses a bit-vector and multiple hashing functions to set bit fields. Membership is determined by seeing if an element's bit indices are set. This allows not storing the actual element itself at the cost of false positives. It is therefore a "filter" because it allows us to remove the negative cases, thereby reducing how often we perform an expensive operation (e.g. I/O call).
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2008
Posts
9
Rep Power
0
Thank you for the explanations.
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2010
Location
Southampton PA
Posts
14
Rep Power
0

#### Bit Shifting

Bit shifting basically use sign representation and to store large value in small size register.