内容简介：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 , 算法
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Python标准库
Doug Hellmann / 刘炽 / 机械工业出版社华章公司 / 2012-6-15 / 139.00元
本书由资深Python专家亲自执笔，Python语言的核心开发人员作序推荐，权威性毋庸置疑。 对于程序员而言，标准库与语言本身同样重要，它好比一个百宝箱，能为各种常见的任务提供完美的解决方案，所以本书是所有Python程序员都必备的工具书！本书以案例驱动的方式讲解了标准库中一百多个模块的使用方法（如何工作）和工作原理（为什么要这样工作），比标准库的官方文档更容易理解（一个简单的示例比一份手册......一起来看看 《Python标准库》 这本书的介绍吧!
