wake-up-neo.net

Wie kann ich die Multiplikation ohne den Operator "*" durchführen?

Ich habe gerade einige grundlegende Dinge durchgelernt, während ich C. lernte. Ich kam auf die Frage, eine Zahl mit 7 zu multiplizieren, ohne den Operator * zu verwenden. Im Grunde ist es so

      (x << 3) - x;

Jetzt weiß ich über grundlegende Bitmanipulationsoperationen Bescheid, aber ich kann nicht verstehen, wie man eine Zahl mit einer anderen ungeraden Zahl multipliziert, ohne den Operator * zu verwenden. Gibt es dafür einen allgemeinen Algorithmus?

45
Race

Denken Sie darüber nach, wie Sie sich mit Bleistift und Papier dezimal multiplizieren:

  12
x 26
----
  72
 24
----
 312

Wie sieht die Multiplikation in binär aus?

   0111
x  0101
-------
   0111
  0000
 0111
-------
 100011

Etwas merken? Im Gegensatz zur Multiplikation in Dezimalzahlen, bei der Sie sich die "Zeittabelle" merken müssen, multiplizieren Sie bei der binären Multiplikation immer einen der Terme entweder mit 0 oder 1, bevor Sie ihn in die Listen-Addends schreiben. Es ist kein Zeitplan nötig. Wenn die Ziffer des zweiten Terms 1 ist, addieren Sie den ersten Term. Wenn es 0 ist, tun Sie es nicht. Beachten Sie auch, wie die Addenden schrittweise nach links verschoben werden.

Wenn Sie sich nicht sicher sind, führen Sie einige binäre Multiplikationen auf Papier durch. Wenn Sie fertig sind, konvertieren Sie das Ergebnis wieder in Dezimalzahlen und prüfen Sie, ob es richtig ist. Nachdem Sie einige erledigt haben, werden Sie die Idee haben, wie die binäre Multiplikation mithilfe von Shifts und Adds implementiert werden kann.

59
Wayne Conrad

Jeder übersieht das Offensichtliche. Es ist keine Multiplikation beteiligt:

10^(log10(A) + log10(B))
25
Jim C

Die Frage lautet:

multiplizieren Sie eine Zahl mit 7, ohne den Operator * zu verwenden

Dies verwendet nicht *:

 number / (1 / 7) 

Bearbeiten:
Das kompiliert und funktioniert gut in C:

 int number,result;
 number = 8;
 result = number / (1. / 7);
 printf("result is %d\n",result);
19

Eine Ganzzahlverschiebung nach links multipliziert mit 2, sofern sie nicht überläuft. Addieren oder subtrahieren Sie einfach, wenn Sie näher kommen.

int multiply(int multiplicand, int factor)
{
    if (factor == 0) return 0;

    int product = multiplicand;
    for (int ii = 1; ii < abs(factor); ++ii) {
        product += multiplicand;
    }

    return factor >= 0 ? product : -product;
}

Du wolltest Multiplikation ohne *, du hast es, Kumpel!

17
user123456

Der '*'-Operator lässt sich leicht vermeiden:

mov eax, 1234h
mov edx, 5678h
imul edx

Kein '*' in Sicht. Wenn Sie sich in den Geist hineinversetzen möchten, können Sie natürlich auch den bewährten alten Shift- und Add-Algorithmus verwenden:

mult proc
; Multiplies eax by ebx and places result in edx:ecx
    xor ecx, ecx
    xor edx, edx
mul1:
    test ebx, 1
    jz  mul2
    add ecx, eax
    adc edx, 0
mul2:
    shr ebx, 1
    shl eax, 1
    test ebx, ebx
    jnz  mul1
done:
    ret
mult endp

Natürlich haben alle (?) Mit modernen Prozessoren Multiplikationsanweisungen, aber als der PDP-11 glänzte und neu war, sah Code wie dieser eine echte Verwendung.

12
Jerry Coffin

Mathematisch gesehen multipliziert verteilt über Addition. Im Wesentlichen bedeutet dies:

x * (a + b + c ...) = (x * a) + (x * b) + (x * c) ...

Jede reelle Zahl (in Ihrem Fall 7) kann als eine Reihe von Additionen dargestellt werden (z. B. 8 + (-1), da die Subtraktion wirklich nur eine Addition ist, die in die falsche Richtung geht). Auf diese Weise können Sie jede einzelne Multiplikationsanweisung als eine äquivalente Reihe von Multiplikationsanweisungen darstellen, die zu demselben Ergebnis führen:

x * 7
= x * (8 + (-1))
= (x * 8) + (x * (-1))
= (x * 8) - (x * 1)
= (x * 8) - x

Der Operator bitwise shift multipliziert oder dividiert im Wesentlichen eine Zahl mit einer Potenz von 2. Solange Ihre Gleichung nur solche Werte behandelt, kann Bitverschiebung verwendet werden, um das gesamte Vorkommen des Multiplikationsoperators zu ersetzen.

(x * 8) - x = (x * 2)3) - x = (x << 3) - x

Eine ähnliche Strategie kann für jede andere ganze Zahl verwendet werden. Dabei spielt es keine Rolle, ob sie gerade oder ungerade ist.

10
goldPseudo

Es ist das gleiche wie x*8-x = x*(8-1) = x*7

8
Igor Zevaka

Jede Zahl, ungerade oder gerade, kann als Summe von Zweierpotenzen ausgedrückt werden. Zum Beispiel,

     1   2   4   8
------------------
 1 = 1
 2 = 0 + 2
 3 = 1 + 2
 4 = 0 + 0 + 4
 5 = 1 + 0 + 4
 6 = 0 + 2 + 4
 7 = 1 + 2 + 4
 8 = 0 + 0 + 0 + 8
11 = 1 + 2 + 0 + 8

Sie können also x mit einer beliebigen Zahl multiplizieren, indem Sie die richtige Menge von Verschiebungen und Additionen ausführen.

 1x = x
 2x = 0 + x<<1
 3x = x + x<<1
 4x = 0 +  0   + x<<2
 5x = x +  0   + x<<2
11x = x + x<<1 +   0  + x<<3
7
benzado

Wenn es darauf ankommt, kann die Multiplikation mit einer positiven Ganzzahl folgendermaßen erfolgen:

int multiply(int a, int b) {
  int ret = 0;
  for (int i=0; i<b; i++) {
    ret += b;
  }
  return ret;
}

Effizient? Kaum. Aber es ist richtig (Berücksichtigung der Grenzen von Ints usw.).

Eine Linksverschiebung ist also nur eine Abkürzung für das Multiplizieren mit 2. Wenn Sie jedoch unter b die höchste Potenz von 2 erreicht haben, fügen Sie a nur die erforderliche Anzahl hinzu, also:

int multiply(int a, int b) {
  int ret = a;
  int mult = 1;
  while (mult <= b) {
    ret <<= 1;
    mult <<= 1;
  }
  while (mult < b) {
    ret += a;
  }
  return ret;
}

oder etwas in der Nähe.

Anders ausgedrückt, mit 7 multiplizieren.

  • Linksverschiebung um 2 (mal 4). Die linke Verschiebung 3 ist 8, was> 7 ist;
  • Fügen Sie dreimal b hinzu.
5
cletus

Eines Abends fand ich, dass ich extrem gelangweilt war, und kochte das zusammen:

#include <iostream>

typedef unsigned int uint32;

uint32 add(uint32 a, uint32 b) {
    do {
        uint32 s = a ^ b;
        uint32 c = a & b;
        a = s;
        b = c << 1;
    } while (a & b)
    return (a | b)
}

uint32 mul(uint32 a, uint32 b) {
    uint32 total = 0;
    do {
        uint32 s1 = a & (-(b & 1))
        b >>= 1; a <<= 1;
        total = add(s1, total)
    } while (b)
    return total;
}

int main(void) {
    using namespace std;
    uint32 a, b;

    cout << "Enter two numbers to be multiplied: ";
    cin >> a >> b;

    cout << "Total: " << mul(a,b) << endl;
    return 0;
}

Der obige Code sollte ziemlich selbsterklärend sein, da ich versucht habe, ihn so einfach wie möglich zu halten. Es sollte mehr oder weniger funktionieren, wie eine CPU diese Operationen ausführen könnte. Der einzige Fehler, den ich kenne, ist, dass a nicht größer als 32.767 sein darf und b nicht groß genug für einen Überlauf a sein darf (das heißt, ein mehrfacher Überlauf wird nicht behandelt, daher sind 64-Bit-Ergebnisse nicht möglich.) . Es sollte sogar mit negativen Zahlen funktionieren, vorausgesetzt, die Eingaben sind entsprechend reinterpret_cast<>.

4
greyfade

O (log (b)) Methode

public int multiply_optimal(int a, int b) {

    if (a == 0 || b == 0)
        return 0;
    if (b == 1)
        return a;
    if ((b & 1) == 0)
        return multiply_optimal(a + a, b >> 1);
    else
        return a + multiply_optimal(a + a, b >> 1);

}

Der resursive Code funktioniert wie folgt:
Basisfall:
Wenn eine der Zahlen 0 ist, ist das Produkt 0.
wenn b = 1, Produkt = a.

Wenn b gerade ist:
ab kann als 2a (b/2) geschrieben werden
2a (b/2) = (a + a) (b/2 (a + a)) == (b >> 1) wobei '>>' rechter arithematischer Schaltoperator ist in Java.

Wenn b ungerade ist:
ab kann als a + a (b-1) geschrieben werden
[...] a + a (b-1) = a + 2a (b-1)/2 = a + (a + a) (b-1)/2 = a + (a + a) ((b-1) ) >> 1)
Da b ungerade ist (b-1)/2 = b/2 = b >> 1
Also ab = a + (2a * (b >> 1))
HINWEIS: Jeder rekursive Aufruf b ist halbiert => O (log (b))

4
FReeze FRancis
unsigned int Multiply(unsigned int m1, unsigned int m2)
{
    unsigned int numBits = sizeof(unsigned int) * 8; // Not part of the core algorithm
    unsigned int product = 0;
    unsigned int mask = 1;
    for(int i =0; i < numBits; ++i, mask = mask << 1)
    {
        if(m1 & mask)
        {
            product += (m2 << i);
        }
    }
    return product;
}
3
Andrew Shepherd

@ Wang, das ist eine gute Verallgemeinerung. Aber hier ist eine etwas schnellere Version. Es wird jedoch kein Überlauf angenommen und a ist nicht negativ.

int mult(int a, int b){
    int p=1;
    int rv=0;
    for(int i=0; a >= p && i < 31; i++){
        if(a & p){
            rv += b;
        }
        p = p << 1;
        b = b << 1;
    }

    return rv;
}

Es wird höchstens 1 + log_2 (a) mal wiederholt. Könnte schneller sein, wenn Sie a und b tauschen, wenn a> b. 

2
unsigned int Multiply( unsigned int a, unsigned int b )
{
    int ret = 0;
    // For each bit in b
    for (int i=0; i<32; i++) {

        // If that bit is not equal to zero
        if (( b & (1 << i)) != 0) {

            // Add it to our return value
            ret += a << i;
        }
    }
    return ret;
}

Ich habe das Zeichenbit vermieden, weil es irgendwie nicht das Thema des Beitrags ist. Dies ist eine Implementierung dessen, was Wayne Conrad grundsätzlich gesagt hat. Hier ist ein weiteres Problem, dass Sie mehr einfache mathematische Operationen ausprobieren möchten.Project Euler ist cool!

2
Buttink

Verschieben und Hinzufügen funktioniert nicht (auch bei Vorzeichenerweiterung), wenn der Multiplikand negativ ist. Die signierte Multiplikation muss mit Booth-Codierung erfolgen:

Ausgehend von LSB ist eine Änderung von 0 auf 1 -1; Eine Änderung von 1 auf 0 ist 1, sonst 0. Unter dem LSB befindet sich auch ein implizites Zusatzbit 0.

Zum Beispiel wird die Nummer 5 (0101) wie folgt codiert: (1) (- 1) (1) (- 1). Sie können überprüfen, ob dies korrekt ist:

5 = 2 ^ 3 - 2 ^ 2 + 2 -1

Dieser Algorithmus arbeitet auch mit negativen Zahlen in Zweierkomplement:

-1 in 4-Bit-2-Komplement ist 1111. Mit dem Booth-Algorithmus: (1) (0) (0) (0) (- 1), wo für das ganz linke Bit 1 kein Platz vorhanden ist, erhalten wir: (0) (0) (0) (- 1) was -1 ist.

/* Multiply two signed integers using the Booth algorithm */
int booth(int x, int y)
{
    int prev_bit = 0;
    int result = 0;

    while (x != 0) {
        int current_bit = x & 0x1;
        if (prev_bit & ~current_bit) {
            result += y;
        } else if (~prev_bit & current_bit) {
            result -= y;
        }

        prev_bit = current_bit;

        x = static_cast<unsigned>(x) >> 1;
        y <<= 1;
    }

    if (prev_bit)
        result += y;

    return result;
}

Der obige Code prüft nicht auf Überlauf. Unten ist eine leicht modifizierte Version, die zwei 16-Bit-Zahlen multipliziert und eine 32-Bit-Zahl zurückgibt, sodass sie niemals überläuft:

/* Multiply two 16-bit signed integers using the Booth algorithm */
/* Returns a 32-bit signed integer */
int32_t booth(int16_t x, int16_t y)
{
    int16_t prev_bit = 0;
    int16_t sign_bit = (x >> 16) & 0x1;
    int32_t result = 0;
    int32_t y1 = static_cast<int32_t>(y);

    while (x != 0) {
        int16_t current_bit = x & 0x1;
        if (prev_bit & ~current_bit) {
            result += y1;
        } else if (~prev_bit & current_bit) {
            result -= y1;
        }

        prev_bit = current_bit;

        x = static_cast<uint16_t>(x) >> 1;
        y1 <<= 1;
    }

    if (prev_bit & ~sign_bit)
        result += y1;

    return result;
}
2
user3225538
import Java.math.BigInteger;

public class MultiplyTest {
    public static void main(String[] args) {
        BigInteger bigInt1 = new BigInteger("5");
        BigInteger bigInt2 = new BigInteger("8");
        System.out.println(bigInt1.multiply(bigInt2));
    }
}
2
lordstriker24

Java:
In Anbetracht der Tatsache, dass jede Zahl in Zweierpotenzen aufgeteilt werden kann:

1 = 2 ^ 0
2 = 2 ^ 1
3 = 2 ^ 1 + 2 ^ 0
...

Wir wollen x wo:
x = n * m

So können wir das erreichen, indem Sie die folgenden Schritte ausführen:

1.   while m is greater or equal to 2^pow:
     1.1  get the biggest number pow, such as 2^pow is lower or equal to m
     1.2  multiply n*2^pow and decrease m to m-2^pow
2.   sum the results

Beispielimplementierung mit Rekursion:

long multiply(int n, int m) {
    int pow = 0;
    while (m >= (1 << ++pow)) ;
    pow--;
    if (m == 1 << pow) return (n << pow);
    return (n << pow) + multiply(n, m - (1 << pow));
}

Ich habe diese Frage im letzten Vorstellungsgespräch bekommen und diese Antwort wurde akzeptiert.

EDIT: Lösung für positive Zahlen

1

Wenn Sie die Protokollfunktion verwenden können:

public static final long multiplyUsingShift(int a, int b) {
    int absA = Math.abs(a);
    int absB = Math.abs(b);

    //Find the 2^b which is larger than "a" which turns out to be the 
    //ceiling of (Log base 2 of b) == numbers of digits to shift
    double logBase2 = Math.log(absB) / Math.log(2);
    long bits = (long)Math.ceil(logBase2);

    //Get the value of 2^bits
    long biggerInteger = (int)Math.pow(2, bits);

    //Find the difference of the bigger integer and "b"
    long difference = biggerInteger - absB;

    //Shift "bits" places to the left
    long result = absA<<bits;

    //Subtract the "difference" "a" times
    int diffLoop = Math.abs(a);
    while (diffLoop>0) {
        result -= difference;
        diffLoop--;
    }

    return (a>0&&b>0 || a<0&&b<0)?result:-result;
}

Wenn Sie die Protokollfunktion nicht verwenden können:

public static final long multiplyUsingShift(int a, int b) {
    int absA = Math.abs(a);
    int absB = Math.abs(b);

    //Get the number of bits for a 2^(b+1) larger number
    int bits = 0;
    int bitInteger = absB;
    while (bitInteger>0) {
        bitInteger /= 2;
        bits++;
    }

    //Get the value of 2^bit
    long biggerInteger = (int)Math.pow(2, bits);

    //Find the difference of the bigger integer and "b"
    long difference = biggerInteger - absB;

    //Shift "bits" places to the left
    long result = absA<<bits;

    //Subtract the "difference" "a" times
    int diffLoop = absA;
    while (diffLoop>0) {
        result -= difference;
        diffLoop--;
    }

    return (a>0&&b>0 || a<0&&b<0)?result:-result;
}

Ich fand das effizienter:

public static final long multiplyUsingShift(int a, int b) {
    int absA = Math.abs(a);
    int absB = Math.abs(b);

    long result = 0L;
    while (absA>0) {
        if ((absA&1)>0) result += absB; //Is odd
        absA >>= 1;
        absB <<= 1;
    }

    return (a>0&&b>0 || a<0&&b<0)?result:-result;
}

und noch ein anderer Weg.

public static final long multiplyUsingLogs(int a, int b) {
    int absA = Math.abs(a);
    int absB = Math.abs(b);
    long result = Math.round(Math.pow(10, (Math.log10(absA)+Math.log10(absB))));
    return (a>0&&b>0 || a<0&&b<0)?result:-result;
}
1
Justin

In c #:

private static string Multi(int a, int b)
{
    if (a == 0 || b == 0)
        return "0";

    bool isnegative = false;

    if (a < 0 || b < 0)
    {
        isnegative = true;

        a = Math.Abs(a);

        b = Math.Abs(b);
    }

    int sum = 0;

    if (a > b)
    {
        for (int i = 1; i <= b; i++)
        {
            sum += a;
        }
    }
    else
    {
        for (int i = 1; i <= a; i++)
        {
            sum += b;
        }
    }

    if (isnegative == true)
        return "-" + sum.ToString();
    else
        return sum.ToString();
}
1
user270004

Dies ist die einfachste C99/C11-Lösung für positive Zahlen:

unsigned multiply(unsigned x, unsigned y) { return sizeof(char[x][y]); }
1
chqrlie

Eine andere denkende Antwort:

BigDecimal a = new BigDecimal(123);
BigDecimal b = new BigDecimal(2);
BigDecimal result = a.multiply(b);
System.out.println(result.intValue());
0
Igor Nadj

Durch Rekursion können wir zwei Ganzzahlen mit den gegebenen Einschränkungen multiplizieren.

Addieren Sie x und y rekursiv, um x und y zu multiplizieren.

     #include<stdio.h>
     /* function to multiply two numbers x and y*/
     int multiply(int x, int y)
     {
        /* multiplied with anything gives */
        if(y == 0)
        return 0;

        /* Add x one by one */
        if(y > 0 )
        return (x + multiply(x, y-1));

        /* the case where y is negative */
        if(y < 0 )
        return -multiply(x, -y);
     }

     int main()
     {
       printf("\n %d", multiply(5, -11));
       getchar();
       return 0;
     }
0
Vikash VK

Schleife es. Führen Sie eine Schleife siebenmal durch und wiederholen Sie die Anzahl, die Sie mit sieben multiplizieren.

Pseudocode:

total = 0
multiply = 34

loop while i < 7

    total = total + multiply

endloop
0
Thomas Winsnes
public static void main(String[] args) {
    System.out.print("Enter value of A -> ");
    Scanner s=new Scanner(System.in);
    double j=s.nextInt();
    System.out.print("Enter value of B -> ");
    Scanner p=new Scanner(System.in);
    double k=p.nextInt();
    double m=(1/k);
    double l=(j/m);
    System.out.print("Multiplication of A & B=> "+l);
}
0
aashish041090

Sei N die Zahl, die wir mit 7 multiplizieren wollen. 

N x 7 = N + N + N + N + N + N + N
N x 7 = N + N + N + N + N + N + N + (N - N)
N x 7 = (N + N + N + N + N + N + N + N) - N
N x 7 = 8xN - N

Wie wir wissen, multiplizieren Sie jede Zahl mit einem Bit nach links, multiplizieren Sie sie mit 2. Daher ist das Multiplizieren einer beliebigen Zahl mit 8 gleichbedeutend mit einer Verschiebung nach rechts um 3 Bits

N x 7 = (N << 3) - N 

Ich habe diese Beschreibung hier gefunden http://www.techcrashcourse.com/2016/02/c-programm-to-multiply-number-by-7-bitwise-operator.html

Ich hoffe es hilft. 

0
Arun Kumar

Ein JavaScript-Ansatz für positive Zahlen 

function recursiveMultiply(num1, num2){
    const bigger = num1 > num2 ? num1 : num2; 
    const smaller = num1 <= num2 ? num1 : num2; 
    const indexIncrement = 1;
    const resultIncrement = bigger;

    return recursiveMultiplyHelper(bigger, smaller, 0, indexIncrement, resultIncrement)
}

function recursiveMultiplyHelper(num1, num2, index, indexIncrement, resultIncrement){
    let result = 0;
    if (index === num2){
        return result;
    } 

    if ((index+indexIncrement+indexIncrement) >= num2){
        indexIncrement = 1;
        resultIncrement = num1;
    } else{
        indexIncrement += indexIncrement;
        resultIncrement += resultIncrement;
    }

    result = recursiveMultiplyHelper(num1, num2, (index+indexIncrement), indexIncrement, resultIncrement);
    result += resultIncrement;
    console.log(num1, num2, index, result);

    return result;
}
0
Eli Silver
public static int multiply(int a, int b) 
{
    int temp = 0;
    if (b == 0) return 0;
    for (int ii = 0; ii < abs(b); ++ii) {
        temp = temp + a;
    }

    return b >= 0 ? temp : -temp;
}

public static int abs(int val) {

    return val>=0 ? val : -val;
}
0
package com.amit.string;

// Here I am passing two values, 7 and 3 and method getResult() will
// return 21 without use of any operator except the increment operator, ++.
//
public class MultiplyTwoNumber {

    public static void main(String[] args) {
        int a = 7;
        int b = 3;
        System.out.println(new MultiplyTwoNumber().getResult(a, b));
    }

    public int getResult(int i, int j) {
        int result = 0;

        // Check for loop logic it is key thing it will go 21 times
        for (int k = 0; k < i; k++) {
            for (int p = 0; p < j; p++) {
                result++;
            }
        }
        return result;
    }
}
0
Amit Sinha