# 神奇的位运算 Date: 2018-01-25 Author: SimonAKing Categories: 后端 Tags: 后端, 位运算 Source: https://simonaking.com/blog/magic-bit-operation/ > 位运算讲解。 --- 位运算在计算机领域的作用可谓举足轻重。 ## 前言     首先，我们要了解一个概念：**程序中的所有数在计算机内存中都是以二进制的形式储存的**。而位运算，就是直接对在内存中的二进制位进行操作，跳过了 程序转义成二进制的这一步骤，对编译时间有所提高，但带来的缺点也很明显，程序的可读性变低了。     掌握位运算 是一位程序员的基本素养，位运算在计算机领域的作用可谓举足轻重。     下面我将讲解 位运算的大体方法以及一些基本的应用。 ## 正文 ### and 运算 > 只有对应的两个 二进制数，均为1，结果才为 1，否则为 0 #### & 1 **判断 n的第m位数**。 介绍两个重要应用，来证明其含义： 1. (n >>m ) & 1 判断 整数n 的二进制 第m位 是否 为1 或者 为0 n 的第m位数，如果为1 ，1&1 就返回1 ，如果为0，0&1 就返回0 2. 判断 奇偶性 如果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. 1 << m 定位到 n的第m位数 2. ~(1 << m) 将1进行非运算，变为 0，其他剩下的m位，变成 1，而 &1，是无实际作用的 3. n & 0 ：& 按位与运算 只有对应的两个数 全部为1时，结果才为1，而&0，返回值一定为 0 ### or运算 > 只有对应的两个 二进制数，均为0，结果才为 0，否则为 1 #### | 1 **将 n的第m位数，重置为1** 基本应用：n | (1 << m): 1. 1 << m 定位到 n 的第m位数 2. n | 1 n的第m位数 进行 |1 操作 其返回值必定为 1！ 因为|只有，两个数都为 0时，结果才为 0 #### | 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. 1 << m ： 定位到 n的第m位数 2. 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 运算 1. **左移运算符 “<<”** 表达式：a << b a<>”** 表达式：a >> b a>>b的值是：将a各二进位全部右移b位后得到的值。右移时，移出最右边的位就被丢弃。 对于有符号数，如long,int,short,char类型变量，在右移时，符号位（即最高位）将一起移动，并且大多数C/C++编译器规定，如果原符号位为1，则右移时高位就补充1，原符号位为0，则右移时高位就补充0。 ``` 实际上，右移n位，就相当于左操作数除以2n，并且将结果往小里取整。 例如：-25 >> 4 = -2 -2 >> 4 = -1 18 >> 4 = 1 ``` ### 应用 #### 对2的整数幂进行模运算 ```cpp #include int main(){ int n,k; while(~scanf("%d %d",&n,&k)){ n<<=k;//相当于 n 乘以 2的 k次幂，并将结果赋给n n>>=k;//相当于 n除以 2的 k次幂，并将结果赋给n printf("%d\n",n); } return 0; } ``` #### 两数交换 ```cpp #include 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** ``` 例如：表达式“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的正整数幂 ```cpp #include 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 ``` 举个例子： 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为正数** #### 判断奇偶性 ```cpp #include 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的二进制：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位数，取其相反 *** ## 结束语 欢迎转载本站文章，请注明作者和出处 [simonaking.com](http://simonaking.com)。