Thread: Bit Shifting

    #1
  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. #2
  3. No Profile Picture
    Lost in code
    Devshed Supreme Being (6500+ posts)

    Join Date
    Dec 2004
    Posts
    8,300
    Rep Power
    7170
    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.
    PHP FAQ

    Originally Posted by Spad
    Ah USB, the only rectangular connector where you have to make 3 attempts before you get it the right way around
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2005
    Location
    Bay Area, California
    Posts
    841
    Rep Power
    1681
    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.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2008
    Posts
    9
    Rep Power
    0
    Thank you for the explanations.
  8. #5
  9. 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.

IMN logo majestic logo threadwatch logo seochat tools logo