首页 文章

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

提问于
浏览 次
0

我已经实现了一个简单的函数，当除数是 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 的幂的情况下？

algorithm math go

2 回答

  • 1
    return num / divisor, num % divisor

    “算法”是合理的，可以说是最好的方式：表达 . 如果有的话，这部分代码可能过于复杂：

    int64(math.Pow(10, float64(digits)))

    转换为 float64 可以说是次优的 . 此外，任何大于18的幂的10将溢出 int64 . 我建议你添加一个完整性检查并用乘法循环替换代码并测量其性能 .

    但那么：如果你关心性能，那就在装配中实现它 .

    回复于
  • 1

    显然，你应该运行一些Go基准：Benchmarks, Package testing .

    您的解决方案看起来效率不高 . 试试这个：

    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
    回复于

相关问题