Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 310
Good morning! Here's your coding interview problem for today.

This problem was asked by Pivotal.

Write an algorithm that finds the total number of set bits in all integers between `1` and `N`.

Pull request:
Day310
Resolves #633.

Patch:
diff --git a/README.md b/README.md
index c6d017c..a4eef03 100644
--- a/README.md
+++ b/README.md
@@ -317,3 +317,4 @@ problems from
 * [Day 306](https://github.com/vaskoz/dailycodingproblem-go/issues/626)
 * [Day 307](https://github.com/vaskoz/dailycodingproblem-go/issues/628)
 * [Day 309](https://github.com/vaskoz/dailycodingproblem-go/issues/631)
+* [Day 310](https://github.com/vaskoz/dailycodingproblem-go/issues/633)
diff --git a/day310/problem.go b/day310/problem.go
new file mode 100644
index 0000000..46c8794
--- /dev/null
+++ b/day310/problem.go
@@ -0,0 +1,72 @@
+package day310
+
+import "math/bits"
+
+// CountSetMathBits returns the number of set bits (1).
+// It uses math/bits.
+func CountSetMathBits(num uint64) []int {
+	result := make([]int, 0, int(num))
+	for i := uint64(1); i <= num; i++ {
+		result = append(result, bits.OnesCount64(i))
+	}
+	return result
+}
+
+// PopcntA is a manual implementation.
+func PopcntA(num uint64) []int {
+	result := make([]int, 0, int(num))
+	for i := uint64(1); i <= num; i++ {
+		x := i
+		x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555)
+		x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
+		x = (x & 0x0f0f0f0f0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f0f0f0f0f)
+		x = (x & 0x00ff00ff00ff00ff) + ((x >> 8) & 0x00ff00ff00ff00ff)
+		x = (x & 0x0000ffff0000ffff) + ((x >> 16) & 0x0000ffff0000ffff)
+		x = (x & 0x00000000ffffffff) + ((x >> 32) & 0x00000000ffffffff)
+		result = append(result, int(x))
+	}
+	return result
+}
+
+// PopcntB is a second manual implementation.
+func PopcntB(num uint64) []int {
+	result := make([]int, 0, int(num))
+	for i := uint64(1); i <= num; i++ {
+		x := i
+		x -= (x >> 1) & 0x5555555555555555
+		x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
+		x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
+		x += x >> 8
+		x += x >> 16
+		x += x >> 32
+		result = append(result, int(x&0x7f))
+	}
+	return result
+}
+
+// PopcntC is a second manual implementation.
+func PopcntC(num uint64) []int {
+	result := make([]int, 0, int(num))
+	for i := uint64(1); i <= num; i++ {
+		x := i
+		x -= (x >> 1) & 0x5555555555555555
+		x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
+		x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
+		result = append(result, int((x*0x0101010101010101)>>56))
+	}
+	return result
+}
+
+// PopcntD is a second manual implementation.
+func PopcntD(num uint64) []int {
+	result := make([]int, 0, int(num))
+	for i := uint64(1); i <= num; i++ {
+		x := i
+		var count int
+		for count = 0; x != 0; count++ {
+			x &= x - 1
+		}
+		result = append(result, count)
+	}
+	return result
+}


Test patch:
diff --git a/day310/problem_test.go b/day310/problem_test.go
new file mode 100644
index 0000000..cf413ff
--- /dev/null
+++ b/day310/problem_test.go
@@ -0,0 +1,99 @@
+package day310
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	num     uint64
+	setBits []int
+}{
+	{3, []int{1, 1, 2}},
+}
+
+func TestPopcntD(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := PopcntD(tc.num); !reflect.DeepEqual(result, tc.setBits) {
+			t.Errorf("Expected %v, got %v", tc.setBits, result)
+		}
+	}
+}
+
+func BenchmarkPopcntD(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PopcntD(tc.num)
+		}
+	}
+}
+
+func TestPopcntC(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := PopcntC(tc.num); !reflect.DeepEqual(result, tc.setBits) {
+			t.Errorf("Expected %v, got %v", tc.setBits, result)
+		}
+	}
+}
+
+func BenchmarkPopcntC(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PopcntC(tc.num)
+		}
+	}
+}
+
+func TestPopcntB(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := PopcntB(tc.num); !reflect.DeepEqual(result, tc.setBits) {
+			t.Errorf("Expected %v, got %v", tc.setBits, result)
+		}
+	}
+}
+
+func BenchmarkPopcntB(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PopcntB(tc.num)
+		}
+	}
+}
+
+func TestPopcntA(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := PopcntA(tc.num); !reflect.DeepEqual(result, tc.setBits) {
+			t.Errorf("Expected %v, got %v", tc.setBits, result)
+		}
+	}
+}
+
+func BenchmarkPopcntA(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PopcntA(tc.num)
+		}
+	}
+}
+
+func TestCountSetMathBits(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := CountSetMathBits(tc.num); !reflect.DeepEqual(result, tc.setBits) {
+			t.Errorf("Expected %v, got %v", tc.setBits, result)
+		}
+	}
+}
+
+func BenchmarkCountSetMathBits(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CountSetMathBits(tc.num)
+		}
+	}
+}