Jak mogę mnożyć i dzielić używając tylko przesunięcia bitowego i dodawania?

86

Jak mogę mnożyć i dzielić używając tylko przesunięcia bitowego i dodawania?

Spidfire
źródło
20
Tak jakbyś robił to na papierze w gimnazjum, używając tylko liczby dwójkowej zamiast dziesiętnej.
Pascal Cuoq
1
@mtk: Czego brakuje w tej odpowiedzi ? Szukasz implementacji C lub asemblera, konkretnych szerokości operandów, określonej metody podziału (np. Przywracanie vs nie przywracanie)?
njuffa
Czy odejmowanie jest prawidłowe? Wszystko wydaje się być pokryte
mksteve
Jaka jest potrzeba stojąca za tym pytaniem? Procesor już tłumaczy operacje mnożenia i dzielenia na przesunięcie bitów i dodawanie lub odejmowanie, a jeśli tak jest, to kompilator jeszcze tego nie zrobił.
Kelly S. French
@ KellyS.French Po prostu ciekawość, to raczej sposób na wyobrażenie sobie, jak kompilator może pracować z ograniczonym zestawem instrukcji.
Spidfire,

Odpowiedzi:

77

Aby pomnożyć w kategoriach dodawania i przesuwania, chcesz rozłożyć jedną z liczb potęgą dwójki, na przykład:

21 * 5 = 10101_2 * 101_2             (Initial step)
       = 10101_2 * (1 * 2^2  +  0 * 2^1  +  1 * 2^0)
       = 10101_2 * 2^2 + 10101_2 * 2^0 
       = 10101_2 << 2 + 10101_2 << 0 (Decomposed)
       = 10101_2 * 4 + 10101_2 * 1
       = 10101_2 * 5
       = 21 * 5                      (Same as initial expression)

( _2oznacza podstawę 2)

Jak widać, mnożenie można rozłożyć na dodawanie i przesuwanie iz powrotem. Dlatego też mnożenie trwa dłużej niż przesuwanie bitów lub dodawanie - w liczbie bitów jest to O (n ^ 2) zamiast O (n). Rzeczywiste systemy komputerowe (w przeciwieństwie do teoretycznych systemów komputerowych) mają skończoną liczbę bitów, więc mnożenie zajmuje stałą wielokrotność czasu w porównaniu z dodawaniem i przesuwaniem. Jeśli dobrze pamiętam, współczesne procesory, jeśli są poprawnie połączone potokowo, mogą wykonywać mnożenie prawie tak szybko, jak dodawanie, mieszając z wykorzystaniem jednostek ALU (jednostek arytmetycznych) w procesorze.

Andrew Toulouse
źródło
4
Wiem, że to było jakiś czas temu, ale czy możesz podać przykład z podziałem? Dzięki
GniruT,
42

Odpowiedź Andrew Toulouse można rozszerzyć na podział.

Dzielenie przez stałe całkowite jest szczegółowo omówione w książce „Hacker's Delight” autorstwa Henry'ego S. Warrena (ISBN 9780201914658).

Pierwszym pomysłem na zaimplementowanie dzielenia jest zapisanie odwrotnej wartości mianownika w podstawie dwa.

Na przykład, 1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....

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

Łącząc terminy w oczywisty sposób możemy zredukować liczbę operacji:

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

b += (b >> 4)

b += (b >> 8)

b += (b >> 16)

Istnieją bardziej ekscytujące sposoby obliczania dzielenia i reszty.

EDYCJA1:

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

EDYCJA2:

Jednym z najszybszych sposobów dzielenia przez stałe całkowite jest wykorzystanie arytmetyki modularnej i redukcji Montgomery'ego: Jaki jest najszybszy sposób podzielenia liczby całkowitej przez 3?

Viktor Latypov
źródło
Dziękuję bardzo za odniesienie do Hacker's Delight!
alecxe
2
Ehm tak, ta odpowiedź (dzielenie przez stałą) jest tylko częściowo poprawna. Jeśli spróbujesz zrobić „3/3”, otrzymasz 0. W Hacker's Delight wyjaśniają oni, że jest błąd, który musisz skompensować. W tym przypadku: b += r * 11 >> 5z r = a - q * 3. Link: hackersdelight.org/divcMore.pdf strona 2+.
atlaste
31

X * 2 = 1 bit przesuń w lewo
X / 2 = 1 bit przesuń w prawo
X * 3 = przesuń w lewo o 1 bit, a następnie dodaj X

Kelly S. French
źródło
4
Masz na myśli add Xten ostatni?
Mark Byers
1
Nadal jest źle - ostatnia linia powinna brzmieć: „X * 3 = przesuń w lewo o 1 bit, a następnie dodaj X”
Paul R
1
„X / 2 = 1 bit przesunięcie w prawo”, nie do końca, zaokrągla w dół do nieskończoności, a nie do 0 (dla liczb ujemnych), co jest zwykłą implementacją dzielenia (przynajmniej o ile widziałem).
Leif Andersen
25

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 potęgę dwóch, nie znam żadnego prostego sposobu, chyba że chcesz zaimplementować logikę niskiego poziomu, użyć innych operacji binarnych i użyć jakiejś formy iteracji.

IVlad
źródło
@IVlad: Jak połączyć powyższe operacje, aby wykonać, powiedzmy, podzielenie przez 3?
Paul R
@Paul R - prawda, to trudniejsze. Wyjaśniłem swoją odpowiedź.
IVlad
dzielenie przez stałą nie jest zbyt trudne (pomnóż przez magiczną stałą, a następnie podziel przez potęgę 2), ale dzielenie przez zmienną jest trochę trudniejsze.
Paul R
1
nie powinno x * 14 == x * 16 - x * 2 == (x << 4) - (x << 2) tak naprawdę kończy się na (x << 4) - (x << 1) ponieważ x < <1 mnoży się przez x przez 2?
Alex Spencer,
18
  1. Przesunięcie w lewo o 1 pozycję jest analogiczne do pomnożenia przez 2. Przesunięcie w prawo jest analogiczne do podzielenia przez 2.
  2. Możesz dodać pętlę, aby pomnożyć. Prawidłowo wybierając zmienną pętli i zmienną dodawania, można ograniczyć wydajność. Gdy już to zbadasz, powinieneś użyć Mnożenia chłopów
Yann Ramin
źródło
9
+1: Ale lewy shift nie tylko analogiczny do pomnożenia przez 2. To jest pomnożenie przez 2. Przynajmniej do momentu przelania ...
Don Roby
Dzielenie przez przesunięcie daje nieprawidłowe wyniki dla liczb ujemnych.
David,
6

Przetłumaczyłem kod Pythona na C. Podany przykład miał niewielką wadę. Jeśli wartość dywidendy, która zajęłaby wszystkie 32 bity, przesunięcie się nie powiedzie. Właśnie wewnętrznie użyłem 64-bitowych zmiennych, 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;
}
user2954726
źródło
A co z liczbą ujemną? Testowałem -12345 z 10 używając eclipse + CDT, ale wynik nie był tak dobry.
kenmux
Czy możesz mi powiedzieć, dlaczego robisz to ullDivisor >>= 1przed whilepętlą? A także nie nPos >= 0załatwi sprawy?
Vivekanand V
@kenmux Musisz wziąć pod uwagę tylko wielkość zaangażowanych liczb, najpierw wykonaj algorytm, a następnie używając odpowiednich instrukcji decyzyjnych, zwróć właściwy znak do ilorazu / reszty!
Vivekanand V
1
@VivekanandV Masz na myśli dodanie znaku - później? Tak to działa.
kenmux
5

Procedurę dzielenia liczb całkowitych wykorzystującą przesunięcia i dodania można wyprowadzić w prosty sposób z dziesiętnego dzielenia odręcznego, jak naucza się w szkole podstawowej. Wybór każdej cyfry ilorazu jest uproszczony, ponieważ cyfra wynosi 0 i 1: jeśli bieżąca reszta jest większa lub równa dzielnikowi, najmniej znaczący bit częściowego ilorazu wynosi 1.

Podobnie jak w przypadku dziesiętnego dzielenia odręcznego, cyfry dywidendy są rozpatrywane od najbardziej znaczącej do najmniej znaczącej, po jednej cyfrze na raz. Można to łatwo osiągnąć, przesuwając w lewo podział binarny. Również bity ilorazowe są zbierane przez przesunięcie w lewo bieżących bitów ilorazu o jedną pozycję, a następnie dołączenie nowego bitu ilorazu.

W układzie klasycznym te dwa przesunięcia w lewo są połączone w przesunięcie w lewo jednej pary rejestrów. W górnej połowie znajduje się bieżąca reszta, w dolnej połowie początkowa jest dywidenda. Ponieważ bity dywidendy są przenoszone do rejestru pozostałego przez przesunięcie w lewo, niewykorzystane najmniej znaczące bity dolnej połowy są wykorzystywane do gromadzenia bitów ilorazu.

Poniżej znajduje się język asemblera x86 i implementacje C tego algorytmu. Ten szczególny wariant dzielenia przesuń i dodaj jest czasami nazywany wariantem „niedziałającym”, 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 przenoszenia używanej przez wersję zespołu w przesunięciu w lewo pary rejestrów. Zamiast tego jest emulowany w oparciu o obserwację, że wynik dodawania modulo 2 n może być mniejszy niż sumowanie tylko wtedy, gdy nastąpiło wykonanie.

#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
njuffa
źródło
@greybeard Dzięki za wskaźnik, masz rację, pomyliłem dywidendę z ilorazem. Naprawię to.
njuffa
4

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

Zacznij od wyniku R o wartości 0.

Weź jedną z liczb, w tym przypadku 1010, nazwiemy ją A i przesuń ją w prawo o jeden bit, jeśli przesuniesz jedną, 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 zobaczysz to zapisane, oto przykład:

      0
   0000      0
  10010      1
 000000      0
1001000      1
 ------
1011010
Jimmeh
źródło
Wydaje się to najszybsze, po prostu wymaga trochę dodatkowego kodowania, aby zapętlić bity najmniejszej liczby i obliczyć wynik.
Hellonearthis
2

Zaczerpnięte stąd .

To dotyczy tylko 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;
}
Ashish Ahuja
źródło
2

jest to po prostu mnożenie i dzielenie z mocą podstawową 2

przesunięcie w lewo = x * 2 ^ y

przesuń w prawo = x / 2 ^ y

shl eax, 2 = 2 * 2 ^ 2 = 8

shr eax, 3 = 2/2 ^ 3 = 1/4

Karim Baidar
źródło
eaxnie może zawierać wartości ułamkowej, takiej jak 1/4. (Chyba że używasz wartości stałej zamiast liczby całkowitej, ale tego nie określiłeś)
Peter Cordes
1

To powinno zadziałać w przypadku 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
Melsi
źródło
Jaki smak montażu?
Keith Pinson
1
To montaż MIPS, jeśli o to pytasz. Myślę, że użyłem MARS do napisania / uruchomienia.
Melsi
1

Poniższa metoda polega na implementacji dzielenia binarnego, biorąc pod uwagę, że obie liczby są dodatnie. Jeśli odejmowanie jest problemem, możemy to również zaimplementować 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);
}

Do 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;
}
muzz
źródło
Jaka jest ta składnia? -(int)multiplyNumber:(int)num1 withNumber:(int)num2?
SS Anne
0

Dla każdego, kto interesuje się 16-bitowym rozwiązania x86, tam jest kawałek kodu przez JasonKnight tutaj 1 (on także podpisany pomnożyć kawałek, który nie testowałem). Jednak ten kod ma problemy z dużymi danymi wejściowymi, w przypadku których część „dodaj bx, bx” mogłaby się przepełnić.

Naprawiona wersja:

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 montażu inline 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"
);
aksyczny
źródło
-1

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])
swguru.net
źródło
5
To wygląda jak python. Pytanie zostało zadane podczas montażu i / lub C.
nieważne