作者 | 陌无崖
转载请联系授权
传入一个整数,求其二进制中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
}