首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

求二进制数中一的个数

2013-10-10 
求二进制数中1的个数对于一个32位的无符号整型变量,求其二进制表示中“1”的个数,要求算法的执行效率尽可能

求二进制数中1的个数

    对于一个32位的无符号整型变量,求其二进制表示中“1”的个数,要求算法的执行效率尽可能高。


求二进制数中一的个数


解法1和解法2的时间复杂度都是O(log2v),解法3的时间复杂度是O(v)

    那有没有时间复杂度是O(1)的呢?答案是有的,但是这种是用空间换时间的方法。

方法4:使用switch case语句,数字越小效率越高,数字越大比较的次数越多效率越低。

方法5:预定义的结果表,将一个整数,这里拿1个字节的整数来说,比如数字是在0~255,那么定义一个256大小的数组,直接在数组设定好0~255对应二进制1的个数。

这二种方法的时间复杂度都是O(1),但这是用空间换时间的办法,在嵌入式编程中,不推荐。这里推荐使用方法3.


热点排行