两个数之间的乘法

Question

我有一个任务要构建一个函数，该函数将 2 个整数相乘且不使用 * 或“-”。我只能使用'+''/'和'%'。

我注意到很多人都在使用移位方法，但我不能没有，因为我们还没有学会它。

尽管我可以在没有 1 个 while 循环的情况下轻松做到这一点，但诀窍是它应该在 n log n 或 log n 运行时效率。

虽然我没有看到任何使用它们的方式，但也没有列出任何数组。

有什么可行的方法吗？？？

Answer 1

根据 Ian Abbot 在此处给出的评论是实现目标的无耻方式：

double Multiply(int n, double x) {
    if (n == 0) return 0.0;
    else return x / (1.0 / n);
}

或者，如果您想要更简洁的单行代码：

double Multiply(int n, double x) { return n ? x / (1.0 / n) : 0.0; }

Ian 的 'answer' 的一个变化（但是，恕我直言，一个 重要的 变化）是 int 参数被检查为零，因为这比尝试测试 double（或 float）的精确零要可靠得多。

注意：原始问题指定的数字是"integer and double,"，我相应地给出了这个答案。

Answer 2

这个算法是O(log n)。分而治之。

double Multiply(int n, double x) {
    if (n == 0) 
        return 0.0;
    if (n == 1)
        return x;
    double a = Multiply(n/2, x);
    if ((n%2) == 1)
        return x + a + a;
    return a + a;
}

注意：代码未经测试。我无法在 iPad.

上编译 C 代码

Answer 3

这是另一个符合 OP 要求的没有递归性的快速而肮脏的解决方案：

int Multiply(int a, int b)
{
  int result = 0;
  while (b > 0)
  {
    if (b % 2 != 0)
      result += a;

    a += a;
    b /= 2;
  }
  return result;
}

基本上和chmike回答的算法一样。

我没有在意复杂性，但它看起来很像一些 O(log n)。

它绝对不适用于 b 的负值，我将修复它作为练习。

Answer 4

只是为了扩展 Jabberwocky 的答案（OP 应该完全接受），这里有几种处理负数的方法。

如果需要获得正确的结果符号，第一种方法通过在主循环之前使用 - 来作弊：

int Multiply(int a, int b)
{
  int result = 0;
  if (b < 0)
    a = -a; /* Cheat! But at least its a unary operation. */
  while (b != 0)
  {
    if (b % 2 != 0)
      result += a;

    a += a;
    b /= 2;
  }
  return result;
}

第二种方法利用unsigned int进行2的补码运算。从技术上讲，这有一个小问题，因为根据 C 标准规则，正确的否定结果可能会被实现定义的结果替换。无论如何，在大多数以 2 的补码表示有符号整数的实现中，这不太可能成为问题。

int Multiply(int a_, int b_)
{
  unsigned int a = a_;
  unsigned int b = b_;
  unsigned int result = 0;
  while (b != 0)
  {
    if (b % 2 != 0)
      result += a;

    a += a;
    b /= 2;
  }
  // N.B. negative result might be replaced with implementation-defined result!
  return (int)result;
}

旁白：忽略有符号整数的处理，这种乘法也称为 Russian peasant method。

Answer 5

这是另一种使用移位和加法的方法。它与其他一些答案有很多共同之处，但尽可能使用按位运算，并且处理负数的方式略有不同（它也避免了 Ian Abbot 承认的 "unary minus" 可能是 'cheat'）：

int mult(int a, int b)
{
    int answer = 0;
    int minus = 0;
    if (a < 0) {
        minus ^= 1;
        a ^= -1; ++a; // Negate (without using *) - assuming 2s complement representation ...
    }
    if (b < 0) {
        minus ^= 1;
        b ^= -1; ++b; // ... where "-x" is the BIT INVERSE of "x" PLUS ONE
    }
    while (a) {
        if (a & 1) answer += b; // If the nth bit of "a" is set we add "b << n"
        b <<= 1; // But shift up (multiply by 2)
        a >>= 1; // Bit shift down (divide by 2)
    }
    if (minus) { // ONE (and only ONE) number was negative ...
        answer ^= -1; ++answer; // ... so we negate our answer!
    }
    return answer;
}

这将适用于负数（一个或两个），但不会处理整数溢出（但是，本机 z = x * y 也不会这样做） .

请随时要求进一步澄清and/or解释。

两个数之间的乘法

Multiplication between two numbers

c

multiplication