【go】剑指offer：3种方法寻找二进制1的个数
作者 | 陌无崖
转载请联系授权
题目要求
传入一个整数，求其二进制中1的个数
题目分析
对于该题很容易有思路，我们将整数进行二进制的转换的过程中记录余数为1的个数即可。需要注意的是传入的负数和循环的终止条件，代码如下，因为循环的终止条件为商为0时停止循环，因此返回结果中应该多加一个1才是真正1的个数。
func Total_1(data int) int {
if data == 0 {
return 0
}
if data < 0 {
data = -data
}
// 将数据转换成二进制
sum := 0
// 商
m := data / 2
// 余数
n := data % 2
// fmt.Println(n)
for m != 0 {
if n ==1{
sum += n
}
temp := m
m = m / 2
// 余数
n = temp % 2
// fmt.Println(n)
}
return sum + 1
}
对于这个题，当然对于常规思路并不是这个题的考点所在，并且上述代码中有不必要的逻辑，我们可以分析二进制中1的个数和二进制的关系，很容易分析出为二进制各个数字的之和，因此在循环中没有必要进行if判断，把if语句去掉仍然可以。代码如下
func Total_1(data int) int {
if data == 0 {
return 0
}
if data < 0 {
data = -data
}
// 将数据转换成二进制
sum := 0
// 商
m := data / 2
// 余数
n := data % 2
// fmt.Println(n)
for m != 0 {
sum += n
temp := m
m = m / 2
// 余数
n = temp % 2
// fmt.Println(n)
}
return sum + 1
}
但是还不够，对于上述的代码以看便知有很多重复的操作，比如开始的求商，求余，那么如何简化我们的代码呢？对于这一题我们的思路需要不停的对商进行求余，那么是否可以抓换成递归传入商呢？我们可以看如下结构：假如求9的二进制f(9)，f(9)代表求9的二进制1的个数，为9的余数+f(4)…..可知如下结构，假设余数为ni
f(9)
n1 f(4)
n2 f(2)
n3 f(1)
n4 f(0)
很明显为一个树状结构，父节点的结果为子节点的和，因此我们可以写如下递归，递归的终止条件为f(0),代码如下：
func Total_two(data int) int {
if data == 0 {
return 0
}
if data < 0 {
data = -data
}
m := data / 2
n := data % 2
return n + Total_two(m)
}
那么有没有更好的方法呢？因为我们知道，虽然递归简单，但是却消耗内存空间，有没有一种方法利用循环，仅仅说在检测到1的时候才循环呢？我们需要了解位的操作与的概念，
计算规则：两位同时为1，结果才为1，否则为0，如：3&5即 0000 0011 & 0000 0101 = 0000 0001因此，3&5的值得1。如：0&0=0;0&1=0;1&0=0;1&1=1;
我们可以将原始二进制数字减去1，如1010——>1001,将1001和1010做与运算发现结果为1000，我们发现原始数据的最右边的1变成了0。那么我们按照这样的方法只需要不停的将1变成0即可。代码如下：
func Total_three(data int) int {
count := 0
if data <= 0 {
data = -data
}
for data != 0 {
data = data & (data - 1)
count++
}
return count
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-12-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录