Как я могу умножить и разделить, используя только сдвиг и добавление битов?

Question

Как я могу умножить и разделить, используя только сдвиг и добавление битов?

Answer 1

Это должно работать для умножения:

.data

.text
.globl  main

main:

# $4 * $5 = $2

    addi $4, $0, 0x9
    addi $5, $0, 0x6

    add  $2, $0, $0 # initialize product to zero

Loop:   
    beq  $5, $0, Exit # if multiplier is 0,terminate loop
    andi $3, $5, 1 # mask out the 0th bit in multiplier
    beq  $3, $0, Shift # if the bit is 0, skip add
    addu $2, $2, $4 # add (shifted) multiplicand to product

Shift: 
    sll $4, $4, 1 # shift up the multiplicand 1 bit
    srl $5, $5, 1 # shift down the multiplier 1 bit
    j Loop # go for next  

Exit: #


EXIT: 
li $v0,10
syscall

Answer 2

Для тех, кто заинтересован в 16-битном x86-решении, здесь есть фрагмент кода JasonKnight здесь 1 (он также включает в себя фрагмент с умножением со знаком, которого у меня нет испытано). Однако в этом коде есть проблемы с большими входами, когда часть «add bx, bx» будет переполнена.

Фиксированная версия:

softwareMultiply:
;    INPUT  CX,BX
;   OUTPUT  DX:AX - 32 bits
; CLOBBERS  BX,CX,DI
    xor   ax,ax     ; cheap way to zero a reg
    mov   dx,ax     ; 1 clock faster than xor
    mov   di,cx
    or    di,bx     ; cheap way to test for zero on both regs
    jz    @done
    mov   di,ax     ; DI used for reg,reg adc
@loop:
    shr   cx,1      ; divide by two, bottom bit moved to carry flag
    jnc   @skipAddToResult
    add   ax,bx
    adc   dx,di     ; reg,reg is faster than reg,imm16
@skipAddToResult:
    add   bx,bx     ; faster than shift or mul
    adc   di,di
    or    cx,cx     ; fast zero check
    jnz   @loop
@done:
    ret

Или то же самое для встроенной сборки GCC:

asm("mov $0,%%ax\n\t"
    "mov $0,%%dx\n\t"
    "mov %%cx,%%di\n\t"
    "or %%bx,%%di\n\t"
    "jz done\n\t"
    "mov %%ax,%%di\n\t"
    "loop:\n\t"
    "shr $1,%%cx\n\t"
    "jnc skipAddToResult\n\t"
    "add %%bx,%%ax\n\t"
    "adc %%di,%%dx\n\t"
    "skipAddToResult:\n\t"
    "add %%bx,%%bx\n\t"
    "adc %%di,%%di\n\t"
    "or %%cx,%%cx\n\t"
    "jnz loop\n\t"
    "done:\n\t"
    : "=d" (dx), "=a" (ax)
    : "b" (bx), "c" (cx)
    : "ecx", "edi"
);

Answer 3

Попробуй это. https://gist.github.com/swguru/5219592

import sys
# implement divide operation without using built-in divide operator
def divAndMod_slow(y,x, debug=0):
    r = 0
    while y >= x:
            r += 1
            y -= x
    return r,y 


# implement divide operation without using built-in divide operator
def divAndMod(y,x, debug=0):

    ## find the highest position of positive bit of the ratio
    pos = -1
    while y >= x:
            pos += 1
            x <<= 1
    x >>= 1
    if debug: print "y=%d, x=%d, pos=%d" % (y,x,pos)

    if pos == -1:
            return 0, y

    r = 0
    while pos >= 0:
            if y >= x:
                    r += (1 << pos)                        
                    y -= x                
            if debug: print "y=%d, x=%d, r=%d, pos=%d" % (y,x,r,pos)

            x >>= 1
            pos -= 1

    return r, y


if __name__ =="__main__":
    if len(sys.argv) == 3:
        y = int(sys.argv[1])
        x = int(sys.argv[2])
     else:
            y = 313271356
            x = 7

print "=== Slow Version ...."
res = divAndMod_slow( y, x)
print "%d = %d * %d + %d" % (y, x, res[0], res[1])

print "=== Fast Version ...."
res = divAndMod( y, x, debug=1)
print "%d = %d * %d + %d" % (y, x, res[0], res[1])