我怎样才能执行乘法没有'*'运算符？

我正在学习一些基本的东西，我正在学习C.我遇到了一个问题，把数字乘以7而不使用*运算符。 基本上就是这样

(x << 3) - x; 

现在我知道基本的位操作操作，但是我不知道如何在不使用*运算符的情况下将数字乘以任何其他奇数。 有一个一般的algorithm呢？

Answer 1

想一想如何用铅笔和纸张在十进制中进行乘法：

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

乘法在二进制中是什么样的？

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

注意什么？ 与十进制乘法不同，在需要记住“时间表”的情况下，当以二进制相乘时，在将其写入列表加数之前，总是将其中一个乘以0或1。 没有时间表需要。 如果第二项的数字是1，则在第一项中添加。 如果它是0，你不。 还要注意加数是如何逐渐向左移动的。

如果您不确定这一点，请在纸上进行一些二进制乘法运算。 完成后，将结果转换回十进制，看看是否正确。 在你做了几个之后，我想你会明白如何使用移位和增加来实现二进制乘法。

Answer 2

每个人都忽略了明显的。 不涉及乘法：

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

Answer 3

一个整数左移乘以2，只要它不溢出。 一旦你接近，只要加上或减去。

Answer 4

这个问题说：

用*运算符乘以7

这不使用* ：

  number / (1 / 7) 

编辑：
这编译和工作正常在C：

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

Answer 5

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

你想没有*乘法，你知道了，朋友！

Answer 6

避免“*”运算符很容易：

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

看不到'*'。 当然，如果你想深入了解它的精神，你也可以使用可靠的老class和添加algorithm：

 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有光泽和新的时候，这样的代码被看作是真正的用途。

Answer 7

从math上讲，乘法分配加法。 基本上，这意味着：

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

一个类似的策略可以用在任何其他的整数上，不pipe是奇数还是偶数都没有区别。

Answer 8

它与x*8-x = x*(8-1) = x*7

Answer 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 

Answer 10

当涉及到它时，乘以一个正整数可以这样做：

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

高效？ 几乎不。 但是这是正确的（考虑到整数限制等等）。

所以使用左移仅仅是乘以2的一个捷径。但是一旦你达到了2的最高次幂，你只需要添加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次。

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

上面的代码应该是不言自明的，因为我试图尽可能地简单。 它应该或多或less地工作于CPU可能执行这些操作的方式。 我知道的唯一的错误是不允许大于32,767和b不允许大到足以溢出（也就是说，不处理乘法溢出，所以64位结果是不可能的） 。 它甚至应该使用负数，只要input正确reinterpret_cast<> 。

Answer 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，则产品= a。

如果b是偶数：
ab可以写成2a（b / 2）
2a（b / 2）=（a + a） （b / 2）=（a + a） （b >> 1）其中'>>'java中的math右移运算符。

如果b是奇数：
ab可以写成a + a（b-1）
一个+ 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））
注意：每个recursion调用b被减半=> O（log（b））

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

Answer 14

@王，这是一个很好的概括。 但是这是一个稍快的版本。 但它假定没有溢出，而且是非负的。

 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，可能会更快。

Answer 15

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

Answer 16

当被乘数为负数时，Shift和Add不起作用（即使有符号扩展）。 带符号的乘法必须使用展位编码完成：

从LSB开始，从0到1的变化是-1; 从1到0的变化是1，否则是0. LSB下面还有一个隐含的附加位0。

例如，编号5（0101）将被编码为：（1）（ – 1）（1）（ – 1）。 你可以validation这是正确的：

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

该algorithm也适用于2的补码forms的负数：

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

Answer 17

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

我避免了标志位，因为它不是post的主题。 这是韦恩·康拉德基本上所说的实现。 这里还有一个问题就是你想要尝试更低层次的math运算。 欧拉计划很酷！

Answer 18

如果你可以使用日志function：

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

如果你不能使用日志function：

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

Answer 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 

使用recursion的示例实现：

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

我在上次面试中得到了这个问题，这个答案被接受了。

编辑：正数的解决scheme

Answer 20

这是正数的最简单的C99 / C11解决scheme：

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

Answer 21

另外一个思考 – 外面的答案：

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

Answer 22

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

Answer 23

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

Answer 24

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

Answer 25

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

Answer 26

循环它。 运行一个循环七次，迭代你乘以七的数字。

伪代码：

 total = 0 multiply = 34 loop while i < 7 total = total + multiply endloop 

Answer 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 

我在这里find这个描述http://www.techcrashcourse.com/2016/02/c-program-to-multiply-number-by-7-bitwise-operator.html

希望能帮助到你。

Answer 28

很简单，朋友…每次当你左移一个数字，这意味着你乘以2，这意味着答案是（X << 3）-x。

Answer 29

不带*运算符的两个数相乘：

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

Answer 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's complement rv -= b<<31; } return rv; }