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

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

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.

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?

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

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.

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

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;
}

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 ⁿ 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

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

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;
}

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

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

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;
}

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

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])