位运算技巧

基础位运算运算符（按位）

1.或

符号：| 
比较两个数的每一位，只要有一个数在这一位上为1，所得的新数在这一位上就为1，否则为0。

• 1 | 1 = 1;
• 1 | 0 = 1;
• 0 | 1 = 1;
• 0 | 0 = 0;

2.与

符号：& 
比较两个数的每一位，只有两数这一位同时为1时所得新数为1，否则为0。

• 1 & 1 = 1;
• 1 & 0 = 0;
• 0 & 0 = 0;
• 0 & 0 = 0;

3.异或

符号：^ 
比较两数的每一位，如果一样所得新数这一位就是0，不一样就是1。

• 1 ^ 1 = 0;
• 1 ^ 0 = 1;
• 0 ^ 1 = 1;
• 0 ^ 0 = 0;

4.取反

符号：~ 
0变1,1变0。

• ~ 1 = 0;
• ~ 0 = 1;

5.移位

符号：<<，>> 
将二进制数整体向左/右移动。常用来整除2，乘2。

• 1 << 1 = 10;
• 1 << 2 = 100;
• 11 << 2 = 1100;
• 1111 >> 2 = 11;

位运算使用进阶技巧

判断一个数的奇偶性

if(x & 1) 奇数();
else 偶数();

交换两变量的值

void swap(int a,int b){
    a ^= b;
    b ^= a;
    a ^= b;
}

取一个数的某一位

int get(int x,int y){//取x的第y位
    return (n >> (m - 1)) & 1;
}