1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Shifting a double-wide variable - bit twiddling

  1. Oct 26, 2007 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Shifting a double-wide variable -- bit twiddling

    I have a number too long to fit into the largest variable size (unsigned long long, 64 bits in this case) so I'm storing it in two variables, left and right. I want to shift it -- and to do it quickly, as I'll do this more than 1e12 times.

    The 'obvious' way is

    Code (Text):
    unsigned long long right, left;

    . . .

    right = ((left&3) << 62) + (right >> 2);
    left >>= 2;
    for a total of 5 operations and two assignments. This example is a right shift of 2, but right shifts by 1 and 4 are also important. In any case the size of the shift should be known at compile time.

    1. Is a shift of 62 too large to be done efficiently? I know that older processors used to take O(n) time to shift n places (something like 3+n micro-ops), but I don't know if this holds on modern processors. Perhaps I should make a switch statement with constant to add (1 << 62, 2 << 62, and 3 << 62 precomputed)? Or would the branch misprediction outweigh this?
    2. Is there a way to do this with fewer operations? I'm sure there are some people out there who have been doing bit manipulations far longer than I have.

    For what it's worth I'm on a Core Duo, but I'm hoping for improvements to my program that work on most systems.
     
  2. jcsd
  3. Oct 26, 2007 #2
    You can replace "(left&3)" with just "left" since the bit mask operation is redundant given the left shift. It cuts your cost down to 4 operations.

    I would also replace the "+" operator with a bitwise OR instead. You are not adding values but combining bits. It may not actually save any execution time, but a "|" is simpler than a "+" operation so there is a remote chance that it is faster on some systems.

    right >>= 2;
    right |= left << 62;
    left >>= 2;
     
  4. Oct 26, 2007 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Ooh, thanks. That does help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Shifting a double-wide variable - bit twiddling
  1. Phase shift using FFT (Replies: 0)

  2. Global variables. (Replies: 7)

Loading...