当前位置： 文江博客话题详情

有效计算整数除法的下限

发布于 2025-01-12 17:22:14 字数 364 浏览 1 评论 0原文

如何在 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< /a>）。有更好的办法吗？

原文

How can I efficiently compute the quotient of two integers, rounded down (not towards zero) in Go? The following code seems to give the correct result, but looks awkward and inefficient:

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
}

(also on the playground). Is there a better way?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（3）

只涨不跌 2025-01-19 17:22:14

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

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

Convert the integers to float64, divide, and use math.Floor.

func floorDiv(a, b int) int {
  return int(math.Floor(float64(a)/float64(b)))
}

Benchmarking shows they run in about the same time, and the same as a simple add function.

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

This suggests it's so fast we're just benchmarking the loop. It is unlikely to be a bottleneck, I would suggest the simplest option.

回复 原文
渔村楼浪 2025-01-19 17:22:14

位旋转是你的朋友 - 我将把它反对将两个整数转换为双精度并使用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 产生 0
    • <代码>0 & math.MinInt 产生 0
    • <代码>-5 & Math.MinInt 产生 math.MinInt

这让我们可以这样做：

  1. 计算 x / y 的商和余数。

  2. 如果余数为零，则商为 ⌊ x / y ⌋。

  3. 否则（余数非零），

    1. 如果符号位不同，则商为负且
      我们必须从商中减去 1 才能得到 ⌊ x / y ⌋。
    2. 如果符号位相同，则商为正，
      商为 ⌊ x / y ⌋。

单击此处查看 Go Playground

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

XY⌊X÷Y⌋
-103-4
-93-3
-83-3
-73-3
-63-2
-53-2
-43-2
-33-1
-23-1
-13-1
030
130
230
331
431
531
632
732
832
933
1033

基准

基准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)
  }
}

Bit twiddling is your friend here — I'll put this up against converting two integers to doubles and using 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 allows us to easily identify the sign of a two's-complement integer:

  • The smallest [negative] value that a two's-complement integer may contain has the sign bit set and the remaining bits all clear (0x80000000).

  • A bitwise AND of an integer value against that smallest value gives us either 0 or the smallest value that that integer type may contain:

    • 5 & math.MinInt yields 0
    • 0 & math.MinInt yields 0
    • -5 & Math.MinInt yields math.MinInt

That lets us do this:

  1. Compute the quotient and remainder for x / y.

  2. If the remainder is zero, the quotient is ⌊ x / y ⌋.

  3. Otherwise (the remainder is non-zero),

    1. If the sign bits differ, the quotient is negative and
      we must subtract 1 from the quotient to yield ⌊ x / y ⌋.
    2. if the sign bits are identical, the quotient is positive and
      the quotient is ⌊ x / y ⌋.

Click here for the Go Playground

Results for x such that -10 ≤ x ≤ +10, and y = 3:

XY⌊X÷Y⌋
-103-4
-93-3
-83-3
-73-3
-63-2
-53-2
-43-2
-33-1
-23-1
-13-1
030
130
230
331
431
531
632
732
832
933
1033

Benchmarks

Benchmark timings across 5 different runs show that converting to float and using math.Floor() to be nearly 21x slower than integer division and bit twiddling.

[Whether or not that actually matters is entirely dependent on the use case.]

The benchmark code calls the function being benchmarked 21x per loop iteration (for -10 to +10 inclusive) so the cost of the loop code doesn't mask the function being benchmarked.

❯ 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

running this benchmark:

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)
  }
}
回复 原文
诗化ㄋ丶相逢 2025-01-19 17:22:14

乘数（a * b）的情况下的基准会更快：-

func floorDivMustafa2(a, b int) int {

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

我尝试了异或方法，但它更慢：

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

基准方法：

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

编辑

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

The benchmark in case multiply numbers (a*b) will be faster:-

func floorDivMustafa2(a, b int) int {

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

I tried the Xor method but it is slower:

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

this is my unit test method

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

the bench-mark method:

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)

            }
        }
    }
}

and the output for all:

>>>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

Edit after I saw the result of Bit twiddling slower in my benchmark I try the bench method of the op and this is my result:

BenchmarkTwentyNumberBitwise-4                    328639            113790 ns/op
BenchmarkTwentyNumberMultiplication-4             295512            101345 ns/op
回复 原文
~没有更多了~

关于作者

终陌

暂无简介

文章
评论
683 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

╰ゝ天使的微笑

文章 0 评论 0

少女净妖师

文章 0 评论 0

朱洁

文章 0 评论 0

觉浅

文章 0 评论 0

滥情空心

文章 0 评论 0

hl1314520

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文