/*
  The purpose of this document is to know the difference between
  an algorithm that uses the modulo operator vs one that does not.
  The two algorithms count the number of ones in the binary representation
  of a number.

  To run the test for yourself you download the document and in the
  directory run the following command:

  $ go test -bench=.

  The results I got were the following:

$ go test -bench=.
goos: linux
goarch: amd64
BenchmarkCount/low-numbers/modulo-4  	124911303	         8.92 ns/op
BenchmarkCount/low-numbers/math-4    	 5866159	       201 ns/op
BenchmarkCount/high-numbers/modulo-4 	15446630	        70.8 ns/op
BenchmarkCount/high-numbers/math-4   	  406203	      2858 ns/op
PASS
ok  	_/tmp	5.843s

*/
package main

import (
	"math"
	"testing"
)

func countOnesModulo(n int) int {
	count := 0
	for n > 0 {
		count += n % 2
		n = n >> 1
	}
	return count
}

func countOnesMath(n int) int {
	count := 0
	num := float64(n)
	for num > 0 {
		power := math.Floor(math.Log2(num))
		num = num - math.Pow(2, power)
		count++
	}
	return count
}

func TestCount(t *testing.T) {
	res := countOnesModulo(64)
	if res != 1 {
		t.Errorf("Modulo count failed, %d != 1", res)
	}

	res = countOnesModulo(65)
	if res != 2 {
		t.Errorf("Modulo count failed, %d != 2", res)
	}

	res = countOnesMath(64)
	if res != 1 {
		t.Errorf("Math count failed, %d != 1", res)
	}

	res = countOnesMath(65)
	if res != 2 {
		t.Errorf("Math count failed, %d != 2", res)
	}
}

func BenchmarkCount(b *testing.B) {
	sets := []struct {
		Name   string
		Number int
	}{
		{"low-numbers", 42},
		{"high-numbers", 3478259823749587},
	}

	for _, set := range sets {
		b.Run(set.Name, func(b *testing.B) {
			b.Run("modulo", func(b *testing.B) {
				for i := 0; i < b.N; i++ {
					countOnesModulo(set.Number)
				}
			})

			b.Run("math", func(b *testing.B) {
				for i := 0; i < b.N; i++ {
					countOnesMath(set.Number)
				}
			})
		})
	}
}