【面试题】i&(i-1)判断n是否为2的次幂

一、参考资料

i&i-1的作用
i&(i-1)
有趣的逻辑运算符“&”，在Python中的用法详解

二、相关介绍

1. 按位与(&)

当 & 运算符用于整数时，会执行按位与操作。按位与操作的规则是将两个整数对应的二进制位进行与运算，得到的结果再转换为十进制。例如：

a = 5  # 二进制表示是 101
b = 3  # 二进制表示是 011
result = a & b  # 二进制表示是 001
print(result)  # 输出结果为 1

2. i&(i-1)

2.1 母题：判断n是否为2的次幂？

// c语言
// 判断n是否为2的次幂，且n为正整数
bool isPowerOfTwo(int n) {
   
    return n>0&&(n&(n-1))==0;
}

# python
"""
查找满足2的次幂的数
https://github.com/lorenzopapa5/SPEED/blob/main/layers.py#L135-L138
"""
def HPO2(filters_value):
    for i in range(filters_value, 0, -1):
        if (i & (i - 1)) == 0:
            return i

2.2 拓展

#include <stdio.h>

int fun(int i) 
{
    
    int cnt = 0; 
    while(i) 
    {
    
        cnt++; 
        i = i&(i-1); 
    } 
    
    return cnt; 
} 

int main()
{
    
    printf( "%d\n", fun(2017) );
    
    return 0;  
}

思考：上面这个函数的作用是什么？

答案： 我们首先来看一下 i&(i-1)， i&(i-1)的作用是将i的二进制表示的最低位为1的改为0。在本题中即数出2017转换成二进制有几个1就会走几次循环。2017对应的二进制是：10000111111，一共7个1，故走7次。