求二进制数中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.