有效地计算整数除法的底数

Question

如何在 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
}

（也上playground）。有没有更好的方法？

Answer 1

将整数转换为 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

这表明它非常快，我们只是在对循环进行基准测试。这不太可能成为瓶颈，我会建议最简单的选择。

Answer 2

这里是你的朋友 - 我会反对将两个整数转换为双精度数并使用 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
}

Bit-twiddling 让我们可以很容易地识别两个's-complement 整数的符号：

一个二s-complement整数可能包含的最小[负]值设置了符号位，其余位全部清除(0x80000000)。
整数值与最小值的按位与运算得到 0 或该整数类型可能包含的最小值：
- 5 & math.MinInt 产生 0
- 0 & math.MinInt 产生 0
- -5 & Math.MinInt 产生 math.MinInt

这让我们可以这样做：

计算 x / y 的商和余数。
如果余数为零，则商为⌊ x / y ⌋。
否则(余数为non-zero),
1. 如果符号位不同，则商为负，我们必须从商中减去 1 以得到 ⌊ x / y ⌋。
2. 符号位相同则商为正商是 ⌊ x / y ⌋.

Click here for the Go Playground

x 的结果使得 -10 ≤ x ≤ +10，并且 y = 3：

X	Y	⌊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 倍。

[这是否重要完全取决于用例。]

基准代码每次循环迭代调用被基准测试的函数 21 次（包括 -10 到 +10），因此循环代码的成本不会掩盖被基准测试的函数。

❯ 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)
  }
}

Answer 3

如果乘以数字 (a*b) 的基准会更快：-

func floorDivMustafa2(a, b int) int {

    if a%b != 0 && a*b < 0 {
        return a/b - 1
    }
    return a / b
}

我尝试了 Xor 方法，但速度较慢：

//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 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)
            }
        }
    }
}

bench-mark方法：

func BenchmarkFloorDivMustafa2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for a := -100; a < 100; a++ {
            for b := -100; b < 100; b++ {
                if b == 0 {
                    continue
                }
                _ = floorDivMustafa2(a, b)

            }
        }
    }
}

所有输出：

>>>go test -bench=^Benchmark  -benchtime=1000x

BenchmarkSchwern-4                  1000            182345 ns/op
BenchmarkFloorDivMustafa-4          1000            441682 ns/op
BenchmarkFloorDivMustafa2-4         1000             31234 ns/op
BenchmarkJochen-4                   1000             60315 ns/op
BenchmarkIntfolurdiv-4              1000          26437611 ns/op
BenchmarkFloorDivICza-4             1000          26406776 ns/op

编辑在我的基准测试中看到 Bit twiddling 变慢的结果后，我尝试了 op 的 bench 方法，这是我的结果：

BenchmarkTwentyNumberBitwise-4                    328639            113790 ns/op
BenchmarkTwentyNumberMultiplication-4             295512            101345 ns/op

有效地计算整数除法的底数

compute the floor of an integer division efficiently

go

integer-division

基准

X	Y	⌊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

X	Y	⌊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

X	Y	⌊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