Jak mnożyć i dzielić używając tylko bitowego przesuwania i dodawania?

Odpowiedź Andrzeja Tuluzy można rozszerzyć na podział.

Pierwszym pomysłem implementacji podziału jest zapis odwrotnej wartości mianownika w bazie drugiej.

Np., 1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....

Więc, a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30) dla arytmetyki 32-bitowej.

Poprzez połączenie terminów w oczywisty sposób możemy zmniejszyć liczbę operacje:

b = (a >> 2) + (a >> 4)

b += (b >> 4)

b += (b >> 8)

b += (b >> 16)

Są bardziej ekscytujące sposoby obliczania podziału i resztek.

EDIT1:

Jeśli OP oznacza mnożenie i dzielenie dowolnych liczb, a nie dzielenie przez stałą liczbę, to ten wątek może być użyteczny: https://stackoverflow.com/a/12699549/1182653

EDIT2:

Jednym z najszybszych sposobów dzielenia przez stałe całkowite jest wykorzystanie modularnego arytmetyka i redukcja Montgomery 'ego: jaki jest najszybszy sposób na podzielenie liczby całkowitej przez 3?

X * 2 = 1 bit shift left
X / 2 = 1 bit przesunięcie w prawo
X * 3 = shift w lewo 1 bit, a następnie dodaj X

x << k == x multiplied by 2 to the power of k
x >> k == x divided by 2 to the power of k

Możesz użyć tych przesunięć, aby wykonać dowolną operację mnożenia. Na przykład:

x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)

Aby podzielić liczbę przez nie-potęgę dwóch, nie znam łatwego sposobu, chyba że chcesz zaimplementować jakąś logikę niskiego poziomu, użyć innych operacji binarnych i użyć jakiejś formy iteracji.

1. przesunięcie w lewo o 1 pozycję jest analogiczne do pomnożenia przez 2. Przesunięcie w prawo jest analogiczne do dzielenia przez 2.
2. możesz dodać w pętli, aby pomnożyć. Wybierając zmienną pętli i zmienną dodawania poprawnie, można powiązać wydajność. Po zbadaniu tego powinieneś użyć mnożenia

Przetłumaczyłem Kod Pythona na C. podany przykład miał drobną wadę. Jeśli wartość dywidendy, która zajęła wszystkie 32 bity, zmiana nie powiedzie się. Po prostu użyłem 64-bitowych zmiennych wewnętrznie, aby obejść problem:

int No_divide(int nDivisor, int nDividend, int *nRemainder)
{
    int nQuotient = 0;
    int nPos = -1;
    unsigned long long ullDivisor = nDivisor;
    unsigned long long ullDividend = nDividend;

    while (ullDivisor <  ullDividend)
    {
        ullDivisor <<= 1;
        nPos ++;
    }

    ullDivisor >>= 1;

    while (nPos > -1)
    {
        if (ullDividend >= ullDivisor)
        {
            nQuotient += (1 << nPos);
            ullDividend -= ullDivisor;
        }

        ullDivisor >>= 1;
        nPos -= 1;
    }

    *nRemainder = (int) ullDividend;

    return nQuotient;
}

Weź dwie liczby, powiedzmy 9 i 10, zapisz je jako binarne - 1001 i 1010.

Zacznij od wyniku, R, z 0.

Weź jedną z liczb, 1010 w tym przypadku, nazwiemy ją A, i przesuń ją w prawo o jeden bit, jeśli przesuniesz jeden, dodaj pierwszą liczbę, nazwiemy ją B, do R.

Teraz przesuń B w lewo o jeden bit i powtarzaj, aż wszystkie bity zostaną przesunięte z A.

Łatwiej jest zobaczyć, co się dzieje, jeśli widzisz to wypisane, oto przykład:

      0
   0000      0
  10010      1
 000000      0
1001000      1
 ------
1011010

Procedura dzielenia liczb całkowitych, która wykorzystuje przesunięcia i dodawania, może być wyprowadzona w prosty sposób z podziału dziesiętnego, jak uczy się w szkole podstawowej. Wybór każdej cyfry ilorazu jest uproszczony, ponieważ cyfra wynosi 0 i 1: jeśli reszta prądu jest większa lub równa dzielnikowi, najmniej znaczącym bitem ilorazu częściowego jest 1.

Podobnie jak w przypadku podziału dziesiętnego, cyfry dywidendy są uważane za najbardziej znaczące do najmniej znaczące, jedna cyfra na raz. Można to łatwo osiągnąć przez przesunięcie w lewo w podziale binarnym. Ponadto bity ilorazowe są zbierane przez przesunięcie w lewo obecnych bitów ilorazu o jedną pozycję, a następnie dodanie nowego bitu ilorazu.

W klasycznym układzie, te dwa przesunięcia lewe są połączone w przesunięcie lewe jednej pary rejestrów. Górna połowa trzyma bieżącą resztę, dolna połowa początkowa trzyma dywidendę. W związku z przeniesieniem dywidendy na pozostałą część rejestrowanie przez przesunięcie w lewo, nieużywane najmniej znaczące bity dolnej połowy są używane do gromadzenia bitów ilorazowych.

Poniżej znajduje się język asemblacji x86 i implementacje C tego algorytmu. Ten szczególny wariant podziału shift & add jest czasami określany jako wariant "no-performing", ponieważ odejmowanie dzielnika od bieżącej reszty nie jest wykonywane, chyba że reszta jest większa lub równa dzielnikowi. W C nie ma pojęcia flagi nośnej używanej przez Wersja montażowa w parach rejestru lewy shift. Zamiast tego, jest on emulowany, opierając się na obserwacji, że wynik dodawania modulo 2 ⁿ może być mniejszy, że albo dodawanie tylko wtedy, gdy było przeprowadzenie.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define USE_ASM 0

#if USE_ASM
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
    uint32_t quot;
    __asm {
        mov  eax, [dividend];// quot = dividend
        mov  ecx, [divisor]; // divisor
        mov  edx, 32;        // bits_left
        mov  ebx, 0;         // rem
    $div_loop:
        add  eax, eax;       // (rem:quot) << 1
        adc  ebx, ebx;       //  ...
        cmp  ebx, ecx;       // rem >= divisor ?
        jb  $quot_bit_is_0;  // if (rem < divisor)
    $quot_bit_is_1:          // 
        sub  ebx, ecx;       // rem = rem - divisor
        add  eax, 1;         // quot++
    $quot_bit_is_0:
        dec  edx;            // bits_left--
        jnz  $div_loop;      // while (bits_left)
        mov  [quot], eax;    // quot
    }            
    return quot;
}
#else
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
    uint32_t quot, rem, t;
    int bits_left = CHAR_BIT * sizeof (uint32_t);

    quot = dividend;
    rem = 0;
    do {
            // (rem:quot) << 1
            t = quot;
            quot = quot + quot;
            rem = rem + rem + (quot < t);

            if (rem >= divisor) {
                rem = rem - divisor;
                quot = quot + 1;
            }
            bits_left--;
    } while (bits_left);
    return quot;
}
#endif

Wzięte z Tutaj .

To jest tylko dla podziału:

int add(int a, int b) {
        int partialSum, carry;
        do {
            partialSum = a ^ b;
            carry = (a & b) << 1;
            a = partialSum;
            b = carry;
        } while (carry != 0);
        return partialSum;
}

int subtract(int a, int b) {
    return add(a, add(~b, 1));
}

int division(int dividend, int divisor) {
        boolean negative = false;
        if ((dividend & (1 << 31)) == (1 << 31)) { // Check for signed bit
            negative = !negative;
            dividend = add(~dividend, 1);  // Negation
        }
        if ((divisor & (1 << 31)) == (1 << 31)) {
            negative = !negative;
            divisor = add(~divisor, 1);  // Negation
        }
        int quotient = 0;
        long r;
        for (int i = 30; i >= 0; i = subtract(i, 1)) {
            r = (divisor << i);
           // Left shift divisor until it's smaller than dividend
            if (r < Integer.MAX_VALUE && r >= 0) { // Avoid cases where comparison between long and int doesn't make sense
                if (r <= dividend) { 
                    quotient |= (1 << i);    
                    dividend = subtract(dividend, (int) r);
                }
            }
        }
        if (negative) {
            quotient = add(~quotient, 1);
        }
        return quotient;
}

To powinno działać dla mnożenia:

.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

Poniższa metoda jest implementacją podziału binarnego, biorąc pod uwagę, że obie liczby są dodatnie. Jeśli odejmowanie jest problemem, możemy to zaimplementować również za pomocą operatorów binarnych.

Kod

-(int)binaryDivide:(int)numerator with:(int)denominator
{
    if (numerator == 0 || denominator == 1) {
        return numerator;
    }

    if (denominator == 0) {

        #ifdef DEBUG
            NSAssert(denominator==0, @"denominator should be greater then 0");
        #endif
        return INFINITY;
    }

    // if (numerator <0) {
    //     numerator = abs(numerator);
    // }

    int maxBitDenom = [self getMaxBit:denominator];
    int maxBitNumerator = [self getMaxBit:numerator];
    int msbNumber = [self getMSB:maxBitDenom ofNumber:numerator];

    int qoutient = 0;

    int subResult = 0;

    int remainingBits = maxBitNumerator-maxBitDenom;

    if (msbNumber >= denominator) {
        qoutient |=1;
        subResult = msbNumber - denominator;
    }
    else {
        subResult = msbNumber;
    }

    while (remainingBits > 0) {
        int msbBit = (numerator & (1 << (remainingBits-1)))>0?1:0;
        subResult = (subResult << 1) | msbBit;
        if(subResult >= denominator) {
            subResult = subResult - denominator;
            qoutient= (qoutient << 1) | 1;
        }
        else{
            qoutient = qoutient << 1;
        }
        remainingBits--;

    }
    return qoutient;
}

-(int)getMaxBit:(int)inputNumber
{
    int maxBit = 0;
    BOOL isMaxBitSet = NO;
    for (int i=0; i<sizeof(inputNumber)*8; i++) {
        if (inputNumber & (1<<i)) {
            maxBit = i;
            isMaxBitSet=YES;
        }
    }
    if (isMaxBitSet) {
        maxBit+=1;
    }
    return maxBit;
}


-(int)getMSB:(int)bits ofNumber:(int)number
{
    int numbeMaxBit = [self getMaxBit:number];
    return number >> (numbeMaxBit - bits);
}

Dla mnożenia:

-(int)multiplyNumber:(int)num1 withNumber:(int)num2
{
    int mulResult = 0;
    int ithBit;

    BOOL isNegativeSign = (num1<0 && num2>0) || (num1>0 && num2<0);
    num1 = abs(num1);
    num2 = abs(num2);


    for (int i=0; i<sizeof(num2)*8; i++)
    {
        ithBit =  num2 & (1<<i);
        if (ithBit>0) {
            mulResult += (num1 << i);
        }

    }

    if (isNegativeSign) {
        mulResult =  ((~mulResult)+1);
    }

    return mulResult;
}

Dla wszystkich zainteresowanych 16-bitowym rozwiązaniem x86 znajduje się fragment kodu JasonKnight tutaj1 (zawiera również podpisany fragment mnożenia, którego nie testowałem). Jednak ten kod ma problemy z dużymi wejściami, gdzie część" add bx,bx " przepełniłaby się.

Wersja stała:

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

Lub to samo w GCC inline assembly:

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"
);

Spróbuj tego. 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])