Comment puis-je multiplier et diviser en utilisant seulement le déplacement de bits et l'ajout?
Comment puis-je multiplier et diviser en utilisant seulement le déplacement de bits et l'addition?
13 réponses
pour multiplier en termes d'addition et de déplacement vous voulez décomposer un des nombres par des puissances de deux, comme ceci:
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
signifie en base 2)
comme vous pouvez le voir, la multiplication peut être décomposée en Ajout et déplacement et retour. C'est aussi pourquoi la multiplication prend plus de temps que les déplacements de bits ou l'addition - c'est O(N^2) plutôt que O(n) dans le nombre de bits. Systèmes informatiques réels (par opposition à l'ordinateur théorique) systèmes) ont un nombre fini de bits, donc la multiplication prend un multiple constant de temps par rapport à l'addition et le déplacement. Si je me souviens bien, les processeurs modernes, s'ils sont pipelinés correctement, peuvent faire la multiplication à peu près aussi vite que l'addition, en jouant avec l'utilisation des ALUs (unités arithmétiques) dans le processeur.
la réponse D'Andrew Toulouse peut être étendue à la division.
La division par des constantes entières est examiné en détail dans le livre "Hacker s Delight" par Henry S. Warren (ISBN 9780201914658).
la première idée pour mettre en œuvre la division est d'écrire la valeur inverse du dénominateur dans la base deux.
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)
pour 32 bits arithmétique.
En combinant les termes d'une façon évidente, nous pouvons réduire le nombre d'opérations:
b = (a >> 2) + (a >> 4)
b += (b >> 4)
b += (b >> 8)
b += (b >> 16)
il y a des façons plus excitantes de calculer la division et les restes.
edit 1:
si le PO signifie multiplication et division de des nombres arbitraires, pas la division par un nombre constant, alors ce fil pourrait être utile: https://stackoverflow.com/a/12699549/1182653
EDIT2:
l'un des moyens les plus rapides de diviser par des constantes entières est d'exploiter l'arithmétique modulaire et la réduction de Montgomery: Quelle est la manière la plus rapide de diviser un entier par 3?
X * 2 = 1 bit shift left
X / 2 = déplacement de 1 bit à droite
X * 3 = déplacer vers la gauche 1 bit puis Ajouter X
x << k == x multiplied by 2 to the power of k
x >> k == x divided by 2 to the power of k
vous pouvez utiliser ces déplacements pour faire n'importe quelle opération de multiplication. Par exemple:
x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)
pour diviser un nombre par une non-puissance de deux, Je ne suis au courant d'aucune manière facile, à moins que vous vouliez mettre en œuvre une logique de bas niveau, utiliser d'autres opérations binaires et utiliser une certaine forme d'itération.
- un déplacement à gauche d'une position est analogue à une multiplication par 2. Un déplacement vers la droite est analogue à la division par 2.
- vous pouvez ajouter dans une boucle pour multiplier. En choisissant correctement la variable boucle et la variable addition, vous pouvez lier les performances. Une fois que vous avez exploré cela, vous devriez utiliser multiplication paysanne
j'ai traduit le code Python en C. L'exemple donné avait un défaut mineur. Si la valeur du dividende qui a pris tous les 32 bits, le déplacement aurait échoué. J'ai juste utilisé des variables 64 bits en interne pour contourner le problème:
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;
}
prenez deux nombres, disons 9 et 10, écrivez - les en binaire-1001 et 1010.
commence avec un résultat, R, de 0.
prenez un des numéros, 1010 dans ce cas, nous l'appellerons A, et décalez-le d'un peu, si vous décalez un un, ajoutez le premier numéro, nous l'appellerons B, À R.
maintenant, décalez B d'un bit et répétez jusqu'à ce que tous les bits aient été retirés de A.
il est plus facile de voir aller de l'avant si vous le voyez écrit, Voici l'exemple:
0
0000 0
10010 1
000000 0
1001000 1
------
1011010
une procédure pour diviser des entiers qui utilise des déplacements et des additions peut être dérivée directement de la division décimale à la main comme enseigné à l'école élémentaire. La sélection de chaque quotient est simplifiée, puisque le chiffre est soit 0 et 1: si le reste du courant est supérieur ou égal au diviseur, le bit le moins significatif du quotient partiel est 1.
comme pour la division décimale à la main, les chiffres du dividende sont considérés à partir de le plus significatif au moins significatif, un chiffre à la fois. Ceci est facilement accompli par un décalage de gauche dans la division binaire. De plus, les bits du quotient sont recueillis en déplaçant à gauche les bits du quotient actuel d'une position, puis en ajoutant le nouveau bit du quotient.
dans un arrangement classique, ces deux déplacements à gauche sont combinés en déplacement à gauche d'une paire de registres. La moitié supérieure détient le courant reste, la moitié inférieure initiale détient le dividende. Comme les bits de dividende sont les bits non utilisés les moins significatifs de la moitié inférieure sont utilisés pour accumuler les bits du quotient.
ci-dessous est le langage d'assemblage x86 et les implémentations C de cet algorithme. Cette variante particulière d'une division shift & add est parfois appelée la variante "non performante", car la soustraction du diviseur du reste courant n'est pas effectuée à moins que le reste soit supérieur ou égal au diviseur. En C, il n'y a aucune notion du drapeau de portage utilisé par la version d'assemblage dans le décalage de gauche de la paire de registres. Il est plutôt émulé, sur la base de l'observation que le résultat d'une addition modulo 2 n peut être plus petit que l'un ou l'autre addend seulement s'il y avait une Effectuer.
#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
tiré de ici .
uniquement pour la division:
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;
}
cela devrait fonctionner pour la multiplication:
.data
.text
.globl main
main:
# * =
addi , "151900920", 0x9
addi , "151900920", 0x6
add , "151900920", "151900920" # initialize product to zero
Loop:
beq , "151900920", Exit # if multiplier is 0,terminate loop
andi , , 1 # mask out the 0th bit in multiplier
beq , "151900920", Shift # if the bit is 0, skip add
addu , , # add (shifted) multiplicand to product
Shift:
sll , , 1 # shift up the multiplicand 1 bit
srl , , 1 # shift down the multiplier 1 bit
j Loop # go for next
Exit: #
EXIT:
li $v0,10
syscall
la méthode ci-dessous est la mise en œuvre de la division binaire considérant les deux nombres sont positifs. Si la soustraction est un problème nous pouvons implémenter cela aussi bien en utilisant des opérateurs binaires.
Code
-(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);
}
pour la multiplication:
-(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;
}
pour toute personne intéressée par une solution x86 16 bits, il y a un morceau de code par JasonKnight ici 1 (il inclut également un morceau multiplie signé, que je n'ai pas testé). Cependant, ce code a des problèmes avec les entrées importantes,où la partie "ajouter bx, bx" déborderait.
la version fixe:
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
Ou même dans GCC inline assemblée:
asm("mov "151910920",%%ax\n\t"
"mov "151910920",%%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 ,%%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"
);
essayez ceci. 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])