Multiplication de deux entiers à l'aide d'opérateurs au niveau du bit

Question

Comment multipiper deux entiers en utilisant des opérateurs au niveau du bit?

J'ai trouvé une implémentation here. Y a-t-il une meilleure façon de mettre en œuvre la multiplication?

Par exemple: 2 * 6 = 12 doit être effectué à l'aide d'opérateurs au niveau du bit.

REMARQUE: Les chiffres sont arbitraires et non puissance de 2

Answer 1

#include<stdio.h> 

main() 
{ 
    int a, b, result; 
    printf("\nEnter the numbers to be multiplied:"); 
    scanf("%d%d", &a, &b);  // a > b 
    result = 0; 
    while (b != 0)    // Iterate the loop till b == 0 
    { 
     if (b & 01)    // Bitwise & of the value of b with 01 
     { 
      result = result + a; // Add a to result if b is odd . 
     } 
     a<<=1;     // Left shifting the value contained in 'a' by 1 
            // Multiplies a by 2 for each loop 
     b>>=1;     // Right shifting the value contained in 'b' by 1. 
    } 
    printf("nResult:%d",result); 
} 

Source

Answer 2

L'entrée de Wikipedia sur bitwise operator applications a un code pseudo, mais il utilise l'opérateur d'addition ainsi que les opérateurs binaires.

Answer 3

algorithme de montage: Cela résulte directement du fait que ax * 7 = (ax * 8) ax.

mov  bx, ax   ;Save AX*1 
shl  ax, 1   ;AX := AX*2 
shl  ax, 1   ;AX := AX*4 
shl  ax, 1   ;AX := AX*8 
sub  ax, bx   ;AX := AX*7 

Chaque étape de changement est une multiplication par 2

Answer 4

En C# est ici la mise en œuvre de la fonction.

public static int Mul(int a, int b) 
    { 
     int r = 0; 
     while (b != 0) 
     { 
      var temp = b & 1; 

      if (temp!= 0) 
      { 
       r = r + a; 
      } 
      a= a << 1; 
      b= b >> 1; 
      if (temp == 0) 
      { 
       r = a; 
       break; 
      } 
     } 

     return r; 
    } 

Answer 5

Celui-ci est purement avec des opérations au niveau des bits.

public int bitwiseMultiply(int a, int b) { 
    if (a ==0 || b == 0) { 
     return 0; 
    } 

    if (a == 1) { 
     return b; 
    } 
    else 
     if (b == 1) { 
      return a; 
     } 


    int result = 0; // Not needed, just for test 
    int initA = a; 
    boolean isORNeeded = false; 
    while (b != 0) { 

     if (b == 1) { 
      break; 
     } 

     if ((b & 1) == 1) { // Carry needed, odd number 
      result += initA; // Test, not needed 
      isORNeeded = true; 
     } 

     a <<= 1; // Double the a 
     b >>= 1; // Half the b 
     System.out.println("a=["+a+"], b=["+b+"], result=["+result+"]"); 
    } 

    return (isORNeeded ? (a | initA) : a); // a + result; 
} 

Answer 6

#include<stdio.h> 
    void main() 
    { 
     int n, m, i, j, x, large, small, t1, m2, result, a1, a2, a3, c, c1, c2, r, r1, la, re; 

     printf("Enter two numbers\n"); 
     scanf("%d%d", &n, &m); 
     result = 0; 

     if (n > m) 
     { 
      large = n; 
      small = m; 
     } 
     else 
     { 
      large = m; 
      small = n; 
     } 

     c = 0; 

     while (small) 
     { 
      t1 = small; 
      t1 &= 1; 

      if (t1 == 1) 
      { 
       printf("\n %d", large); 
       la = large; 
       re = result; 
       m2 = 0; 
       r1 = 1; 
       while (re || la || c) 
       { 
        a2 = la; 
        a2 &= 1; 
        a3 = re; 
        a3 &= 1; 

        c1 = a2 & a3; 
        r = a3^a2; 

        c2 =r & c; 
        r ^= c; 
        if (c1 || c2) 
         c = 1; 
        else 
         c = 0; 

        result &= ~r1; 
        x = r; 
        m2 >>= 1; 
        while (m2) 
        { 
         r <<= 1; 
         m2 >>= 1; 
        } 

        result |= r; 
        la >>= 1; 
        re >>= 1; 
        r1 <<= 1; 
        m2 = r1; 
       } 

      } 
      large <<= 1; 
      small >>= 1; 

     } 
     printf("\n%dX%d= %d\n", n, m, result); 
    } 

Answer 7

Je suis venu ici à la recherche de cette question et je trouve la réponse de Zengr correcte. Merci Zengr! Mais il y a une modification que je voudrais voir qui se débarrasse de l'opérateur '+' dans son code. Ceci devrait faire la multiplication de deux nombres arbitraires en utilisant AUCUN OPÉRATEUR ARITHMÉTIQUE mais tous les bits.

solution de Zengr première:

#include<stdio.h> 
main() 
{ 
    int a,b,result;  
    printf("nEnter the numbers to be multiplied :"); 
    scanf("%d%d",&a,&b);   // a>b 
    result=0; 
    while(b != 0)    // Iterate the loop till b==0 
    { 
     if (b&01)    // Bitwise & of the value of b with 01 
     { 
      result=result+a;  // Add a to result if b is odd . 
     } 
     a<<=1;     // Left shifting the value contained in 'a' by 1 
          // multiplies a by 2 for each loop 
     b>>=1;     // Right shifting the value contained in 'b' by 1. 
    } 
    printf("nResult:%d",result); 
} 

Ma réponse est:

#include<stdio.h> 
main() 
{ 
    int a,b,result;  
    printf("nEnter the numbers to be multiplied :"); 
    scanf("%d%d",&a,&b);   // a>b 
    result=0; 
    while(b != 0)    // Iterate the loop till b==0 
    { 
     if (b&01)    // Bitwise & of the value of b with 01 
     { 
      result=add(result,a);  // Add a to result if b is odd . 
     } 
     a<<=1;     // Left shifting the value contained in 'a' by 1 
           // multiplies a by 2 for each loop 
     b>>=1;     // Right shifting the value contained in 'b' by 1. 
    } 
    printf("nResult:%d",result); 
} 

où je voudrais écrire ajouter() comme:

int Add(int x, int y) 
{ 
    // Iterate till there is no carry 
    while (y != 0) 
    { 
     // carry now contains common set bits of x and y 
     int carry = x & y; 

     // Sum of bits of x and y where at least one of the bits is not set 
     x = x^y; 

     // Carry is shifted by one so that adding it to x gives the required sum 
     y = carry << 1; 
    } 
    return x; 
} 

ou en ajoutant récursive comme:

int Add(int x, int y) 
{ 
    if (y == 0) 
     return x; 
    else 
     return Add(x^y, (x & y) << 1); 
} 

source pour le code additionnel: http://www.geeksforgeeks.org/add-two-numbers-without-using-arithmetic-operators/