Как я могу выполнить умножение без оператора '*'?

Ответ 1

Подумайте, как вы умножаете десятичное число с помощью карандаша и бумаги:

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

Что такое умножение в двоичном формате?

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

Заметьте что-нибудь? В отличие от умножения в десятичном значении, когда вам нужно запомнить "таблицу раз" при умножении в двоичном формате, вы всегда умножаете одно из условий на 0 или 1, прежде чем записывать их в списках. Нет необходимости в таблице раз. Если цифра второго слагаемого равна 1, вы добавляете в первый член. Если это 0, вы этого не сделаете. Также обратите внимание, как слагаемые постепенно смещаются влево.

Если вы не уверены в этом, сделайте несколько бинарных умножений на бумаге. Когда вы закончите, верните результат обратно в десятичный и посмотрите, правильно ли он. После того, как вы сделали несколько, я думаю, вы поймете, как двоичное умножение может быть реализовано с помощью сдвигов и добавлений.

Ответ 2

Все игнорируют очевидное. Не используется умножение:

10^(log10(A) + log10(B))

Ответ 3

Целый левый сдвиг умножается на 2, если он не переполняется. Просто добавьте или вычтите по мере необходимости, как только вы приблизитесь.

Ответ 4

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;
}

Вы хотели размножаться без *, вы получили его, приятель!

Ответ 5

В вопросе говорится:

умножьте число на 7 без использования * operator

Это не использует *:

 number / (1 / 7) 

Edit:
Это компилируется и отлично работает в C:

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

Ответ 6

Легко избежать оператора '*':

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

Нет '*' в поле зрения. Конечно, если вы хотели вникать в это, вы могли бы также использовать надежную старую смену и добавить алгоритм:

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

Конечно, с современными процессорами все (?) имеют инструкции умножения, но назад, когда PDP-11 был блестящим и новым, такой код видел реальное использование.

Ответ 7

Математически умножение распределяется по сложениям. По сути, это означает:

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

Любое действительное число (в вашем случае 7) может быть представлено в виде серии дополнений (например, 8 + (-1), так как вычитание действительно просто происходит неправильно). Это позволяет представить любой оператор умножения как эквивалентную последовательность операторов умножения, которая будет иметь тот же результат:

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

Оператор побитового сдвига по существу просто умножает или делит число на мощность 2. Пока ваше уравнение имеет дело только с такими значениями, смещение битов может использоваться для замены всего возникновения оператор умножения.

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

Аналогичная стратегия может быть использована для любого другого целого числа, и не имеет значения, является ли это нечетным или четным.

Ответ 8

Это то же самое, что и x*8-x = x*(8-1) = x*7

Ответ 9

Любое число, нечетное или четное, может быть выражено как сумма степеней двух. Например,

     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

Итак, вы можете умножить x на любое число, выполнив правильный набор сдвигов и добавив.

 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

Ответ 10

Когда дело доходит до этого, умножение на положительное целое можно сделать следующим образом:

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

Эффективное? Едва. Но он правильный (факторинг в пределах по ints и т.д.).

Таким образом, использование сдвига влево - это просто ярлык для умножения на 2. Но как только вы дойдете до наивысшей мощности-2 в b, просто добавьте a необходимое количество раз, поэтому:

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;
}

или что-то близкое к этому.

Иными словами, умножить на 7.

• Сдвиг влево на 2 (раз 4). Левый сдвиг 3 равен 8, который равен > 7;
• Добавить b 3 раза.

Ответ 11

Однажды вечером я обнаружил, что мне очень скучно, и приготовил это:

#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;
}

Приведенный выше код должен быть совершенно понятным, поскольку я старался максимально упростить его. Он должен работать, более или менее, способом, которым процессор может выполнять эти операции. Единственная ошибка, о которой я знаю, заключается в том, что a не разрешается превышать 32 767, а b не допускается достаточно большим для переполнения a (то есть переполнение переполнения не обрабатывается, поэтому 64- битные результаты невозможны). Он должен работать даже с отрицательными числами, если входы соответствуют reinterpret_cast<>.

Ответ 12

O (log (b)) метод

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

}

Ресурсный код работает следующим образом:
Базовый блок:
если любое из чисел 0, произведение равно 0.
если b = 1, product = a.

Если b четно:
ab можно записать как 2a (b/2)
2a (b/2) = (a + a) (b/2) = (a + a) (b → 1) где ' → ' арифметический оператор правого сдвига в java.

Если b нечетно:
ab может быть записано как a + a (b-1)
а + а (б-1) = а + 2а (B-1)/2 = а + (а + а) (б-1)/2 = а + (а + а) ((б-1) → 1)
Так как b нечетно (b-1)/2 = b/2 = b → 1
Итак, ab = a + (2a * (b → 1))
ПРИМЕЧАНИЕ: каждый рекурсивный вызов b уменьшается наполовину = > O (log (b))

Ответ 13

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;
}

Ответ 14

@Wang, это хорошее обобщение. Но вот немного более быстрая версия. Но он не предполагает переполнения и a неотрицателен.

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;
}

Он будет занимать не более 1 + log_2 (a) раз. Может быть быстрее, если вы замените a и b, когда a > b.

Ответ 15

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;
}

Я избегал знакового бита, потому что это не тема поста. Это реализация того, что сказал Уэйн Конрад. Еще одна проблема заключается в том, что вы хотите попробовать более низкие математические операции. Project Euler - это классно!

Ответ 16

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

Ответ 17

Сдвиг и добавление не работают (даже с расширением знака), когда мультипликация отрицательна. Подписанное умножение должно быть выполнено с помощью Бут-кодировка:

Начиная с LSB, изменение от 0 до 1 равно -1; изменение от 1 до 0 равно 1, в противном случае 0. Существует также неявный дополнительный бит 0 ниже LSB.

Например, номер 5 (0101) будет кодироваться как: (1) (- 1) (1) (- 1). Вы можете убедиться, что это правильно:

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

Этот алгоритм также работает с отрицательными числами в 2 форме дополнения:

-1 в 4-битном дополнении - 1111. Используя алгоритм Бута: (1) (0) (0) (0) (- 1), где нет места для самого левого бита 1, получаем: (0) (0) (0) (-1), которая равна -1.

/* 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;
}

Приведенный выше код не проверяет переполнение. Ниже приведена небольшая версия, которая умножает два 16-разрядных номера и возвращает 32-битное число, поэтому оно никогда не переполняется:

/* 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;
}

Ответ 18

Если вы можете использовать функцию журнала:

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;
}

Если вы не можете использовать функцию журнала:

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;
}

Я нашел это более эффективным:

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;
}

и еще один способ.

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;
}

Ответ 19

JAVA:. Учитывая тот факт, что каждое число можно разделить на степени двух:

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

Мы хотим получить x где:
x = n * m

Поэтому мы можем добиться этого, выполнив следующие шаги:

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

Пример реализации с использованием рекурсии:

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

Я получил этот вопрос на последнем собеседовании, и этот ответ был принят. EDIT: решение для положительных чисел

Ответ 20

Это простейшее решение C99/C11 для положительных чисел:

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

Ответ 21

Другой ответ на вопрос:

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

Ответ 22

В С#:

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();
}

Ответ 23

Завершить его. Запустите цикл семь раз и итерации по числу, которое вы умножаете на семь.

псевдокод:

total = 0
multiply = 34

loop while i < 7

    total = total + multiply

endloop

Ответ 24

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;
    }
}

Ответ 25

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;
}

Ответ 26

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

Ответ 27

Пусть N - число, которое мы хотим умножить на 7.

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

Как мы знаем, левое смещение любого числа на один бит умножает его на 2. Следовательно, умножение любого числа на 8 эквивалентно праву, смещающему его на 3 бита

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

Я нашел это описание здесь http://www.techcrashcourse.com/2016/02/c-program-to-multiply-number-by-7-bitwise-operator.html

Надеюсь, это поможет.

Ответ 28

Очень просто, приятель... Каждый раз, когда вы оставляете сдвиг числа, это означает, что вы умножаете число на 2, что означает, что ответ равен (x < 3) -x.

Ответ 29

Чтобы умножить два числа без оператора *:

int mul(int a,int b) {
    int result = 0;
    if(b > 0) {
        for(int i=1;i<=b;i++){
            result += a;
        }
    }
    return result;
}

Ответ 30

Уродливый, медленный и непроверенный, но...

int mult(a,b){
    int i, rv=0;
    for(i=0; i < 31; ++i){
        if(a & 1<<i){
            rv += b << i;
        }
    }
    if(a & 1<<31){ // two complement
        rv -= b<<31;
    }
    return rv;
}