Author Topic: Division by 2 using SHR  (Read 3204 times)

Petra93

  • Regular Member
  • *
  • Posts: 5
Division by 2 using SHR
« on: September 17, 2015, 05:56:39 AM »
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

  • Member
  • *****
  • Posts: 7541
  • Assembler is fun ;-)
    • MasmBasic
Re: Division by 2 using SHR
« Reply #1 on: September 17, 2015, 06:12:18 AM »
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

  • Member
  • ****
  • Posts: 944
Re: Division by 2 using SHR
« Reply #2 on: September 17, 2015, 06:30:00 AM »
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
« Last Edit: September 17, 2015, 11:25:34 PM by FORTRANS »

KeepingRealBusy

  • Member
  • ***
  • Posts: 426
Re: Division by 2 using SHR
« Reply #3 on: September 17, 2015, 08:37:17 AM »
What about SHRD - two registers treated as one for the shift.

Dave.

rrr314159

  • Member
  • *****
  • Posts: 1381
Re: Division by 2 using SHR
« Reply #4 on: September 17, 2015, 09:20:21 AM »
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]
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
« Last Edit: September 17, 2015, 12:34:57 PM by rrr314159 »
I am NaN ;)

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: Division by 2 using SHR
« Reply #5 on: September 17, 2015, 10:21:36 AM »
if the large integer is signed...
Code: [Select]
    SAR     HighWord,1
    RCR     LowWord,1

if the large integer is not signed...
Code: [Select]
    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
« Last Edit: September 17, 2015, 12:19:37 PM by dedndave »

rrr314159

  • Member
  • *****
  • Posts: 1381
Re: Division by 2 using SHR
« Reply #6 on: September 17, 2015, 10:35:09 AM »
@dedndave,

you left out the count, ", 1" in your code
I am NaN ;)

dedndave

  • Member
  • *****
  • Posts: 8734
  • Still using Abacus 2.0
    • DednDave
Re: Division by 2 using SHR
« Reply #7 on: September 17, 2015, 12:25:51 PM »
thanks

i see that KeepingRealBusy mentioned SHRD (SHift Right Double)
that might be used if the shift count were greater than 1
Code: [Select]
        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

  • Member
  • *****
  • Posts: 1381
Re: Division by 2 using SHR
« Reply #8 on: September 17, 2015, 12:33:58 PM »
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
« Last Edit: September 18, 2015, 02:51:16 AM by rrr314159 »
I am NaN ;)

Petra93

  • Regular Member
  • *
  • Posts: 5
Re: Division by 2 using SHR
« Reply #9 on: September 17, 2015, 10:46:18 PM »
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

  • Member
  • ****
  • Posts: 944
Re: Division by 2 using SHR
« Reply #10 on: September 17, 2015, 11:37:00 PM »
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

  • Member
  • *****
  • Posts: 1370
    • https://github.com/nidud/asmc
Re: Division by 2 using SHR
« Reply #11 on: September 18, 2015, 12:10:32 AM »
Signed right shift for 64-bit using CL:
Code: [Select]
cmp cl,63
ja SIGN
cmp cl,31
ja I63
shrd eax,edx,cl
sar edx,cl
ret
I63:
mov eax,edx
sar edx,31
and cl,31
sar eax,cl
ret
SIGN:
sar edx,31
mov eax,edx
ret

Signed right shift for 32-bit should then be:
Code: [Select]
cmp cl,31
ja SIGN
cmp cl,15
ja I31
shrd ax,dx,cl
sar dx,cl
ret
I31:
mov ax,dx
sar dx,15
and cl,15
sar ax,cl
ret
SIGN:
sar dx,15
mov ax,dx
ret