i&i-1的作用

先来看一个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

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

int main()
{ 
    printf( "%dn", fun(2017) );
    
    return 0;  
}

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

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

拓展：

1)判断n是不是2的次幂

1
2
3
4
    bool isPowerOfTwo(int n) {
        return n>0&&(n&(n-1))==0;
    }

2)判断n是不是3的次幂

3)判断n是不是4的次幂

1
2
3
4
    bool isPowerOfFour(int num) {
        return num>0&&(num&(num-1))==0&&(num-1)%3==0;
    }

证明：
(1)首先证明(4^n - 1) % 3 == 0:
4^n - 1 = (2^n + 1) * (2^n - 1),连续的三个之间必定有一个数是3的倍数，2^n 一定不是3的倍数，所以(2^n + 1)和(2^n - 1)中必定有一个是3的倍数，所以(4^n - 1)一定是3的倍数

(2)对于2^ n， 当n是奇数时，2^n 不是4的次幂，当n是偶数时，2^n 是4的次幂。
2^ n 等于（3-1）^n
回顾一下：(a+b)的n次方的展开式是多少?
由二次项定理 （a+b)n次方＝C(n,0)a(n次方)+C(n,1)a（n-1次方）b（1次方）+…+C（n,r）a(n-r次方)b(r次方)+…+C(n,n)b(n次方)(n∈N*)
2^n = (3-1)^n = C(n,0)3^ n *(-1)^ 0+…+(-1)^n.
上式中，除了最后一项(-1)^ n，其余项均为3的倍数，可以得到当n为奇数时， (-1)^ n等于-1，那么（2^ n-1）%3！=0，当n为偶数时， (-1)^ n等于1，那么（2^ n-1）%3==0。

所以，综上所述，加一个筛选条件(num-1)%3==0，即可从符合2的次幂的数中筛选出符合4的次幂的数。

最后

以上就是犹豫嚓茶最近收集整理的关于i&i-1的作用的全部内容，更多相关i&i-1内容请搜索靠谱客的其他文章。