在 o(1) 中实现 c 二进制除法

Question

我找到了这个（稍作修改的）代码来实现无符号数的除法：

#include <climits>
#include <stdio.h>



unsigned divide(unsigned dividend, unsigned divisor) { 


    unsigned current = 1;
    unsigned answer=0;

    if ( divisor > dividend) 
        return 0;

    if ( divisor == dividend)
        return 1;

    while (divisor <= dividend) {   // this will not work with UINT_MAX
        divisor <<= 1;
        current <<= 1;
    }

    divisor >>= 1;
    current >>= 1;

    while (current!=0) {
        if ( dividend >= divisor) {
            dividend -= divisor;
            answer |= current;
        }
        current >>= 1;
        divisor >>= 1;
    }    
    return answer;
}
int main()
{
    unsigned int x =0;
    x = divide (UINT_MAX,113);
    printf ("%u",x);

    return 0;
}

它适用于 "normal" 值，但除以最大 unsigned int 值会产生问题；因为它是 Oxffffffff，所以不可能将 divisor 移动到足以使其变大的程度 - 任何进一步的移动都会将除数推到 32 位限制之上并破坏创建无限循环的值。我可以得到有关如何修复此错误的建议吗？甚至可能创建一个硬代码案例？

Answer 1

而不是

while (divisor <= dividend) {   // this will not work with UINT_MAX
    divisor <<= 1;
    current <<= 1;
}

divisor >>= 1;
current >>= 1;

尝试

unsigned k = 1 << (sizeof(unsigned) * 8 - 1);
while (((divisor & k) == 0) && ((divisor << 1) <= dividend)) {
    divisor <<= 1;
    current <<= 1;
}

这个想法是，在建议的算法中，divisor 和 current 的最后左移由稍后的右移补偿。所以我们可能一开始就避免它。

Answer 2

另一种解决方案是使用无符号长整数。

在 o(1) 中实现 c 二进制除法

Implementing c binary division in o(1)

c

binary

division