除10运算的快速算法

大家好，欢迎来到IT知识分享网。

例如A/10，原本打算通过位操作，进行除10运算，但后来发现通过简单的移位基本上无法实现除10操作。

在一番搜索之后，发现了两个比较好的解决方法：

1.通过乘以2^32/10的值429496729.6，十六进制表示为19999999.99999999A，取整为1999999A，然后再右移32位，达到误差基本可以忽略的一种快速计算。

本方法假定了是32位的机器，故64位机器需要自己修改代码。（代码在AnycodeX在线编译器测试）

int32_t div10(int32_t dividend)
{
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

2.完全通过移位操作实现（ 代码在AnycodeX在线编译器测试）

unsigned divu10(unsigned n) {
    unsigned q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n - (((q << 2) + q) << 1);
    return q + (r > 9);
}

关于移位操作实现更多的除法等的快速算法可以参考 Hacker’s Delight的文章