利用位运算计算二进制中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
}

文章作者: 陌无崖
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 陌无崖 !
 上一篇
defer、panic、recover defer、panic、recover
Defer,Panic,and RecoverAndrew Gerrand4 August 2010 Go拥有一般的控制流程机制,像if、for、switch、goto。除此之外go也拥有一个单独的goroutine机制运行go语句。这里我
2019-09-17
下一篇 
关于NATS连接Golang实践 关于NATS连接Golang实践
重新连接如果因为任何原因断开连接,大多数(如果不是全部)客户端库将重新连接到NATS系统。 重新连接逻辑可能因库而异,因此请检查客户端库的文档。 通常,客户端将尝试通过connect调用中提供的URL或NATS系统本身提供的URL连接到它知
2019-09-15
  目录