如何有效地計算兩個整數的商，在 Go 中向下舍入（而不是向零）？以下代碼似乎給出了正確的結果，但看起來笨拙且效率低下：
func floorDiv(a, b int) int {
if b < 0 {
a, b = -a, -b
}
r := a % b
if r < 0 {
r = b
}
return (a - r) / b
}
（也在操場上）。有沒有更好的辦法？
uj5u.com熱心網友回復：
將整數轉換為 float64、除法并使用math.Floor.
func floorDiv(a, b int) int {
return int(math.Floor(float64(a)/float64(b)))
}
基準測驗顯示它們幾乎在同一時間運行，并且與簡單的添加功能相同。
func BenchmarkFloorDiv(b *testing.B) {
for i := 0; i < b.N; i {
_ = floorDiv(i, 3)
}
}
func BenchmarkFloorDivGo(b *testing.B) {
for i := 0; i < b.N; i {
_ = floorDivGo(i, 3)
}
}
func BenchmarkFloorAdd(b *testing.B) {
for i := 0; i < b.N; i {
_ = add(i, 3)
}
}
goos: darwin
goarch: amd64
pkg: github.com/my/repo/test_go
cpu: Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz
BenchmarkFloorDiv-8 1000000000 0.2612 ns/op
BenchmarkFloorDivGo-8 1000000000 0.2610 ns/op
BenchmarkFloorAdd-8 1000000000 0.2565 ns/op
PASS
ok github.com/my/repo/test_go 1.000s
這表明它是如此之快，我們只是在對回圈進行基準測驗。它不太可能成為瓶頸，我會建議最簡單的選擇。
uj5u.com熱心網友回復：
Bit twiddling 是你的朋友——我會反對將兩個整數轉換為雙精度數并使用math.Floor().
func IntFloorDiv(x int, y int) int {
q := x / y
r := x % y
if r != 0 && x&math.MinInt != y&math.MinInt {
q -= 1
}
return q
}
位旋轉使我們能夠輕松識別二進制補碼整數的符號：
二進制補碼整數可能包含的最小 [負] 值設定了符號位，其余位全部清除 (
0x80000000)。一個整數值與該最小值的按位與給我們 0 或該整數型別可能包含的最小值：
5 & math.MinInt產量 00 & math.MinInt產量 0-5 & Math.MinInt產量math.MinInt
這讓我們可以這樣做：
計算 的商和余數
x / y。如果余數為零，則商為? x / y ?。
否則（余數非零），
- 如果符號位不同，則商為負，我們必須從商中減去 1 以得到 ? x / y ?。
- 如果符號位相同，則商為正且商為? x / y ?。
點擊此處前往 Go Playground
滿足x-10 ≤ x≤ 10 和y= 3 的結果：
| X | 是 | ?X÷Y? |
|---|---|---|
| -10 | 3 | -4 |
| -9 | 3 | -3 |
| -8 | 3 | -3 |
| -7 | 3 | -3 |
| -6 | 3 | -2 |
| -5 | 3 | -2 |
| -4 | 3 | -2 |
| -3 | 3 | -1 |
| -2 | 3 | -1 |
| -1 | 3 | -1 |
| 0 | 3 | 0 |
| 1 | 3 | 0 |
| 2 | 3 | 0 |
| 3 | 3 | 1 |
| 4 | 3 | 1 |
| 5 | 3 | 1 |
| 6 | 3 | 2 |
| 7 | 3 | 2 |
| 8 | 3 | 2 |
| 9 | 3 | 3 |
| 10 | 3 | 3 |
基準
5 次不同運行的基準時間表明，轉換為浮點數和使用math.Floor()比整數除法和位旋轉慢近 21 倍。
[這是否真正重要完全取決于用例。]
基準代碼在每次回圈迭代（包括 -10 到 10）呼叫 21 倍的基準測驗函式，因此回圈代碼的成本不會掩蓋被基準測驗的函式。
? go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8 1000000000 0.2730 ns/op
Benchmark_floorDiv_Math-8 189576496 5.969 ns/op
PASS
ok foobar.com/floordiv 2.266s
? go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8 1000000000 0.2718 ns/op
Benchmark_floorDiv_Math-8 196402200 5.954 ns/op
PASS
ok foobar.com/floordiv 2.243s
? go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8 1000000000 0.2756 ns/op
Benchmark_floorDiv_Math-8 200432154 5.976 ns/op
PASS
ok foobar.com/floordiv 2.271s
? go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8 1000000000 0.2814 ns/op
Benchmark_floorDiv_Math-8 195009298 6.083 ns/op
PASS
ok foobar.com/floordiv 2.314s
? go test -bench=.
goos: darwin
goarch: amd64
pkg: foobar.com/floordiv
cpu: Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz
Benchmark_floorDiv_Int-8 1000000000 0.2751 ns/op
Benchmark_floorDiv_Math-8 201196482 6.033 ns/op
PASS
ok foobar.com/floordiv 2.290s
運行這個基準：
package main
import (
"math"
"testing"
)
func floorDiv_Int(x int, y int) int {
q := x / y
r := x % y
if r != 0 && x&math.MinInt != y&math.MinInt {
q -= 1
}
return q
}
func floorDiv_Math(x int, y int) int {
return int(math.Floor(
float64(x) / float64(y),
))
}
func Benchmark_floorDiv_Int(b *testing.B) {
for i := 0; i < b.N; i {
floorDiv_Int(-10, 3)
floorDiv_Int(-9, 3)
floorDiv_Int(-8, 3)
floorDiv_Int(-7, 3)
floorDiv_Int(-6, 3)
floorDiv_Int(-5, 3)
floorDiv_Int(-4, 3)
floorDiv_Int(-3, 3)
floorDiv_Int(-2, 3)
floorDiv_Int(-1, 3)
floorDiv_Int(0, 3)
floorDiv_Int(1, 3)
floorDiv_Int(2, 3)
floorDiv_Int(3, 3)
floorDiv_Int(4, 3)
floorDiv_Int(5, 3)
floorDiv_Int(6, 3)
floorDiv_Int(7, 3)
floorDiv_Int(8, 3)
floorDiv_Int(9, 3)
floorDiv_Int(10, 3)
}
}
func Benchmark_floorDiv_Math(b *testing.B) {
for i := 0; i < b.N; i {
floorDiv_Math(-10, 3)
floorDiv_Math(-9, 3)
floorDiv_Math(-8, 3)
floorDiv_Math(-7, 3)
floorDiv_Math(-6, 3)
floorDiv_Math(-5, 3)
floorDiv_Math(-4, 3)
floorDiv_Math(-3, 3)
floorDiv_Math(-2, 3)
floorDiv_Math(-1, 3)
floorDiv_Math(0, 3)
floorDiv_Math(1, 3)
floorDiv_Math(2, 3)
floorDiv_Math(3, 3)
floorDiv_Math(4, 3)
floorDiv_Math(5, 3)
floorDiv_Math(6, 3)
floorDiv_Math(7, 3)
floorDiv_Math(8, 3)
floorDiv_Math(9, 3)
floorDiv_Math(10, 3)
}
}
uj5u.com熱心網友回復：
不如@Nicholas Carey 或@icza 快我嘗試了xor 方法和multiply 方法：
//xor method
func floorDivMustafa(a, b int) int {
if a%b != 0 && (a < 0 || b < 0) && !(a < 0 && b < 0) {
return a/b - 1
}
return a / b
}
要么
func floorDivMustafa2(a, b int) int {
if a%b != 0 && a*b < 0 {
return a/b - 1
}
return a / b
}
這是我的單元測驗方法
func Test_floorDivSchwern(t *testing.T) {
var (
got, want int
)
for a := -10; a < 10; a {
for b := -10; b < 10; b {
if b == 0 {
continue
}
got = floorDivMustafa(a, b)
want = floorDivSchwern(a, b)
if got != want {
t.Errorf("divRound(%v/%v) = %v, want %v", a, b, got, want)
}
}
}
}
基準法：
func BenchmarkMustafa(b *testing.B) {
for i := 0; i < b.N; i {
for a := 0; a < 1000; a {
for b := -1000; b < 1000; b {
if a == -100 || b == 0 {
continue
}
_ = floorDivMustafa(a, b)
}
}
}
}
以及所有人的輸出：
goos: windows
goarch: amd64
pkg: rounint
cpu: Intel(R) Core(TM) i7-4510U CPU @ 2.00GHz
BenchmarkSchwern
BenchmarkSchwern-4 1159 950888 ns/op
BenchmarkMustafa
BenchmarkMustafa-4 994 1048233 ns/op
BenchmarkFloorDivMustafa2
BenchmarkFloorDivMustafa2-4 1250 1185158 ns/op
BenchmarkJochen
BenchmarkJochen-4 6985 207090 ns/op
BenchmarkIntfolurdiv
BenchmarkIntfolurdiv-4 100 10735139 ns/op
BenchmarkFloorDivICza
BenchmarkFloorDivICza-4 100 10229135 ns/op
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/439703.html