算法:
核心在于单个数字的1的个数的计算,其他的题目都是基于这个基础来做的操作。
题目1:
https://leetcode-cn.com/problems/number-of-1-bits/
代码实现:
func hammingWeight(num uint32) int {
count := 0
for i := 0; i < 32; i++ {
if num&(1<<i) != 0 {
count++
}
}
return count
}
// 算法:
// 利用单个bit上面的 a&1=1 表示a=1;a&1=0 表示a=0
执行结果:
题目2:
https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits/
代码实现:
func sortByBits(arr []int) []int {
tmp := make(map[int][]int)
nums := []int{}
for _, a:=range arr {
n:=getCount(a)
v,ok:=tmp[n]
if !ok {
v = []int{a}
tmp[n] = v
nums = append(nums,n)
} else {
v = append(v,a)
tmp[n] = v
}
}
// 利用map将数组按照升序的方式排序
sort.Ints(nums)
res := []int{}
for _,v := range nums{
// 相同位数的数组里面也需要按照升序排序
sort.Ints(tmp[v])
res =append(res,tmp[v]...)
}
return res
}
func getCount(a int) int {
c := 0
for a != 0 {
if a&1 == 1 {
c++
}
a = a>>1
}
return c
}
执行结果:
题目3:
https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation/
代码实现:
func countPrimeSetBits(L int, R int) int {
// 质数是只能被1和自己整除,R最大值是10^6,也就是2^20,所以质数如下
s := []int{2,3,5,7,11,13,17,19}
m := make(map[int]int)
for _,v:=range s {
m[v] = v
}
// 计算每个数中1的个数
c := 0
for i:=L;i<=R;i++ {
t := numCount(i)
if _,ok := m[t];ok {
c++
}
}
return c
}
func numCount(num int) int {
c := 0
for i:=0;i<64;i++ {
if num&(1<<i) != 0 {
c++
}
}
return c
}
执行结果: