程序中的所有数在计算机内存中都是以二进制的形式储存的 。而位运算，就是直接对在内存中的二进制位进行操作，跳过了 程序转义成二进制的这一步骤，对编译时间有所提高，但带来的缺点也很明显，程序的可读性变低了。
掌握位运算 是一位程序员的基本素养，位运算在计算机领域的作用可谓举足轻重。下面我将讲解 位运算的大体方法以及一些基本的应用。
and 运算
只有对应的两个 二进制数，均为 1，结果才为 1，否则为 0
& 1 判断 n 的第 m 位数 。
介绍两个重要应用，来证明其含义：
(n >>m ) & 1 判断 整数 n 的二进制 第 m 位 是否 为 1 或者 为 0 n 的第 m 位数，如果为 1 ，1&1 就返回 1 ，如果为 0，0&1 就返回 0
判断 奇偶性 如果 n 为奇数，辗转相除 2，最后的余数 必定为 1，如果 n 为偶数，辗转相除 余数必定为 0 也就是说，n 为奇数，n&1 等价于 1&1 ，返回 1，n 为偶数，n&1 等价于 0&1，返回 0
& 0 将 n 的第 m 位数，重置为 0 基本应用：n & ~(1 << m)
1 << m 定位到 n 的第 m 位数
~(1 << m) 将 1 进行非运算，变为 0，其他剩下的 m 位，变成 1，而 &1，是无实际作用的
n & 0 ：& 按位与运算 只有对应的两个数 全部为 1 时，结果才为 1，而&0，返回值一定为 0
or 运算
只有对应的两个 二进制数，均为 0，结果才为 0，否则为 1
| 1 将 n 的第 m 位数，重置为 1
基本应用：n | (1 << m):
1 << m
n | 1
| 0 无实际作用
一定要清楚， 是 n 的第 m 位数 在进行操作，其他 位数操作，根本无 影响
因为，其他位数，是 在进行 “| 0” 操作，而所谓的 |0 操作，与 &1 操作，毫无差别。
假设 k=n 的第 m 位数，k = 1 ，k|0 = 1|0 = 1，k = 0，k|0 = 0|0 = 0，所谓 无实际作用。
但是要注意一点，我说的 0 是在二进制数中的 0，有实际含义的 0，不是补 0 的 0
所以，可以感性的认识到，| 0 与 & 1 以及 下文的 ^ 0，都是无实际作用的
xor 运算
只有对应的两个 二进制数相等时，结果才为 0，否则为 1
^ 1 将 n 的第 m 位数，取反
基本应用：n ^ (1 << m)
1 << m ： 定位到 n 的第 m 位数
n ^ 1，我们要知道，^ (异或）：不相等为 1，相等为 0
而 ^1：如果 n 的第 m 位数 为 1，1^1 返回值为 0，如果 n 的第 m 位数 为 0，0^1 返回值 为 1
所以，^1 的重要作用，就是 与之相反的作用
^ 0 无实际作用
假定 整数 k 为 0，k^0 = 0^0 = 0 ; 假定整数 k 为 1，k^0 = 1^0 = 1
所以说，无论怎么变化，^0 都是无实际作用的
shl & shr 运算
左移运算符 “<<”
表达式：a << b a<<b 的值是：将 a 各二进位全部左移 b 位后得到的值。左移时，高位丢弃，低位补 0。 实际上，左移 1 位，就等于是乘以 2，左移 n 位，就等于是乘以 2n。 而左移操作比乘法操作快得多。
1 2 3 4 5 COPY例如:9 << 4 9 的二进制形式：0000 0000 0000 0000 0000 0000 0000 1001 因此，表达式“9<<4”的值，就是将上面的二进制数左移4位，得： 0000 0000 0000 0000 0000 0000 1001 0000 即为十进制的144 , 而 9 *2的4次幂 = 9 *16 = 144 .
右移运算符 “>>”
表达式：a >> b a>>b 的值是：将 a 各二进位全部右移 b 位后得到的值。右移时，移出最右边的位就被丢弃。 对于有符号数，如 long,int,short,char 类型变量，在右移时，符号位（即最高位）将一起移动，并且大多数 C/C++编译器规定，如果原符号位为 1，则右移时高位就补充 1，原符号位为 0，则右移时高位就补充 0。
1 2 COPY实际上，右移 n 位，就相当于左操作数除以2n，并且将结果往小里取整。 例如：-25 >> 4 = -2 -2 >> 4 = -1 18 >> 4 = 1
应用 对 2 的整数幂进行模运算 1 2 3 4 5 6 7 8 9 10 11 12 COPY#include <stdio.h> int main () int n,k; while (~scanf ("%d %d" ,&n,&k)){ n<<=k; n>>=k; printf ("%d\n" ,n); } return 0 ; }
两数交换 1 2 3 4 5 6 7 8 9 10 11 COPY#include <stdio.h> int main () int n,m; while (~scanf ("%d %d" ,&n,&m)){ n^=m; m^=n; n^=m; printf ("%d %d\n" ,n,m); } return 0 ; }
按位异或 ^ : 不相同 为：1 ; 相同 为 ：0 将参与运算的两操作数各对应的二进制位进行异或操作， 即只有对应的两个二进位不相同时，结果的对应二进制位才是 1，否则为 0。
异或运算的特点是：如果 a^b=c，那么就有 c^b = a 以及 c^a=b
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 COPY例如：表达式“21 ^ 18 ”的值是7(即二进制数111)。 21： 10101 18： 10010 21^18: 00111 假设 n = 5，m = 6 5的二进制为：101 6的二进制为：110 n^=m = 5^=6 = 101 ^ 110 = 011 , 此时 n 的二进制为：011 m^=n = 6^=011 = 110 ^ 011 = 101 , 此时 m 的二进制为：101，也正是 5的二进制数，也就是说 m ==开始的 n n^=m = 011^=5 = 011 ^ 101 = 110 , 此时 n 的二进制位：110，也正是 6的二进制数，也就是说 n ==开始的 m
层次结构：A->B B->A A->B 正 反 正
判断 2 的正整数幂 1 2 3 4 5 6 7 8 9 10 11 COPY#include <stdio.h> int main () int n; while (~scanf ("%d" ,&n)){ if (!(n & (n-1 )) && n) printf ("%d 为 2 的正整数幂\n" ,n); else printf ("%d 不是 2 的正整数幂\n" ,n); } return 0 ; }
给定整数 n 判断 n 是否为 2 的正整数幂 表达式：(! (n & (n-1)) && n
1 2 3 4 COPY举个例子： n = 16 = 10000，n-1 = 15 = 1111 那么 ：10000 & 01111 = 00000 = 0 再举个例子： n = 256 = 10000000 ,n-1 = 255 = 11111111 那么：100000000 & 011111111 = 000000000 = 0
是的，如果一个数 n 是 2 的正整数幂，那么 n 的二进制必定为 1000…. n-1 的二进制必定为 1111…. 即： n & n-1 = 0 所以 (! (n & (n-1)) 为 1 ; && n ：判断 n 为正数
判断奇偶性 1 2 3 4 5 6 7 8 9 10 11 COPY#include <stdio.h> int main () int n; while (~scanf ("%d" ,&n)){ if (n&1 ) printf ("%d 是奇数\n" ,n); else printf ("%d 是偶数\n" ,n); } return 0 ; }
记住：在做位运算时，位数不够的数，自动在 前面补 0 比如：21 & 1 ：10101 & 00001 = 00001 = 1 16 & 1 ：10000 & 00001 = 00000 = 0 事实证明：偶数的二进制的末尾 为 0，奇数的二进制的末尾 为 1
十进制 m 转换 n 进制方法： m 一直除 n，每相除一次，m 就等于商，直到商为 0，然后余数反排 即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 COPY1的二进制：1 /2 = 0 余1 余数反排 即是 1 的二进制：1 6 的二进制：6 /2 = 3 余0 3 /2 = 1 余1 1 /2 = 0 余1 余数反排 即是 6 的二进制：110 15 的二进制：15 /2 = 7 余1 7 /2 = 3 余1 3 /2 = 1 余1 1 /2 = 0 余1 余数反排 即是 15 的二进制：1111 5 的二进制：5 /2 = 2 余1 2 /2 = 1 余0 1 /2 = 0 余1 余数反排 即是 5 的二进制：101 21 的二进制：21 /2 = 10 余1 10 /2 = 5 余0 5 /2 = 2 余1 2 /2 = 1 余0 1 /2 = 0 余1 余数反排 即是 21 的二进制：10101
其他方面
(n >> m) & 1 == (n >> m) | 0 == (n >> m) ^ 0
n & ~(1 << m) : 将 n 的第 m 位数，重置为 0
n | (1 << m) : 将 n 的第 m 位数，重置为 1
n ^ (1 << m) : 将 n 的第 m 位数，取其相反
使用位移运算来避免乘法运算是一种技巧，乘数必须都是正整数，而且必须至少有一个是2的n次方，例如：2，4，6，8，16，32……移位运算的特点是速度快，而乘法运算速度较慢，把乘法运算转化为移位运算可以提高程序运算效率。
1 2 3 4 5 6 7 8 9 12 *2 = 12 << 1 12 *3 = 12 *(2 +1 ) = 12 *2 + 12 = 12 << 1 + 12 12 *4 = 12 << 2 12 *5 = 12 *(4 +1 ) = 12 << 2 + 12 12 *6 = 12 *(4 +2 ) = 12 *4 + 12 *2 = 12 << 2 + 12 << 1 12 *7 = 12 *(4 +2 +1 ) = 12 << 2 + 12 << 1 + 12 12 *8 = 12 << 3 12 *9 = 12 *(8 +1 ) = 12 << 3 + 12 12 *10 = 12 *(8 +2 ) = 12 << 3 + 12 << 1
位移也可以做除法
1 2 3 12 /2 = 12 >> 1 12 /4 = 12 >> 2 12 /8 = 12 >> 3