tablas - ¿Cómo puedo multiplicar y dividir utilizando solo cambios de bit y adición?
reglas para multiplicar por 10 100 y 1000 (13)
- Un cambio 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.
- Puede agregar un bucle para multiplicar. Al elegir la variable de bucle y la variable de adición correctamente, puede vincular el rendimiento. Una vez que haya explorado eso, debe usar Multiplicación Campesina
¿Cómo puedo multiplicar y dividir utilizando solo cambios de bit y adición?
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 implementar eso 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;
}
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
Para cualquier persona interesada en una solución de 16 bits x86, hay una pieza 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á.
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"
);
Para multiplicar en términos de sumar y desplazar, quiere 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)
( _2 significa base 2)
Como puede ver, la multiplicación puede descomponerse en suma y desplazamiento y viceversa. Esta es también la razón por la que la multiplicación lleva más tiempo que los cambios de bit 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 lleva un múltiplo de tiempo constante en comparación con la suma y el desplazamiento. Si recuerdo correctamente, los procesadores modernos, si se canalizan correctamente, pueden multiplicar casi tan rápido como la suma, al interferir con la utilización de las ALU (unidades aritméticas) en el procesador.
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])
Tomado de here .
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;
}
Tome dos números, digamos 9 y 10, escríbalos como binarios - 1001 y 1010.
Comience con un resultado, R, de 0.
Toma uno de los números, 1010 en este caso, lo llamaremos A, y lo desplazarás un poco hacia la derecha, si cambias uno, agrega el primer número, lo llamaremos B, a R.
Ahora mueva B un poco hacia la izquierda y repita hasta que todos los bits hayan sido desplazados de A.
Es más fácil ver lo que sucede si lo ves escrito, este es el ejemplo:
0
0000 0
10010 1
000000 0
1001000 1
------
1011010
Traducí el código de Python a C. El ejemplo dado tenía un defecto menor. Si el valor de 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;
}
Un procedimiento para dividir números enteros que usa turnos y agregaciones puede derivarse de manera directa de la división decimal de mano dura tal 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 alzada, los dígitos del dividendo se consideran de mayor a menor, un dígito a la vez. Esto se logra fácilmente mediante un cambio a la izquierda en la división binaria. Además, los bits del cociente se recopilan al desplazar a la izquierda los bits del cociente actual en una posición, y luego se agrega el nuevo bit del cociente.
En una disposición clásica, estos dos cambios a la izquierda se combinan en desplazamiento a la izquierda de un par de registros. La mitad superior contiene el resto actual, la inicial de la mitad inferior contiene el dividendo. A medida que los bits de dividendos se transfieren al registro restante por desplazamiento a la izquierda, los bits menos significativos no utilizados de la mitad inferior se usan para acumular los bits de 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 agregación 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 ninguna noción de la bandera de acarreo utilizada por la versión del conjunto en el par de registros del cambio a la izquierda. En cambio, se emula, basándose en la observación de que el resultado de un módulo de adición 2 n puede ser más pequeño, que puede sumar 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
X * 2 = cambio de 1 bit a la izquierda
X / 2 = cambio de 1 bit a la derecha
X * 3 = desplazar 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 un no poder de dos, no estoy al tanto 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.
La respuesta de Andrew Toulouse puede extenderse 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 división es escribir el valor inverso del denominador en la base dos.
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 aritmética de 32 bits.
Al combinar 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 residuos.
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 útil: https://.com/a/12699549/1182653
EDIT2:
Una de las maneras 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 manera más rápida de dividir un número entero por 3?