Division by 2 using SHR

[Petra93]

I am writing a program where it is necessary to divide a large number by 2. The number is represented by two words, wordhi and wordlo.  I would like to use the SHR instruction for both words. The LSB of the high word will appear in the carry bit, but I don't know how to move the carry bit into the MSB of the low word. Can someone help me out?

[jj2007]

First things first: Welcome to the forum :icon14:

Your request is not very clear, an example would be nice. How is that "large" number composed? Words can hold 0...65535, that is not large. So you probably mean a dword - and that can be divided in one go by, for example, sar eax, 1

So what is your number, and what is your expected result?

[FORTRANS]

Hi,

   Using SHR on both words would be tedious.  As you noted there
is no easy way to manipulate the carry bit directly with SHR.  You
could test the low bit of the high word, and set the high bit of the
low word with an OR 01000H if it was set in the high word.  What
you probably want to use is the Rotate through Carry, Right
instruction: RCR.  You would shift the high word by one, and then
use RCR by one on the low word.

HTH,

Steve N.

Edit:  AND => OR to set bit.  Use AND or TEST to test low bit in the
high word, OR to set high bit (if needed) in low word.

SRN

[KeepingRealBusy]

What about SHRD - two registers treated as one for the shift.

Dave.

[rrr314159]

Hi Petra93,

@jj2007, presumably he does mean "words" not dwords since this is the 16-bit forum.

@FORTRANS, that looks like the best suggestion except for one thing, presumably Petra93 might have to divide negative number. So use SAR on high word then RCR on low word

@KeepingRealBusy, SHRD also works: first "SHRD wordlo, wordhi, 1" then SAR "wordhi, 1". However glancing at the timings, it appears RCR is faster. Perhaps that should be tested. The other good thing about SHRD, it would work for dividing by higher powers of 2 also

@Petra93, this appears best:

Code Select Expand

SAR wordhi, 1
RCR wordlo, 1

But another suggestion, since you need to deal with large (32-bit) numbers, would be easier to use 32-bit code

[dedndave]

if the large integer is signed...

Code Select Expand

    SAR     HighWord,1
    RCR     LowWord,1

if the large integer is not signed...

Code Select Expand

    SHR     HighWord,1
    RCR     LowWord,1

RCR = Rotate through Carry Right
SAR = Shift Arithmetic Right
SHR = SHift Right
if multiplying, it would be left - SHL is used for both (there is no special SAL instruction)

it's generally faster if the operands (HighWord and LowWord) are in registers, often DX and AX

edit: added shift counts

[rrr314159]

@dedndave,

you left out the count, ", 1" in your code

[dedndave]

thanks

i see that KeepingRealBusy mentioned SHRD (SHift Right Double)
that might be used if the shift count were greater than 1

Code Select Expand


        shrd    ax,dx,2               ;shift low word first
        shr     dx,2                  ;then shift high word

it also supports a variable shift count in CL
and, it can be used to chain more than just 2 registers
SHLD is similar for shifting left

[rrr314159]

that's right, I hadn't even noticed SHRD, could be useful, but for dividing by 2 appears to be slower than SAR / RCR or SHR / RCR

[Petra93]

Thank you so much for all the suggestions.  I like the RCR approach offered by FORTRANS, and will try it
right away.  (I am working through the problems at the Euler Project; this is related to Problem 14.)

[FORTRANS]

Hi,

   Fixed the dumb error in my earlier post.

@FORTRANS, that looks like the best suggestion except for one thing, presumably Petra93 might have to divide negative number. So use SAR on high word then RCR on low word

   True.  SHR was mentioned, so I assumed unsigned.  But noticing
the possibility of a signed operation is good practice.  However, in
my experience, multi-byte/word/double word arithmetic is almost
always unsigned.  Using a sign and magnitude representation is easier
than mucking about with signed quantities for multiply and divide.

Regards,

Steve

[nidud]

deleted