今天看树状数组,突然发现了这个东西,想了一想,然后用文字简要的证明了一下:

2^k = L and (L xor (L - 1) )

设i在二进制下从末尾数的第 k 位第一次不为0.
先用 c = i^(i-1)则将第 k 位以左的数变为0,从k位往右都为1
再用 i & c 因为c的末尾 k位为1,k位以左为0,i的末尾 k-1位为0,第k位为1,k位以左不知道。
按位与后则剩余的数即为 2^(k - 1)

下面是程序:

    #include <stdio.h>
    #include <math.h>
    #define NUM 16
                            
    //lowbit:计算当 i 在二进制下整数 末尾0的个数为k时求2^k 即 2^k = lowBit(i)
                            
    //设i在二进制下从末尾数的第 k 位第一次不为0.
    //先用 c = i^(i-1)则将第 k 位以左的数变为0,从k位往右都为1
    //再用 i & c 因为c的末尾 k位为1,k位以左为0,i的末尾 k-1位为0,第k位为1,k位以左不知道。
    //按位与后则剩余的数即为 2^(k - 1),
                            
    //从而能计算出当 i 在二进制下整数 末尾0的个数为k时求2^k 即 2^k = lowBit(i)
    //要算k为多少只需再以2为底进行取余即可。 
    int lowBit(int i){
        return i&(i^(i-1));
    }
                            
    int main(int argc, char *argv[])
    {
                                
        for(int i = 1;i < NUM + 1;++i){
            printf("%d:\t%d\n",i,(int)log2(lowBit(i)));
        }
        return 0;
    }

在解决完这个问题后,我突然想到了,一个问题,按照这个方法,改改程序,我就可以求出fft里面的那个码位倒序这个过程了。

代码如下:fft中的码位倒序代码, 当然也可以一位一位的去求但是当i为2的k次幂时就会比较费时,至少能起到一个常数系数的优化:

    #include <stdio.h>
    #include <math.h>
    #define NUM 16
    #define NUM_WEI 4
               
    int lowBit(int i){
        return i&(i^(i-1));
    }
              
    int ma_wei_dao_xu(int k){
        int l;
        int sum = 0;
        while(k){
                      
            l = lowBit(k);
                      
            sum += (int)pow(2,NUM_WEI - log2(l) - 1);
                      
            k &= (NUM  - l * 2);
        }
        return sum;
    } 
              
              
    int main(int argc, char *argv[])
    {
                  
        for(int i = 0;i < NUM;++i){
            printf("%d:\t%d\n",i,ma_wei_dao_xu(i));
        }
        return 0;
    }

后续:

刚才吃饭的时候想了一下以4位数来说节省的时间为C(1,4) + 2C(2,4) +3 C(3,4) + 4*C(4,4);

对于为N位的二进制数来说总的时间为: C(1,N) + 2C(2,N) +…..+ (N-1)C(N-1,N) + N*C(N,N);

因为节剩的总 时间就为0的总个数。 C(m,N)其实就暗含了,N位二进制中包含m个零的数的个数,包含的零的个数为:m*C(m,N);