i&i-1的作用

63 阅读 0 评论 42 点赞

我是靠谱客的博主犹豫嚓茶，最近开发中收集的这篇文章主要介绍i&i-1的作用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

先来看一个函数

#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的次幂

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

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

3)判断n是不是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的次幂的数。