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

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 main

import "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/op

BenchmarkGetQuotientAndRemainder     5000000           296 ns/op