¿Cómo puedo multiplicar y dividir usando solo el cambio de bits y la suma?

86

¿Cómo puedo multiplicar y dividir usando solo el cambio de bits y la suma?

Spidfire
fuente
20
Como lo harías en papel en la escuela secundaria, solo usando binario en lugar de decimal.
Pascal Cuoq
1
@mtk: ¿Qué falta en esta respuesta ? ¿Está buscando una implementación de ensamblado o C, anchos de operandos particulares, un método de división específico (por ejemplo, restaurar o no restaurar)?
njuffa
¿Está bien la resta? Todo parece estar cubierto
mksteve
¿Cuál es la necesidad detrás de esta pregunta? La CPU traduce las operaciones de multiplicación y división en desplazamiento de bits y suma o resta, y si es que el compilador aún no lo ha hecho.
Kelly S. French
@ KellyS.French Solo curiosidad, es más una forma de imaginar cómo un compilador puede trabajar con un conjunto de instrucciones restringido.
Spidfire

Respuestas:

77

Para multiplicar en términos de suma y desplazamiento, desea descomponer uno de los números por potencias de dos, así:

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)

( _2significa base 2)

Como puede ver, la multiplicación se puede descomponer en sumas y cambios y viceversa. Esta es también la razón por la que la multiplicación lleva más tiempo que los cambios de bits o la suma: es O (n ^ 2) en lugar de O (n) en el número de bits. Los sistemas informáticos reales (a diferencia de los sistemas informáticos teóricos) tienen un número finito de bits, por lo que la multiplicación requiere un múltiplo constante de tiempo en comparación con la suma y el desplazamiento. Si mal no recuerdo, los procesadores modernos, si se canalizan correctamente, pueden hacer una multiplicación casi tan rápido como una suma, jugando con la utilización de las ALU (unidades aritméticas) en el procesador.

Andrew Toulouse
fuente
4
Sé que fue hace un tiempo, pero ¿podrías dar un ejemplo con la división? Gracias
GniruT
42

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.

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

Entonces, a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30) para la 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 interesantes de calcular la división y los residuos.

EDIT1:

Si 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 útil: https://stackoverflow.com/a/12699549/1182653

EDIT2:

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

Viktor Latypov
fuente
¡Muchas gracias por la referencia de Hacker's Delight!
alecxe
2
Ehm sí, esta respuesta (división por constante) es solo parcialmente correcta. Si intentas hacer '3/3' terminarás con 0. En Hacker's Delight, en realidad explican que hay un error que debes compensar. En este caso: b += r * 11 >> 5con r = a - q * 3. Enlace: hackersdelight.org/divcMore.pdf página 2+.
Atlas
30

X * 2 = desplazamiento de 1 bit a la izquierda
X / 2 = desplazamiento de 1 bit a la derecha
X * 3 = desplazamiento de 1 bit a la izquierda y luego agregar X

Kelly S. Francés
fuente
4
¿Te refieres add Xa ese último?
Mark Byers
1
Sigue siendo incorrecto; la última línea debería decir: "X * 3 = desplazar 1 bit a la izquierda y luego agregar X"
Paul R
1
"X / 2 = 1 bit shift right", no del todo, se redondea hacia abajo al infinito, en lugar de hasta 0 (para números negativos), que es la implementación habitual de la división (al menos hasta donde he visto).
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

Puede utilizar estos cambios para realizar 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 un no poder de dos, no conozco ninguna forma fácil, a menos que desee implementar alguna lógica de bajo nivel, usar otras operaciones binarias y usar alguna forma de iteración.

IVlad
fuente
@IVlad: ¿Cómo combinarías las operaciones anteriores para realizar, digamos, dividir por 3?
Paul R
@Paul R - cierto, eso es más difícil. He aclarado mi respuesta.
IVlad
la división por una constante no es demasiado difícil (multiplicar por la constante mágica y luego dividir por la potencia de 2), pero la división por una variable es un poco más complicada.
Paul R
1
¿no debería x * 14 == x * 16 - x * 2 == (x << 4) - (x << 2) realmente terminar siendo (x << 4) - (x << 1) ya que x < <1 es multiplicar por x por 2?
Alex Spencer
18
  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 un bucle para multiplicar. Al elegir correctamente la variable de ciclo y la variable de adición, puede limitar el rendimiento. Una vez que haya explorado eso, debe usar la multiplicación campesina
Yann Ramin
fuente
9
1: Sin embargo, el desplazamiento a la izquierda no es sólo análogo a multiplicar por 2. Se multiplica por 2. Al menos hasta que rebose ...
Don Roby
La división por turnos produce resultados incorrectos para números negativos.
David
6

Traduje el código de Python a C. El ejemplo dado tenía un pequeño defecto. Si el valor del dividendo ocupaba todos los 32 bits, el cambio fallaría. Solo usé 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;
}
usuario2954726
fuente
¿Qué pasa con el número negativo? Probé -12345 con 10 usando eclipse + CDT, pero el resultado no fue tan bueno.
kenmux
¿Puedes decirme por qué lo haces ullDivisor >>= 1antes del whilebucle? Además, ¿no funcionará nPos >= 0?
Vivekanand V
@kenmux Tienes que considerar solo la magnitud de los números involucrados, primero, haz el algoritmo y luego, usando algunas declaraciones apropiadas para la toma de decisiones, ¡devuelve el signo adecuado al cociente / resto!
Vivekanand V
1
@VivekanandV ¿Te refieres a agregar el letrero, más tarde? Si, funciona.
Kenmux
5

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

Al igual que con la división decimal a mano, los dígitos del dividendo se consideran del más significativo al menos significativo, un dígito a la vez. Esto se logra fácilmente mediante un desplazamiento a la izquierda en la división binaria. Además, los bits del cociente se recopilan desplazando a la izquierda los bits del cociente actual en una posición y luego agregando el nuevo bit del cociente.

En una disposición clásica, estos dos desplazamientos a la izquierda se combinan en un desplazamiento a la izquierda de un par de registros. La mitad superior contiene el resto actual, la mitad inferior inicial contiene el dividendo. A medida que los bits de dividendo se transfieren al registro restante mediante un desplazamiento a la izquierda, los bits menos significativos no utilizados de la mitad inferior se utilizan para acumular los bits del cociente.

A continuación se muestra el lenguaje ensamblador x86 y las implementaciones C de este algoritmo. Esta variante particular de una división de cambio y suma a veces se denomina variante "sin rendimiento", ya que la resta del divisor del resto actual no se realiza a menos que el resto sea mayor o igual que el divisor. En C, no hay noción de bandera de acarreo utilizada por la versión de ensamblaje en el desplazamiento a la izquierda del par de registros. En cambio, se emula, basándose en la observación de que el resultado de una suma módulo 2 n puede ser menor que cualquiera de los dos sumandos solo si hubo una ejecución.

#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
fuente
@greybeard Gracias por el puntero, tienes razón, mezclé el dividendo con el cociente. Lo arreglaré.
njuffa
4

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 un bit hacia la derecha, si saca uno, agregue el primer número, lo llamaremos B, a R.

Ahora cambie B a la izquierda 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 ve escrito, este es el ejemplo:

      0
   0000      0
  10010      1
 000000      0
1001000      1
 ------
1011010
Jimmeh
fuente
Esto parece más rápido, solo requiere un poco de codificación adicional para recorrer los bits del número más pequeño y calcular el resultado.
Hellonearthis
2

Tomado de aqui .

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;
}
Ashish Ahuja
fuente
2

es básicamente multiplicar y dividir con la potencia base 2

desplazar a la izquierda = x * 2 ^ y

desplazar a la derecha = x / 2 ^ y

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

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

Karim Baidar
fuente
eaxno puede contener un valor fraccionario como 1/4. (A menos que esté usando un punto fijo en lugar de un número entero, pero no lo especificó)
Peter Cordes
1

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
Melsi
fuente
¿Qué sabor de montaje?
Keith Pinson
1
Es ensamblaje MIPS, si esto es lo que estás preguntando. Creo que usé MARS para escribirlo / ejecutarlo.
Melsi
1

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 multiplicar:

-(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;
}
bozal
fuente
¿Qué es esta sintaxis? -(int)multiplyNumber:(int)num1 withNumber:(int)num2?
SS Anne
0

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 un fragmento de multiplicación firmado, 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 de 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"
);
axico
fuente
-1

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])
swguru.net
fuente
5
Esto parece una pitón. La pregunta se hizo para ensamblar y / o C.
nulo el