英文:
How to get the quotient and remainder effectively without using "/" and "%"?
问题
我已经实现了一个简单的函数，当除数是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的幂的情况下才适用？
英文:
I have implemented a simple function which returns the quotient and remainder when the divisor is the power of 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
}
}
Just curious, except using directly / and % operators, is there any better algorithm to get the the quotient and remainder? Or only in the case when the divisor is the power of 10?
答案1
得分: 1
返回 num / divisor, num % divisor
“算法”是可靠的，并且以一种可以说是最好的方式编写：表达性强。如果有什么问题，可能是你的代码这部分过于复杂：
int64(math.Pow(10, float64(digits)))
转换为和从 `float64` 的类型可能不是最佳选择。而且，10 的任何大于 18 的次方都会导致 `int64` 溢出。我建议你添加一个合理性检查，并用一个乘法循环替换这段代码，并测量其性能。
但是，如果性能是你关心的问题，那就直接用汇编语言实现吧。
英文:
return num / divisor, num % divisor
The "algorithm" is sound and written in arguably the best way possible: expressively. If anything, this part of your code may be overly complicated:
int64(math.Pow(10, float64(digits)))
Converting to and from float64 is arguably sub-optimal. Also, 10 to the power of anything greater than 18 will overflow int64. I suggest you add a sanity check and replace the code with a multiplying loop and measure its performance.
But then: if performance is your concern, just implement it in assembly.
答案2
得分: 1
显然，你应该运行一些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
英文:
Obviously, you should run some Go benchmarks: Benchmarks, Package testing.
Your solution doesn't look very efficient. Try this:
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))
}
Output:
4 2
-4 -2
Benchmark:
BenchmarkDivPow 20000000 77.4 ns/op
BenchmarkGetQuotientAndRemainder 5000000 296 ns/op
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论