LeetCode 计算二进制数中1的个数

栏目: 编程工具 · 发布时间: 3周前

来源: studygolang.com

本文转载自:https://studygolang.com/articles/21410,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有。

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.670s  
Golang , 算法

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

为你推荐:

相关软件推荐:

查看所有标签

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

有趣的二进制

有趣的二进制

[ 日] 爱甲健二 / 周自恒 / 人民邮电出版社 / 2015-10 / 39.00元

《有趣的二进制:软件安全与逆向分析》通过逆向工程,揭开人们熟知的软件背后的机器语言的秘密,并教给读者读懂这些二进制代码的方法。理解了这些方法,技术人员就能有效地Debug,防止软件受到恶意攻击和反编译。本书涵盖的技术包括:汇编与反汇编、调试与反调试、缓冲区溢出攻击与底层安全、钩子与注入、Metasploit 等安全工具。 《有趣的二进制:软件安全与逆向分析》适合对计算机原理、底层或计算机安全......一起来看看 《有趣的二进制》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具