How to divide 16bit number by 2 in 6502 asm?

Question

I want to divide a 16bit number by two. My solution to the problem was as below

    lda $17 ;set high byte
    ldx $32    ;set low byte

divide:
    PHA         ;push A to stack        
    TXA         ;X > A  
    LSR         ;divide low byte by 2   
    TAX         ;A > X

    PLA         ;pull A from stack  
    LSR         ;divide high byte by 2
    BCC +       ;C=0, skip

    PHA         ;while C=1
    TXA         ;add $80 to the lsb
    ADC #$80
    TAX
    PLA 
+   
    +printDecimal $0400+120

All PHA/PLA trickery is because my printDecimal macro reads MSB from A and LSB from X.

When I check alternatives online, I found 4 instruction alternative to my humble division routine. But I didn't understand.

div2:
    LDA counter_hi       ;Load the MSB
    ASL                  ;Copy the sign bit into C
    ROR counter_hi       ;And back into the MSB
    ROR counter_lo       ;Rotate the LSB as normal

    LDA counter_hi
    LDX counter_lo      
    +printDecimal $0400+40    

How this works?

Answer 1

Division by 2 (of an unsigned number) is the same as shifting all bits one position to the right. For example, the number 100 is represented in binary by:

01100100

Moving all positions one to the right yields

00110010

which is the binary representation of 50.

The ROR command moves all positions to the right. The new MSB of the byte will be equal to the old value of the carry flag, while the new value of the carry flag will be equal to the old LSB of the byte.

If the the 16-bit number is unsigned, it is sufficient to shift the high and the low byte of the number to the right:

LSR counter_hi
ROR counter_lo

LSR and ROR both shift their argument to the right, but LSR makes the MSB of counter_hi 0 and shifts the LSB of counter_hi into the carry flag, while ROR makes the MSB of counter_lo equal to the (old) LSB of counter_hi.

If the number is signed, you need to store the sign bit and make sure that the sign bit of the new number is the same. That is what the first two commands of the code you quoted do. Note that this works because the number is stored in two's complement.

Answer 2

(Obviously you know shifting right by N bits divides by 2^N, and similarly left shifting multiplies by 2)

From this reference:

ASL puts the Most Significant Bit (MSB) of the hi byte counter_hi into the Carry Register (so that the sign is remembered when we shift - Division by a positive integer (2) won't change the original sign of our 16 bit number).

ROR counter_hi shifts the counter_hi by 1 bit to the right. Importantly:

The Carry is shifted into bit 7 and the original bit 0 is shifted into the Carry.

which serves two purposes - keeping the original sign, and also will transfer the LSB of counter_hi for the second ROR

ROR counter_lo then does the same for the low byte. The LSB of the counter_hi is now shifted into the MSB of counter_lo

Answer 3

Don't remember all addressing modes of instructions but maybe this is OK:

LSR
PHA
TXA
ROR
TAX
PLA

Answer 4

If I remember correctly, the ROR and ROL shift the bits in the direction stated and the least significant bit (for ROR) and most significant (for ROL) are moved into the Carry flag.

It's about 25 years since I looked at any 6502, though so it isn't all very clear to me, but that's immediately how I thought it would be done.

Edit: Also, in ROR and ROL, the existing state of the carry flag is transferred into the least/most significant bit of the accumulator.

Answer 5

It works as the comments in the code say ;) In 6502 there is unfortunately no arithmetic shift right, which would leave the sign bit intact. So it needs to be emulated. For this, first the sign bit is extracted from the high word. Notice this is done using the accumulator, so the original value is not changed. The ROR is used on the high word, which rotates the 9 bit value made from extending the operand with the carry flag. As such, the sign bit which is currently in CF will be rotated into the MSB, the rest of the bits will be shifted right and the LSB will end up in the CF. This accomplished a signed division. The second ROR on the low word simply transfers the LSB from the high word into the MSB of the low word, and shifts the rest of the bits right.