How to implement shifts?

[Tord Romstad]

Hello,

Unfortunately, my compiler (GCC) doesn't seem to support 96-bit or 128-bit ints, so I have to roll my own. My current problem is that I can't find a way to implement left or right shifts efficiently. How is it done?

Tord

[sje]

Run gcc on a strictly 32 bit system and see how it generates 64 bit integer shifts. Use analogical reasoning to extend the generated assembly language to handle 128 bit shifts on a 64 bit system.

[Tord Romstad]

Run gcc on a strictly 32 bit system and see how it generates 64 bit integer shifts.

That's what I hoped to avoid. There are few things I hate more than trying to read assembly language.

Use analogical reasoning to extend the generated assembly language to handle 128 bit shifts on a 64 bit system.

Actually, I use a 32 bit system, but that probably doesn't make any difference for the algorithm.

Tord

[CRoberson]

Here goes a top of my head manual effort.

You have two locations Hi and Lo each are 64 bit.
You want to shift left B bits which means carry over the
leftmost B bits in Lo to the lower B bits in Hi. I am assuming
both Hi and Lo are unsigned.

Code: Select all

      int B;
      unsigned long long upperbits, Hi, Lo;
      upperbits = -1; // fill upperbits with 1s
      upperbits = upperbits << &#40;64 - B&#41;; // creates mask for upper bits
      upperbits = Lo & upperbits; // save the upperbits of Lo
      Lo = Lo << B;
      Hi = &#40;Hi << B&#41; | &#40;upperbits >> &#40;64-B&#41;);

Shift right could be implement similarly.

[Karlo Bala]

Here goes a top of my head manual effort.

You have two locations Hi and Lo each are 64 bit.
You want to shift left B bits which means carry over the
leftmost B bits in Lo to the lower B bits in Hi. I am assuming
both Hi and Lo are unsigned.

Code: Select all

      int B;
      unsigned long long upperbits, Hi, Lo;
      upperbits = -1; // fill upperbits with 1s
      upperbits = upperbits << &#40;64 - B&#41;; // creates mask for upper bits
      upperbits = Lo & upperbits; // save the upperbits of Lo
      Lo = Lo << B;
      Hi = &#40;Hi << B&#41; | &#40;upperbits >> &#40;64-B&#41;);

Shift right could be implement similarly.

I dont know if my implementation is correct but look nice

Code: Select all

      int B;
      unsigned long long Hi, Lo;
      Hi = &#40;Hi << B&#41; | &#40;Lo >> &#40;64-B&#41;);
      Lo = Lo << B;

[Tord Romstad]

Charles and Karlo,

Thanks for your replies! Both solutions look rather more expensive than I would like (several shifts, a subtraction, a binary OR), but perhaps there is nothing better. At least I haven't been able to find something better myself yet.

Tord

[friedeks]

"Hackers delight" has some examples of multi-word shifts.

Here is a sample implementation of mine:

Code: Select all

/**
 * 128 Bit Integer
 */
public class XLong {
  long hi;
  long lo;

  void shiftLeft(int n){
    long yhi = &#40;hi << n&#41; | &#40;lo >>> &#40;64 - n&#41;) | &#40;lo << &#40;n - 64&#41;);
    long ylo = lo << n;

    hi = yhi;
    lo = ylo;
  &#125;

  void shiftRightUnsigned&#40;int n&#41;&#123;
    long ylo = &#40;lo >>> n&#41; | &#40;hi << &#40;64 - n&#41;) | &#40;hi >>> &#40;n - 64&#41;);
    long yhi = hi >>> n;

    hi = yhi;
    lo = ylo;
  &#125;

  void shiftRightSigned&#40;int n&#41;&#123;
    long ylo;
    if&#40;n < 64&#41;&#123;
      ylo = &#40;lo >>> n&#41; | &#40;hi << &#40;64 - n&#41;);
    &#125;else&#123;
      ylo = hi >> &#40;n - 64&#41;;
    &#125;
    long yhi = hi >> n;

    hi = yhi;
    lo = ylo;
  &#125;

&#125;

The book contains a branchless version of the singed shift as well if your interested.

[Dann Corbit]

Hello,

Unfortunately, my compiler (GCC) doesn't seem to support 96-bit or 128-bit ints, so I have to roll my own. My current problem is that I can't find a way to implement left or right shifts efficiently. How is it done?

Tord

In assembly, it's ASL/ASR combined with ROL (arithemetic shift left/right, then roll over of the carry bit)

Maybe something like this can be helpful:

#define UINT_BIT (sizeof (unsigned) * CHAR_BIT)

unsigned rollWithCarryRight(unsigned value, unsigned *carryFlag)
{
unsigned carryFlagContents = *carryFlag;
*carryFlag = value & 1;
return (value >> 1) || (carryFlagContents << (UINT_BIT - 1));
}

Obviously, the same idea scales to any unsigned integer size.

[Dann Corbit]

Here is the MS VC++ code for shifting right and left 64 bit integers using 32 bit integers. In assembly, of course.

;***
;llshl - long shift left
;
;Purpose:
; Does a Long Shift Left (signed and unsigned are identical)
; Shifts a long left any number of bits.
;
;Entry:
; EDX:EAX - long value to be shifted
; CL - number of bits to shift by
;
;Exit:
; EDX:EAX - shifted value
;
;Uses:
; CL is destroyed.
;
;Exceptions:
;
;*******************************************************************************

CODESEG

_allshl PROC NEAR

;
; Handle shifts of 64 or more bits (all get 0)
;
cmp cl, 64
jae short RETZERO

;
; Handle shifts of between 0 and 31 bits
;
cmp cl, 32
jae short MORE32
shld edx,eax,cl
shl eax,cl
ret

;
; Handle shifts of between 32 and 63 bits
;
MORE32:
mov edx,eax
xor eax,eax
and cl,31
shl edx,cl
ret

;
; return 0 in edx:eax
;
RETZERO:
xor eax,eax
xor edx,edx
ret


;***
;ullshr - long shift right
;
;Purpose:
; Does a unsigned Long Shift Right
; Shifts a long right any number of bits.
;
;Entry:
; EDX:EAX - long value to be shifted
; CL - number of bits to shift by
;
;Exit:
; EDX:EAX - shifted value
;
;Uses:
; CL is destroyed.
;
;Exceptions:
;
;*******************************************************************************

CODESEG

_aullshr PROC NEAR

;
; Handle shifts of 64 bits or more (if shifting 64 bits or more, the result
; depends only on the high order bit of edx).
;
cmp cl,64
jae short RETZERO

;
; Handle shifts of between 0 and 31 bits
;
cmp cl, 32
jae short MORE32
shrd eax,edx,cl
shr edx,cl
ret

;
; Handle shifts of between 32 and 63 bits
;
MORE32:
mov eax,edx
xor edx,edx
and cl,31
shr eax,cl
ret

;
; return 0 in edx:eax
;
RETZERO:
xor eax,eax
xor edx,edx
ret

[Dann Corbit]

Don't know if it will help in general, but there seems to be an intrinsic for 128 bit shifts on Apple computers:
http://developer.apple.com/documentatio ... ion_2.html

This looks useful:
http://www.math.sci.hiroshima-u.ac.jp/~ ... 062821.pdf

The Jikes compiler:
http://sourceforge.net/project/showfile ... _id=128803
has long.cpp and long.h which implement 64 bit integers in terms of 32 bit integers as a number class with overloaded operators. I guess that it would be a great model, as the results would be very convenient to use when doubled in size to 128 bits.