内容简介：1 题目描述给定一个非负整数num，对0 ≤ i ≤ num区间内每个整数，计算其对应的二进制数中1的个数，结果用数组返回。
2018年11月1日
1 题目描述
给定一个非负整数num，对0 ≤ i ≤ num区间内每个整数，计算其对应的二进制数中1的个数，结果用数组返回。
例子1：
输入：2
输出：[0, 1, 1]
例子2：
输入：5
输出：[0,1,1,2,1,2]
2 解决思路
2.1 常规算法
func decimal2Binary(n int) string {
b := ""
for {
// remain
r := 0
n, r = n>>1, n%2
b = strconv.Itoa(r) + b
if 0 == n {
return b
}
}
}
func countOne(s string) int {
c := 0
for _, i := range []rune(s) {
if '1' == i {
c++
}
}
return c
}
func countBits(num int) []int {
s := make([]int, num+1)
for i := 0; i <= num; i++ {
s[i] = countOne(decimal2Binary(i))
}
return s
}
2.2 改进思路
避免对递增数组中的每个数值作计算，将4位看做一个单元，单元内0-15的二进制数中1的个数是确定的。这样采用16进制去计算，给定数值，每除以16所得的余数就是落在该单元内的数值，直至被除数为0，将每个单元中1的个数累加既可。
func countBinaryOneInHexUnit(n int) int {
countOne := 0
switch n {
case 0:
countOne = 0
case 1, 2, 4, 8:
countOne = 1
case 3, 5, 6, 9, 10, 12:
countOne = 2
case 7, 11, 13, 14:
countOne = 3
case 15:
countOne = 4
}
return countOne
}
func countBinaryOne(n int) int {
// remain
r := 0
countOne := 0
for n > 0 {
n, r = n>>4, n%16
countOne += countBinaryOneInHexUnit(r)
}
return countOne
}
func countBits(num int) []int {
s := make([]int, num+1)
for i := 0; i <= num; i++ {
s[i] = countBinaryOne(i)
}
return s
}
4 基准测试
4.1 测试代码
package main
import (
"testing"
)
func BenchmarkCountBits(b *testing.B) {
for i := 0; i < b.N; i++ {
countBits(100000000)
}
}
go test -test.bench=".*"
4.2 测试结果
goos: darwin goarch: amd64 pkg: github.com/olzhy/test BenchmarkCountBits-4 1 4618146566 ns/op PASS ok github.com/olzhy/test 4.670sGolang , 算法
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
An Introduction to Genetic Algorithms
Melanie Mitchell / MIT Press / 1998-2-6 / USD 45.00
Genetic algorithms have been used in science and engineering as adaptive algorithms for solving practical problems and as computational models of natural evolutionary systems. This brief, accessible i......一起来看看 《An Introduction to Genetic Algorithms》 这本书的介绍吧!
