- n mod 2^k = n&((1<<k)-1)
- 判断n是否为2的正整数幂n>1 && !(n&(n-1))
位压缩:
- 读取第k位:a>>k&1
- 读取第k位并取反:~a>>k&1
- 将第k位清0:a&=~(1<<k)
- 将第k位置1:a|=1<<k
- 将第k位取反:a^=1<<k
- 将第k1~k2位反转:a^=((1<<(k2-k1+1))-1)<<k2 (?)
- 是否恰好只有一个true:!(x&(x-1))&&x
- 判断是否有两个相邻的true:x>>1&x
- 是否有三个相邻的true:x>>1&x>>2&x
打包位统计:
- 统计true的个数的奇偶性:x=x>>1;x=x>>2;x=x>>4;x=x>>8;x^=x>>16; 之后:(x>>k1^x>>(k2+1))&1
- 统计true的个数1:每次n&=n-1,计数器+1
- 统计true的个数2:
1
2
3
4
5
6
7
8int 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;
} - 反转位的顺序:
1
2
3
4
5
6
7
8unsigned 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
2
3
4int abs(int x){
int y=x>>31;
return (x+y)^y;
}求最大值:
1
2
3
4int max(int x,int y){
int m=(x-y)>>31;
return y&m|x&~m;
}
其他:
- 交换变量:
1
2
3void swap(int& x,int& y){x^=y;y^=x;x^=y;};
//C++可以写成x^=y^=x^=y
//Java不行