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

#### Petra93

• Regular Member
• Posts: 12
##### 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: 10260
• Assembler is fun ;-)
##### 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

#### FORTRANS

• Member
• Posts: 1070
##### 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: 1382
##### 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, 1RCR 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: 8825
• Still using Abacus 2.0
##### 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

« Last Edit: September 17, 2015, 12:19:37 PM by dedndave »

#### rrr314159

• Member
• Posts: 1382
##### 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: 8825
• Still using Abacus 2.0
##### 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: 1382
##### 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: 12
##### 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: 1070
##### 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: 1925
##### 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 retI63: mov eax,edx sar edx,31 and cl,31 sar eax,cl retSIGN: 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 retI31: mov ax,dx sar dx,15 and cl,15 sar ax,cl retSIGN: sar dx,15 mov ax,dx ret`