C. C. Blog

Security Research, Algorithm and Data Structure

数学技巧(位运算)

  1. n mod 2^k = n&((1<<k)-1)
  2. 判断n是否为2的正整数幂n>1 && !(n&(n-1))

位压缩:

  1. 读取第k位:a>>k&1
  2. 读取第k位并取反:~a>>k&1
  3. 将第k位清0:a&=~(1<<k)
  4. 将第k位置1:a|=1<<k
  5. 将第k位取反:a^=1<<k
  6. 将第k1~k2位反转:a^=((1<<(k2-k1+1))-1)<<k2 (?)
  7. 是否恰好只有一个true:!(x&(x-1))&&x
  8. 判断是否有两个相邻的true:x>>1&x
  9. 是否有三个相邻的true:x>>1&x>>2&x

打包位统计:

  1. 统计true的个数的奇偶性:x=x>>1;x=x>>2;x=x>>4;x=x>>8;x^=x>>16; 之后:(x>>k1^x>>(k2+1))&1
  2. 统计true的个数1:每次n&=n-1,计数器+1
  3. 统计true的个数2:
    1
    2
    3
    4
    5
    6
    7
    8
    int count(unsigned int x){//注意传入uint
    x=(x&0x55555555)+(x>>1&0x55555555);
    x=(x&0x33333333)+(x>>2&0x33333333);
    x=(x&0x0F0F0F0F)+(x>>4&0x0F0F0F0F);
    x=(x&0x00FF00FF)+(x>>8&0x00FF00FF);
    x=(x&0x0000FFFF)+(x>>16&0x0000FFFF);
    return x;
    }
  4. 反转位的顺序:
    1
    2
    3
    4
    5
    6
    7
    8
    unsigned int rev(unsigned int x){
    x=(x&0x55555555)<<1|(x>>1&0x55555555);
    x=(x&0x33333333)<<2|(x>>2&0x33333333);
    x=(x&0x0F0F0F0F)<<4|(x>>4&0x0F0F0F0F);
    x=(x&0x00FF00FF)<<8|(x>>8&0x00FF00FF);
    x=(x&0x0000FFFF)<<16|(x>>16&0x0000FFFF);
    return x;
    }

消除分支:

  1. 计算绝对值:

    1
    2
    3
    4
    int abs(int x){
    int y=x>>31;
    return (x+y)^y;
    }

  2. 求最大值:

    1
    2
    3
    4
    int max(int x,int y){
    int m=(x-y)>>31;
    return y&m|x&~m;
    }

其他:

  1. 交换变量:
    1
    2
    3
    void swap(int& x,int& y){x^=y;y^=x;x^=y;};
    //C++可以写成x^=y^=x^=y
    //Java不行

感谢骆神犇,09年的文再看还是大有收获。

  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/6899/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!