Shifting a double-wide variable - bit twiddling

[CRGreathouse]

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

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.

 

[out of whack]

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;

 

[CRGreathouse]

Ooh, thanks. That does help.