¿Cómo puedo multiplicar y dividir usando solo desplazamiento de bits y adición?

La respuesta de Andrew Toulouse se puede extender a la división.

La división por constantes enteras se considera en detalle en el libro "Hacker's Delight" de Henry S. Warren (ISBN 9780201914658).

La primera idea para implementar la división es escribir el valor inverso del denominador en base dos.

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

So, a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30) para aritmética de 32 bits.

Combinando los términos de una manera obvia podemos reducir el número de operaciones:

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

b += (b >> 4)

b += (b >> 8)

b += (b >> 16)

Hay formas más emocionantes de calcular la división y los restos.

EDIT1:

Si el OP significa multiplicación y división de números arbitrarios, no la división por un número constante, entonces este hilo podría ser de utilidad: https://stackoverflow.com/a/12699549/1182653

EDIT2:

Una de las formas más rápidas de dividir por constantes enteras es explotar el modular aritmética y reducción de Montgomery: ¿Cuál es la forma más rápida de dividir un entero por 3?

X * 2 = 1 bit shift left
X / 2 = 1 bit shift a la derecha
X * 3 = cambiar a la izquierda 1 bit y luego agregar X

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

Puede usar estos cambios para hacer cualquier operación de multiplicación. Por ejemplo:

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

Para dividir un número por una no potencia de dos, no soy consciente de ninguna manera fácil, a menos que desee implementar alguna lógica de bajo nivel, usar otras operaciones binarias y usar alguna forma de iteración.

1. Un desplazamiento a la izquierda por 1 posición es análogo a multiplicar por 2. Un desplazamiento a la derecha es análogo a dividir por 2.
2. Puede agregar en un bucle para multiplicar. Al elegir correctamente la variable de bucle y la variable de adición, puede vincular el rendimiento. Una vez que haya explorado eso, debe usar Multiplicación campesina

Traduje el código Python a C. El ejemplo dado tenía un defecto menor. Si el valor del dividendo que tomó todos los 32 bits, el cambio fallaría. Acabo de usar variables de 64 bits internamente para solucionar el problema:

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

Tome dos números, digamos 9 y 10, escríbalos como binarios - 1001 y 1010.

Comience con un resultado, R, de 0.

Tome uno de los números, 1010 en este caso, lo llamaremos A, y lo desplazaremos a la derecha por un bit, si cambia a uno, agregue el primer número, lo llamaremos B, a R.

Ahora cambie B a la izquierda por un bit y repita hasta que todos los bits se hayan desplazado fuera de A.

Es más fácil ver lo que está pasando si lo ves escrito, este es el ejemplo:

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

Un procedimiento para dividir enteros que utiliza cambios y adiciones se puede derivar de manera directa de la división decimal a mano larga como se enseña en la escuela primaria. La selección de cada dígito cociente se simplifica, ya que el dígito es 0 y 1: si el resto actual es mayor o igual al divisor, el bit menos significativo del cociente parcial es 1.

Al igual que con la división decimal de mano larga, los dígitos del dividendo se consideran de más significativos a menos significativo, un dígito a la vez. Esto se logra fácilmente por un desplazamiento a la izquierda en la división binaria. Además, los bits del cociente se recogen cambiando a la izquierda los bits del cociente actual por una posición, y luego añadiendo el nuevo bit del cociente.

En un arreglo clásico, estos dos cambios a la izquierda se combinan en un cambio a la izquierda de un par de registros. La mitad superior tiene el resto actual, la mitad inferior inicial tiene el dividendo. A medida que los bits de dividendo se transfieren al resto registro por desplazamiento izquierdo, los bits menos significativos no utilizados de la mitad inferior se utilizan para acumular los bits cocientes.

A continuación se muestra el lenguaje ensamblador x86 y las implementaciones en C de este algoritmo. Esta variante particular de una división shift & add a veces se conoce como la variante" sin rendimiento", ya que la sustracción del divisor del resto actual no se realiza a menos que el resto sea mayor o igual al divisor. En C, no hay noción de la bandera de porte utilizada por la versión de ensamblaje en el par de registro cambio a la izquierda. En su lugar, se emula, basado en la observación de que el resultado de una adición módulo 2ⁿ puede ser menor que cualquiera de los dos addend solo si hubo un carry out.

#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

Tomado de aquí.

Esto es solo para la división:

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

Esto debería funcionar para la multiplicación:

.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

El siguiente método es la implementación de la división binaria considerando que ambos números son positivos. Si la resta es una preocupación, podemos implementarla también usando operadores binarios.

Código

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

Para la multiplicación:

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

Para cualquier persona interesada en una solución x86 de 16 bits, hay un fragmento de código de JasonKnight aquí1 (también incluye una pieza de multiplicación firmada, que no he probado). Sin embargo, ese código tiene problemas con entradas grandes,donde la parte "agregar bx, bx" se desbordaría.

La versión fija:

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

O lo mismo en el ensamblaje en línea 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"
);

Prueba esto. 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])