如何在不使用“/”和“%”的情况下有效地获得商和余数？

Question

我实现了一个简单的函数，当除数是 的幂时，它返回商和余数10：

func getQuotientAndRemainder(num int64, digits uint) (int64, int64) {

    divisor := int64(math.Pow(10, float64(digits)))

    if num >= divisor {

        return num / divisor, num % divisor

    } else {

        return 0, num

    }

}

只是好奇，除了直接使用/和%运算符，有没有更好的算法来获得商和余数？还是仅在除数是 的幂的情况下10？

Answer 1

return num / divisor, num % divisor“算法”是健全的，并且可以说是最好的方式：富有表现力。如果有的话，这部分代码可能过于复杂：int64(math.Pow(10, float64(digits)))来回转换 float64可以说是次优的。此外，10 的任何大于 18 的幂都会溢出int64。我建议您添加健全性检查并用乘法循环替换代码并测量其性能。但是：如果您关心性能，只需在汇编中实现它。

Answer 2

显然，您应该运行一些 Go 基准测试：基准测试、包测试。您的解决方案看起来效率不高。试试这个：package mainimport "fmt"func pow(base, exp int64) int64 {    p := int64(1)    for exp > 0 {        if exp&1 != 0 {            p *= base        }        exp >>= 1        base *= base    }    return p}func divPow(n, base, exp int64) (q int64, r int64) {    p := pow(base, exp)    q = n / p    r = n - q*p    return q, r}func main() {    fmt.Println(divPow(42, 10, 1))    fmt.Println(divPow(-42, 10, 1))}输出：4 2-4 -2基准：BenchmarkDivPow                     20000000            77.4 ns/opBenchmarkGetQuotientAndRemainder     5000000           296 ns/op