欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

统计整数的二进制表达里有多少个1 Python版

程序员文章站 2024-02-27 15:49:57
...

题目
给定一个整数,统计其二进制表示里有多少个1。

分析
方法1:循环迭代该数的二进制的每一位,复杂度是 o(log2 n),n就是该整数
方法2:复杂度仅仅是1的个数。方法是采用位运算抹去0不需要处理。这里的位运算表达式不光在这里见到,其它地方的用处也非常多。

再者,计算机组成原理里有详细的对加减乘数四则运算的讲解,如何表示负数、小数等等,不过我都忘了……这些运算与位运算息息相关。单靠位运算即可实现十进制数的加减乘除

代码

    def count1(a):
        '''
            整数的二进制表达里有多少个1,复杂度为a的二进制长度。
        '''
        num = 0
        while a != 0:
            num += a & 1
            a >>= 1
        return num

    def count2(a):
        '''
            整数的二进制表达里有多少个1,复杂度仅为1的个数
        '''
        num = 0
        while a != 0:
            a = a & (a - 1)  # 就是这个操作,需要掌握,它的本质含义是抹去了0不考虑
            num += 1
        return num
相关标签: python 位运算