From 177dfba1120d2d5976bb5fb5a68bf20bb6ca9ada Mon Sep 17 00:00:00 2001
From: Robert Griesemer <gri@golang.org>
Date: Sat, 18 Feb 2017 11:14:35 -0800
Subject: math/bits: faster OnesCount

Using some additional suggestions per "Hacker's Delight".
Added documentation and extra tests.

Measured on 1.7 GHz Intel Core i7, running macOS 10.12.3.

benchmark                  old ns/op     new ns/op     delta
BenchmarkOnesCount-4       7.34          5.38          -26.70%
BenchmarkOnesCount8-4      2.03          1.98          -2.46%
BenchmarkOnesCount16-4     2.56          2.50          -2.34%
BenchmarkOnesCount32-4     2.98          2.39          -19.80%
BenchmarkOnesCount64-4     4.22          2.96          -29.86%

Change-Id: I566b0ef766e55cf5776b1662b6016024ebe5d878
Reviewed-on: https://go-review.googlesource.com/37223
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
---
 src/math/bits/bits_test.go | 85 ++++++++++++++++++++++++++--------------------
 1 file changed, 49 insertions(+), 36 deletions(-)

(limited to 'src/math/bits/bits_test.go')

diff --git a/src/math/bits/bits_test.go b/src/math/bits/bits_test.go
index c74e58ebde..50045c246e 100644
--- a/src/math/bits/bits_test.go
+++ b/src/math/bits/bits_test.go
@@ -232,48 +232,61 @@ func BenchmarkTrailingZeros64(b *testing.B) {
 }
 
 func TestOnesCount(t *testing.T) {
+	var x uint64
+	for i := 0; i <= 64; i++ {
+		testOnesCount(t, x, i)
+		x = x<<1 | 1
+	}
+
+	for i := 64; i >= 0; i-- {
+		testOnesCount(t, x, i)
+		x = x << 1
+	}
+
 	for i := 0; i < 256; i++ {
-		want := tab[i].pop
 		for k := 0; k < 64-8; k++ {
-			x := uint64(i) << uint(k)
-			if x <= 1<<8-1 {
-				got := OnesCount8(uint8(x))
-				if got != want {
-					t.Fatalf("OnesCount8(%#02x) == %d; want %d", x, got, want)
-				}
-			}
+			testOnesCount(t, uint64(i)<<uint(k), tab[i].pop)
+		}
+	}
+}
 
-			if x <= 1<<16-1 {
-				got := OnesCount16(uint16(x))
-				if got != want {
-					t.Fatalf("OnesCount16(%#04x) == %d; want %d", x, got, want)
-				}
-			}
+func testOnesCount(t *testing.T, x uint64, want int) {
+	if x <= 1<<8-1 {
+		got := OnesCount8(uint8(x))
+		if got != want {
+			t.Fatalf("OnesCount8(%#02x) == %d; want %d", x, got, want)
+		}
+	}
 
-			if x <= 1<<32-1 {
-				got := OnesCount32(uint32(x))
-				if got != want {
-					t.Fatalf("OnesCount32(%#08x) == %d; want %d", x, got, want)
-				}
-				if UintSize == 32 {
-					got = OnesCount(uint(x))
-					if got != want {
-						t.Fatalf("OnesCount(%#08x) == %d; want %d", x, got, want)
-					}
-				}
+	if x <= 1<<16-1 {
+		got := OnesCount16(uint16(x))
+		if got != want {
+			t.Fatalf("OnesCount16(%#04x) == %d; want %d", x, got, want)
+		}
+	}
+
+	if x <= 1<<32-1 {
+		got := OnesCount32(uint32(x))
+		if got != want {
+			t.Fatalf("OnesCount32(%#08x) == %d; want %d", x, got, want)
+		}
+		if UintSize == 32 {
+			got = OnesCount(uint(x))
+			if got != want {
+				t.Fatalf("OnesCount(%#08x) == %d; want %d", x, got, want)
 			}
+		}
+	}
 
-			if x <= 1<<64-1 {
-				got := OnesCount64(uint64(x))
-				if got != want {
-					t.Fatalf("OnesCount64(%#016x) == %d; want %d", x, got, want)
-				}
-				if UintSize == 64 {
-					got = OnesCount(uint(x))
-					if got != want {
-						t.Fatalf("OnesCount(%#016x) == %d; want %d", x, got, want)
-					}
-				}
+	if x <= 1<<64-1 {
+		got := OnesCount64(uint64(x))
+		if got != want {
+			t.Fatalf("OnesCount64(%#016x) == %d; want %d", x, got, want)
+		}
+		if UintSize == 64 {
+			got = OnesCount(uint(x))
+			if got != want {
+				t.Fatalf("OnesCount(%#016x) == %d; want %d", x, got, want)
 			}
 		}
 	}
-- 
cgit v1.3-5-g9baa