简单的算法，是否为2的乘方

发表于 | 分类于

简单的算法

1.判断一个正数是否是2的乘方(比如16是2的4次方)。

思路：
如果一个整数是2的乘方，那么转换为二进制，只有最高位为1；
把这个整数减一，转换为二进制，所有位都为1;
两者相与，则等于0

十进制 二进制 N-1 是否2的乘方
8 1000 111 是
16 10000 1111 是
32 100000 11111 是
64 1000000 111111 是
100 1100100 1100011 否 
1
2
def is_2_power(num):
    return (num & num -1) == 0

2.求出一个正整数转换成二进制后的数字“1”的个数

思路：
当然，也应该与位运算有关了。
一个数N，N&1 要么是0，要么是1。
所以，结果为1时，说明最低位是1。为0时，说明最低位不是1。
因此，每次&后，都右移一位，再次&，直到N右移为0时，结束循环。

1
2
3
4
5
6
7
def count_1(num):
    cnt = 0
    while num:
        if (num & 1):
            cnt += 1
        num = num >> 1
    return cnt