'*' 연산자 없이 곱셈을 수행하려면 어떻게 해야 합니까?

'*' 연산자 없이 곱셈을 수행하려면 어떻게 해야 합니까?

저는 C를 배우면서 몇 가지 기본적인 것들을 공부하고 있었습니다.* 연산자를 사용하지 않고 숫자에 7을 곱하는 문제가 발생했습니다.기본적으로 이렇습니다.

      (x << 3) - x;

이제 기본적인 비트 조작 작업에 대해 알고 있지만 * 연산자를 사용하지 않고 어떻게 다른 홀수를 곱하는지 알 수 없습니다.이것에 대한 일반적인 알고리즘이 있습니까?

연필과 종이를 사용하여 십진법으로 곱하는 방법을 생각해 보십시오.

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

이진법에서 곱셈은 어떻게 보입니까?

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

뭔가 눈치채셨나요?"시간표"를 기억해야 하는 십진수의 곱셈과 달리 이진법으로 곱셈할 때는 항상 용어 중 하나에 0 또는 1을 곱한 후에 목록에 추가합니다.시간표가 필요 없습니다.두 번째 항의 숫자가 1이면 첫 번째 항에 추가합니다.0이면 안 됩니다.또한 추가가 왼쪽으로 점진적으로 이동하는 방식도 확인할 수 있습니다.

이에 대해 잘 모르면 종이에 몇 개의 이진 곱셈을 수행합니다.작업이 완료되면 결과를 십진수로 다시 변환하고 정확한지 확인합니다.몇 가지 작업을 마치면 시프트와 추가를 사용하여 이진 곱셈을 구현하는 방법에 대한 아이디어를 얻을 수 있을 것입니다.

모든 사람들이 명백한 것을 간과하고 있습니다.곱셈은 포함되지 않습니다.

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

질문은 다음과 같습니다.

* 연산자를 사용하지 않고 숫자에 7을 곱합니다.

이것은 사용되지 않습니다.*:

 number / (1 / 7) 

은 C 것은에 C: 서컴되작동다니합고일에서 잘 합니다.

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

정수 왼쪽 이동은 오버플로가 발생하지 않는 한 2를 곱합니다.가까이 가면 적당히 더하거나 빼세요.

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

고객이 필요로 하는 곱셈은*알았어, 친구!

'*' 연산자는 쉽게 피할 수 있습니다.

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이 반짝이고 새로워졌을 때 이와 같은 코드가 실제로 사용되었습니다.

수학적으로, 곱셈은 덧셈보다 더 많이 분포합니다.기본적으로 이는 다음을 의미합니다.

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

에는 임의당실수경우의신의당()경우▁any▁(▁real7), , , , 될 수 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

유사한 전략을 다른 정수에 사용할 수 있으며 홀수든 짝수든 아무런 차이가 없습니다.

은 과 같습니다.x*8-x = x*(8-1) = x*7

홀수 또는 짝수에 관계없이 임의의 숫자는 2의 거듭제곱의 합으로 표현할 수 있습니다.예를들면,

     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

다음과 같이 양의 정수를 곱할 수 있습니다.

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

효율성?전혀.하지만 정확합니다(int 등의 한계를 고려).

따라서 왼쪽 시프트를 사용하는 것은 2를 곱하는 지름길입니다.이 의일만단 2고최제도달면하에서곱아에서 2의 거듭제곱에 하면, 래에지하.b추가만 하면 됩니다.a so: 요한횟수필서, 라따::

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세 번.

어느 날 저녁, 저는 제가 극도로 지루하다는 것을 알게 되었고, 이것을 요리했습니다.

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

위의 코드는 제가 최대한 단순하게 유지하려고 노력했기 때문에 상당히 자명해야 합니다.CPU가 이러한 작업을 수행하는 방식으로 작동해야 합니다.내가 아는 유일한 버그는a 및 32,767보다 클 수.b 오버플로가 발생할 로 큰 은 허용되지 않습니다.a(즉, 다중 오버플로는 처리되지 않으므로 64비트 결과는 불가능합니다.).reinterpret_cast<>.

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입니다.
, 곱a.b=1인 경우, 곱 =a.

짝수인 :b 짝 수인경우가:경:
ab은 2a(b/2)로 작성할 수 있습니다.
2a(b/2)=(a+a)(b/2)=(a+a)(b>>1) 여기서 '>'는 자바의 산술 우 이동 연산자입니다.

b가 홀수인 경우:
ab은 a+a(b-1)로 쓸 수 있습니다.
a+a(b-1)=a+2a(b-1)/2=a+(a+a)(b-1)/2=a+(a+a)((b-1)>1)
b가 홀수(b-1)/2=b/2=b>>1이므로
그래서 ab=a+(2a*(b>>1)
참고: 각 재귀 호출 b는 절반으로 줄어듭니다. => O(log(b))

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

@왕, 그것은 좋은 일반화입니다.하지만 여기 조금 더 빠른 버전이 있습니다.그러나 오버플로가 없다고 가정하고 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를 교환하면 더 빠를 수 있습니다.

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

다중 랜드가 음수일 때 시프트 및 추가가 작동하지 않습니다(부호 확장을 사용하더라도).서명된 곱셈은 부스 인코딩을 사용하여 수행해야 합니다.

LSB부터 시작하여 0에서 1로의 변화는 -1이고, 1에서 0으로의 변화는 1이고, 그렇지 않으면 0입니다.LSB 아래에는 암시적 추가 비트 0도 있습니다.

예를 들어, 숫자 5(0101)는 (1)(-1)(-1)(-1)로 인코딩됩니다.이 값이 올바른지 확인할 수 있습니다.

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

이 알고리즘은 2의 보어 형태의 음수에서도 작동합니다.

-1 in 4-bit 2의 보어는 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;
}

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

저는 게시물의 주제가 아니기 때문에 표지판을 살짝 피했습니다.이것은 웨인 콘래드가 기본적으로 말한 것의 구현입니다.또 다른 문제는 낮은 수준의 수학 연산을 더 시도하려는 것입니다.오일러 프로젝트는 멋집니다!

로그 기능을 사용할 수 있는 경우:

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

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

JAVA:
모든 숫자를 2의 거듭제곱으로 나눌 수 있다는 사실을 고려하면,

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

지난 취업 면접에서 이런 질문을 받았는데 이 답변이 받아들여졌습니다.

편집: 양수에 대한 솔루션

다음은 양수에 대한 가장 간단한 C99/C11 솔루션입니다.

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

또 다른 독창적인 대답은 다음과 같습니다.

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

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

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

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

반복해요.루프를 7번 실행하고 곱하는 숫자에 7을 반복합니다.

의사 코드:

total = 0
multiply = 34

loop while i < 7

    total = total + multiply

endloop

양수에 대한 JavaScript 접근법

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

우리가 사용하는 일반적인 곱셈 방법에 대해 생각해 보세요.

         1101 x        =>13
         0101          =>5
---------------------
         1101
        0000
       1101
      0000
===================        
      1000001 .        => 65

코드에 위와 동일한 내용을 적는 것.

#include<stdio.h>

int multiply(int a, int b){
    int res = 0,count =0;
    while(b>0) {
        if(b & 0x1)
            res = res + (a << count);
        b = b>>1;
        count++;
    }
    return res;
}
int main() {
    printf("Sum of x+y = %d", multiply(5,10));
    return 0;
}

아주 간단해, 친구...숫자를 이동할 때마다 숫자에 2를 곱한다는 의미이며, 이는 (x<3)-x라는 의미입니다.

를 사용하지 않고 두 숫자를 곱하는 방법*연산자:

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

언급URL : https://stackoverflow.com/questions/2069488/how-can-i-perform-multiplication-without-the-operator