位运算集锦
文中2'k代表2的k次方
?
1 除以2的k次幂可以用位运算：
n/2'k == n>>k
?
2 对2的k次幂取余数可以用位运算：
n%2'k == n & ((1<<k)-1)
比如 100%32
100的二进制为 ? ? ? ? ?1100100
((1<<5)-1)等于31为 ?0011111
两个数相与即得 100，故
100%32 = 4
?
3 对于整数n，从低位开始，把它的第k位（0<=k<=31）置为1的操作为：
n = n | (1<<k)
?
4 对于整数n，从低位开始，把它的第k位（0<=k<=31）置为0的操作为：
n = n & ~(1<<k)
?
?
5 对于整数n，从低位开始，测试它的第k位（0<=k<=31）是否为1，若为1，返回一个大于0的数，否则返回0
return ?n & (1<<k)
?
6 对于整数n，判断它是奇数还是偶数
若n & 1大于0，则n是奇数，否则n是偶数
?
7 对于整数n，若n是奇数，则把n减1变成偶数，若n是偶数，则把n加1变成奇数
n = n ^ 1
?
8 对于奇数n，有如下性质
(n-1) ^ n ==1
?
9 最大的int
01 1111111111 1111111111 1111111111
MAX_INT = ~(1<<31)
?
10 最小的int
10 0000000000 0000000000 0000000000
MIN_INT = (1<<31)
?
11 把最低位的1变为0
比如： 111000 ? ---> 110000
n = n - (n&-n)
?
12 判断两个整数数是否同号
#define MASK 0x80000000
flag?=?(x & MASK) ^ (y & MASK)
如果flag为0，说明不同号，否则同号
?
13?交换两个值，不用临时变量
想将ａ和ｂ的值互换，可以用以下赋值语句实现：
??? ａ＝a∧b;
??? ｂ＝b∧a;
??? ａ＝a∧b;
?
?
14 bitset的C语言实现
?
#include <stdio.h>#include <string.h>#define N 4000000000#define SHIFT 5#define MASK 0x1fint a[1+N/32];void set(unsigned int i) {a[i>>SHIFT] |= (1 << (i & MASK));// a[i/32] |= (1 << i%32)}void clr(unsigned int i){a[i>>SHIFT] &= ~(1 << (i & MASK)); // a[i/32] &= ~(1 << i%32)}unsigned int test(unsigned int i){return a[i>>SHIFT] & (1 << (i & MASK)); // a[i/32] & (1 << i%32)}int main(){unsigned inti;memset(a, 0, sizeof(a));for (i = 0; i < N; i++) {set(i);}for (i = 0; i < 10; i++) {if(test(i)) {printf("%d exitst\n", i);}}getchar();return 0;}