2

我发现了很多关于按位除法的帖子，并且我完全了解大多数按位用法，但我想不出具体的除法。我想用所有可能的 2 的倍数来除一个给定的数字（比如说 100）（注意：我不想用 2 位倍数的幂来除！）
例如：100/2、100/4、100/ 6, 100/8, 100/10...100/100
我也知道，因为使用unsigned int答案将被四舍五入，例如 100/52=0 但这并不重要，因为我可以跳过这些答案或打印出来，没问题。我最关心的是如何除以 6 或 10 等（2 的倍数）。需要用 C 来完成，因为我可以设法将你给我的任何代码从 Java 转换为 C。

4

3 回答 3

2

根据除以 3 问题的公认解决方案所示的数学运算，您可以推导出除法算法的递归式：

计算(int)(X / Y)

  • 令 k 满足 2 k ≥ Y 和 2 k-1 < Y
    （注意，2 k = (1 << k)）
  • 令 d = 2 k - Y

  • 然后，如果 A = (int)(X / 2 k ) 且 B = X % 2 k，

    X = (1 << k) * A + B
  = (1 << k) * A - Y * A + Y * A + B
  = d * A + Y * A + B
  = Y * A + (d * A + B)

  • 因此，

    X/Y = A + (d * A + B)/Y

换句话说，

如果S(X, Y) := X/Y，那么S(X, Y) := A + S(d * A + B, Y)。

这种重复可以用一个简单的循环来实现。循环的停止条件是分子低于 2 k时。该函数divu实现递归，仅使用位运算符并使用无符号类型。数学运算的辅助函数未实现，但不应该太难（链接的答案add已经提供了完整的实现）。该rs()功能用于“右移”，它对unsigned输入进行符号扩展。该函数div是 的实际 API ，并在委托给 之前int检查除以零和负数。做 2 的补码否定。ydivunegate

static unsigned divu (unsigned x, unsigned y) {
    unsigned k = 0;
    unsigned pow2 = 0;
    unsigned mask = 0;
    unsigned diff = 0;
    unsigned sum = 0;
    while ((1 << k) < y) k = add(k, 1);
    pow2 = (1 << k);
    mask = sub(pow2, 1);
    diff = sub(pow2, y);
    while (x >= pow2) {
        sum = add(sum, rs(x, k));
        x = add(mul(diff, rs(x, k)), (x & mask));
    }
    if (x >= y) sum = add(sum, 1);
    return sum;
}

int div (int x, int y) {
    assert(y);
    if (y > 0) return divu(x, y);
    return negate(divu(x, negate(y)));
}

此实现取决于signed int使用 2 的补码。为了获得最大的可移植性，div应在调用divu. 然后，它应该将divu返回的结果从 2 的补码转换为原生签名表示。

于 2013-06-17T07:58:04.063 回答
0

以下代码适用于正数。当被除数或除数或两者都为负时，有标志来适当地改变答案的符号。

int divi(long long m, long long n)
{
    if(m==0 || n==0 || m<n)
        return 0;
    long long  a,b;
    int f=0;
    a=n;b=1;

    while(a<=m)
    {
        b = b<<1;
        a = a<<1;
        f=1;
    }

    if(f)
    {
        b = b>>1;
        a = a>>1;
    }

    b = b + divi(m-a,n);
    return b;
}
于 2014-01-25T23:15:24.237 回答
-1

/尽可能多地使用运算符进行整数除法。

例如，当你想将 100 除以 6 或 10 时，你应该写100/6or 100/10。当您提到按位除法时，您是（1）表示运算符的实现/还是（2）您指的是除以两个数字的幂。

对于 (1) 处理器应该有一个整数除法单元。如果不是，编译器应该提供一个好的实现。

对于 (2)，您可以使用100>>2而不是100/4. 如果分子在编译时已知，那么好的编译器应该自动使用移位指令。

于 2013-06-16T23:27:43.973 回答