内容简介: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 , 算法
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- C语言实现一个数的二进制位的倒位
- 02_Python学习笔记之统计整数二进制中1的个数
- swoole之协程channel元素个数
- 用堆找出最小的 N 个数
- leetcode.69.求一个数的平方根
- 统计两个IP地址之间的IP个数
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
JSP应用开发技术
柳永坡 / 人民邮电出版社 / 2005-9 / 52.00元
本书全面系统地介绍了JSP应用开发技术,包括JSP预备知识和环境配置、JSP编程基础、JSP应用开发进阶、在JSP中使用数据库、Servlet技术、标签库和表达式语言、Web编程模式和应用框架等几个方面的内容。本书不但由浅入深地介绍了JSP程序设计的原理、方法和技术,还提供了大量的JSP应用开发实例,给出了相应的实用技巧、操作步骤及优化思路。 本书着重于JSP技术的应用性和可操作性,......一起来看看 《JSP应用开发技术》 这本书的介绍吧!
HTML 编码/解码
HTML 编码/解码
SHA 加密
SHA 加密工具