compute the floor of an integer division efficiently

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?

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.

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:

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

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