不使用除法或乘法运算符除以 9

Question

这个问题我已经尝试解决了，但是没办法。任何指针将不胜感激。

做除法的常规减法方式不是这里的意图，使用移位运算符的巧妙方式来完成这个是意图。

Answer 1

这个 http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication 算法可以在 log(n) 时间内仅使用减法和二进制移位来完成。然而，据我所知，最先进的硬件已经使用了这个，甚至更好的算法。因此，我认为你无能为力（假设性能是你的目标），除非你能以某种方式完全避免除法或改变你的用例以便你可以除以 2 的幂，因为这些有一些技巧案例。

Answer 2

看到这个答案：

除了除数是 3 之外，正是您要查找的内容。

编辑：解释

我将用简单的 + 替换 add 函数，因为您正在寻找不使用 * 或 / 的解决方案。

在这个解释中，我们假设我们除以 3。

此外，我假设您知道如何将十进制转换为二进制，反之亦然。

int divideby3 (int num) {
    int sum = 0;
    while (num > 3) {
        sum += (num >> 2);
        num = (num >> 2) + (num & 3);
    }
    if (num == 3)
        sum += 1;
    return sum; 
}

此方法使用按位运算符：

按位与：&.
按位左移：<<。左移二进制值。
按位右移：>>。右移二进制值。
按位异或：^

第一个条件(num > 3)是这样的，因为除数是3。在你的情况下，除数是9，所以当你使用它时，条件必须是(num > 9)。

假设我们要除的数是6.

在二进制中，6表示为000110。

现在，我们进入while (num > 3)循环。第一条语句将 sum（初始化为 0）添加到 num >> 2.

num >> 2 的作用：

num in binary initially: 00000000 00000110

after bitwise shift: 00000000 00000001 i.e. 1 in decimal

sum加上num >> 2后就是1.

因为我们知道 num >> 2 等于 1，所以我们将其添加到 num & 3。

num in binary initially: 00000000 00000110

3 in binary: 00000000 00000011

对于表达式a & b的结果中的每个位位置，如果两个操作数都包含1，则该位为1，否则为0

result of num & 3: 00000000 00000010 i.e. 2 in decimal

num 在 num = (num >> 2) + (num & 3) 之后等于 1 + 2 = 3

现在，由于 num 等于 3，我们进入 if (num==3) 循环。

然后我们将总和加 1，然后 return 值。这个sum的值就是商。

正如预期的那样，值 returned 是 2。

希望这不是一个可怕的解释。

Answer 3

创建一个循环，每一步你都应该减去 N-9 .. 然后 (N-9)-9 .. 直到 N<9 OR N=0 并且每次减法你都计算步骤例如：36/9 36-9=27 cmpt (1) 27-9=18 cmpt(2) 18-9=9 cmpt(3) 9-9=0 cmpt (4)

所以36/9= 4

Answer 4

如果需要除以一个正数，可以使用如下函数：

unsigned int divideBy9(unsigned int num) 
{
    unsigned int result = 0;
    while (num >= 9)
    {
        result += 1;
        num -= 9;
    }
    return result;
}

如果是负数，可以用类似的方法。

希望对您有所帮助！

Answer 5

如果不允许 multiply/divide，您将剩下 addition/subtraction。除以一个数字表示除数包含被除数的次数。你可以在return中使用这个：你可以从原始值中减去多少次？

divisor = 85;
dividend = 9;
remaining = divisor;
result = 0;
while (remaining >= dividend)
{
    remaining -= dividend;
    result++;
}
std::cout << divisor << " / " << dividend << " = " << result;

Answer 6

这是一个深受 Hacker's Delight 启发的解决方案，它实际上只使用位移位：

def divu9(n):
    q = n - (n >> 3)
    q = q + (q >> 6)
    q = q + (q>>12) + (q>>24); q = q >> 3
    r = n - (((q << 2) << 1) + q)
    return q + ((r + 7) >> 4)
    #return q + (r > 8)

Answer 7

尽管答案已被接受，但我 post 还是物有所值。

更新。这是通过乘以一个循环二进制分数来实现的。十进制 1/9 = 0.1111111 循环。在二进制中，即 1/1001 = 0.000111000111000111 重复出现。

注意二进制乘法器以 6 位为一组，十进制 7 循环出现。所以我想在这里做的是将被除数乘以 7，将其右移 6 位，并将其添加到运行商。但是为了保持重要性，我在加法之后进行了移位，并在循环结束后将商q移位以正确对齐。

32 位的计算循环最多有 6 次迭代int（6 位 * 6 次移位 = 36 位）。

#include<stdio.h> int main(void) { unsigned x, y, q, d; int i, err = 0; for (x=1; x<100; x++) { // candidates q = 0; // quotient y = (x << 3) - x; // y = x * 7 while(y) { // until nothing significant q += y; // add (effectively) binary 0.000111 y >>= 6; // realign } q >>= 6; // align d = x / 9; // the true answer if (d != q) { printf ("%d / 9 = %d (%d)\n", x, q, d); // print any errors err++; } } printf ("Errors: %d\n", err); return 0; }

不幸的是，对于每一个 9 的倍数的候选者，这都失败了，因为舍入误差，原因与乘以小数 27 * 0.111111 = 2.999999 而不是 3 相同。所以我现在通过保留 4 使答案复杂化l.s。四舍五入的商位。结果是它适用于所有受前两个半字节限制的 int 值，一个用于 * 7，一个用于 * 16 重要性。

#include<stdio.h> int main(void) { unsigned x, y, q, d; int i, err = 0; for (x=1; x<0x00FFFFFF; x++) { q = 8; // quotient with (effectively) 0.5 for rounding y = (x << 3) - x; // y = x * 7 y <<= 4; // y *= 16 for rounding while(y) { // until nothing significant q += y; // add (effectively) binary 0.000111 y >>= 6; // realign } q >>= (4 + 6); // the 4 bits significance + recurrence d = x / 9; // the true answer if (d != q) { printf ("%d / 9 = %d (%d)\n", x, q, d); // print any errors err++; } } printf ("Errors: %d\n", err); return 0; }

不使用除法或乘法运算符除以 9

Divide by 9 without using division or multiplication operator

c

algorithm

math

multiplication

integer-division