Comment puis-je multiplier et diviser en utilisant uniquement le décalage de bits et l'ajout d'?

La réponse d'Andrew Toulouse peut être étendu à 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 de la mise en œuvre de la division est d'écrire l'inverse de la valeur du dénominateur dans la base de deux.

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

Donc,
a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30)
pour les 32 bits de l'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 de plus excitant façons de calculer la division et les restes.

EDIT1:

Si l'OP moyens de multiplication et de division d'un nombre arbitraire, pas la division par un nombre constant, alors ce fil pourrait être d'utilisation: https://stackoverflow.com/a/12699549/1182653

EDIT2:

L'un des moyens les plus rapides pour diviser par des constantes entières est d'exploiter l'arithmétique modulaire et Montgomery réduction: Quel est le moyen le plus rapide pour diviser un nombre entier par 3?

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 changements à faire toute 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)

De diviser un nombre par une puissance de deux, je ne suis pas au courant de toute manière facile, sauf si vous voulez mettre en œuvre certaines de bas niveau de la logique, de l'utilisation d'autres opérations binaires et l'utilisation d'une certaine forme d'itération.

J'ai traduit le code Python à C. L'exemple donné avait un défaut mineur. Si la valeur du dividende qui a pris toutes les 32 bits, le changement serait un échec. J'ai juste utilisé 64 bits des variables à l'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;
}

Une procédure de division de nombres entiers qui utilise les quarts de et ajoute peut être dérivé en simple mode de décimales en main de la division tel qu'il est enseigné à l'école primaire. La sélection de chaque quotient chiffre est simplifié, car le chiffre est de 0 et de 1: si le solde est supérieur ou égal au diviseur, le bit le moins significatif de l'partielle quotient est 1.

Tout comme avec décimale la main de la division, les chiffres du dividende sont considérés à partir de la plus importante à la moins importante, un chiffre à la fois. Ceci est facilement accompli par un virage à gauche dans la division binaire. Aussi, le quotient bits sont recueillies par la gauche déplacer le courant du quotient de bits d'une position, puis l'ajout de la nouvelle quotient peu.

Dans un ordonnancement classique, ces deux quarts de travail sont combinés dans la gauche le déplacement d'une seule paire. La moitié supérieure détient le courant reste, la moitié inférieure initiale détient le dividende. Comme le dividende bits sont transférés vers le reste s'inscrire en virage à gauche, la partie inutilisée des bits de poids faible de la moitié inférieure sont utilisés pour accumuler le quotient de bits.

Ci-dessous est x86 langage assembleur et C implémentations de cet algorithme. Cette variante particulière d'un shift & ajouter de la division est parfois appelé la "non-exécution", une variante de la soustraction de la division de l'actuelle reste n'est pas effectué, sauf si le solde est supérieur ou égal au diviseur. En C, il n'y a pas de notion de le porter un drapeau utilisé par la version de l'assembly dans le registre de la paire de décalage vers la gauche. Au lieu de cela, il est émulé, basée sur l'observation que le résultat d'une addition modulo 2ⁿ peut être plus petit que soit addend que si il y avait une réaliser.

#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

Cela devrait fonctionner pour la multiplication:

.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

Pour quiconque s'intéresse à un 16-bit x86 solution, il y a un morceau de code par JasonKnight iciUn (il comprend également signé multiplier pièce, que je n'ai pas testé). Toutefois, ce code a des problèmes avec les grandes entrées, où le "add bx,bx" une partie de débordement.

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 assembly en ligne:

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