October 5th, 2010, 04:11 PM
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?
October 5th, 2010, 05:50 PM
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.
October 5th, 2010, 09:19 PM
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).
Core design principles
when developing software systems.
See my open-source project
as an example of professional code.
The opinions expressed do not represent those of my employer.
October 11th, 2010, 01:30 AM
Thank you for the explanations.
November 9th, 2010, 11:51 PM
Bit shifting basically use sign representation and to store large value in small size register.