位运算是指按二进制进行的运算。在系统软件中，常常需要处理二进制位的问题。C语言提供了6个位操作运算符，这些运算只能用于整型操作数，即只能用于带符号或无符号的char、short、int与long类型。浮点数因为浮点型和整型在计算机内的存储方式大相径庭，同样是32位。但是浮点数是1位表示符号位，23位表示数值部分，8位其他表示指数部分。而整型只是单纯32位补码形式存放的，这就是位运算不能用于浮点数的原因。
1、“按位与”运算符（&）
按位与是指:参加运算的两个数据，按二进制进行“与”运算。如果两个相应的二进制位都位1，则该位的结果为1；否则为0。这里的1的可以理解为逻辑中的true，0可以理解为逻辑的false。按位与其实与逻辑上“与”的运算规则一致。逻辑上的“与”，要求运算数全真，结果才为真。若A=true， B=true，则A∩B=true 例如：3&5， 3的二进制编码是11(2)。（为了区分十进制和其他进制，本文规定，凡是非十进制的数据均在数据后面加上括号，括号中注明其进制，二进制则标记为2，内存储存数据的基本单位是字节(Byte)，一个字节由8个位(bit)所组成。位是用以描述电脑数据量的最小单位。二进制系统中，每个0或1就是一个位。将11(2)补足成一个字节，则是00000011(2)。5的二进制编码是101(2)，将其补足称一个字节，则00000101(2)。
按位与运算：
0000 0011(2) & 000000101(2) = 00000001(2)
由此可知3&5 = 1。
C语言代码：
1 #include <stdio.h> 2 3 int main(void) { 4 int a = 3, b = 5; 5 printf("a and b: %d\n", a & b); //0011 & 0101 6 return 0; 7 }
CPU处理位运算的速度是最快的，所以很多操作我们都可以转换为位运算，以下是用按位与替换取模运算进行奇偶数判断。
1 /************************************************************************* 2 > File Name: 2.test.c 3 > Author: yudongqun 4 > Mail: qq2841015@163.com 5 > Created Time: Sun 18 Oct 2020 10:19:55 PM CST 6 ************************************************************************/ 7 #include <stdio.h> 8 9 int main(void) { 10 int n; 11 printf("please input a integer:"); 12 while (scanf("%d", &n) != EOF) { 13 //if(n % 2) { 14 if (n & 1) { 15 printf("Odd number\n"); //奇数 16 } else { 17 printf("Even number\n");//偶数 18 } 19 printf("please input a integer:"); 20 } 21 return 0; 22 }
编译运行，并输入数字来测试，结果如下：
ydqun@VM-0-9-ubuntu 20201017 % g++ 2.test.c [0] ydqun@VM-0-9-ubuntu 20201017 % ./a.out [0] please input a integer:3 Odd number please input a integer:2 Even number please input a integer:% ydqun@VM-0-9-ubuntu 20201017 %
14行就是用&运算符去代替%运算符实现奇偶数判断，这样效率更快。
2.按位或运算符
两个相应的二进制位中只要有一个为1，该位的结果值为1。借用逻辑学中或运算的话来说就是，一真为真。
例如 十进制6对应二进制0000 0110与8对应的二进制0000 1000进行或运算，0000 0110 | 0000 1000 = 0000 1110，对应十进制的14。
测试的c语言代码。
1 /************************************************************************* 2 > File Name: 3.test.c 3 > Author: yudongqun 4 > Mail: qq2841015@163.com 5 > Created Time: Mon 19 Oct 2020 05:14:44 PM CST 6 ************************************************************************/ 7 8 #include <stdio.h> 9 10 int main(void) { 11 int n = 8, m = 6; 12 printf("%d | %d = %d\n", n, m, n | m); 13 return 0; 14 }
3.异或运算
异或是一个数学运算，用于逻辑运算。如果a、b两个值不同，则异或结果为1，否则结果为0，在C语言中是一种强大的基本运算符，有很多巧妙的应用。
例如, A = 14, B = 10;
A = 14，二进制则为1110，B = 10，二进制为1010.
对二进制数进行异或运算 -> 1110^1010 = 0100，对应十进制就为4。
在二进制数异或过程中，我们可以得知异或运算是一种半加运算。什么意思呢？半加即不带进位的加法运算。
如上面1110^1010 = 0100，如果在加法中，如下
我们从低位开始加起，首先第0位为0+0=0；第一位1+1=0，如果是加号运算符，则需要进位，但由于是异或运算（半加），故不用进位，第二位为1+0=1；最后一位为1+1=0。最终结果就是0100，这就是半加的过程。
特性
1.一个数与0进行异或运算，其运算结果是自身；
2.一个数与自身进行异或运算，其运算结果为0；
3.异或运算满足分配律，即 3^4^3与3^3^4的结果一样，都为4。
异或运算的一些应用
1.异或最常用的一种用法 -- 交换两个数的值。
这里直接上代码。
1 /************************************************************************* 2 > File Name: swap.c 3 > Author: yudongqun 4 > Mail: qq2841015@163.com 5 > Created Time: Fri 16 Oct 2020 04:48:54 PM CST 6 ************************************************************************/ 7 8 #include <stdio.h> 9 10 int main(void) { 11 int a = 10, b = 20, tmp; 12 13 #if 0 14 /*用中间值来实现值交换*/ 15 tmp = a; 16 a = b; 17 b = tmp; 18 #else 19 /*用异或操作来实现值交换*/ 20 a ^= b; 21 b ^= a; 22 a ^= b; 23 #endif 24 printf("a: %d, b: %d\n", a, b); 25 26 return 0; 27 }
ydqun@VM-0-9-ubuntu operator % gcc swap.c [0] ydqun@VM-0-9-ubuntu operator % ./a.out [0] a: 20, b: 10 ydqun@VM-0-9-ubuntu operator %
这里异或操作实现的值交换的好处是少使用了一个临时变量，执行效率也比较高。
2，寻找只出现一次的数字。
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
1 /************************************************************************* 2 > File Name: single_number.c 3 > Author: yudongqun 4 > Mail: qq2841015@163.com 5 > Created Time: Fri 16 Oct 2020 05:20:25 PM CST 6 ************************************************************************/ 7 8 #include <stdio.h> 9 10 int single_number(int nums[], int n) { 11 int res = 0; 12 for (int index = 0; index < n; index++) { 13 res ^= nums[index]; 14 } 15 return res; 16 } 17 18 int main(void) { 19 int nums[5] = {1, 2, 2, 1, 6}; 20 printf("single number is : %d\n", single_number(nums, 5)); 21 }
ydqun@VM-0-9-ubuntu operator % g++ single_number.c [0] ydqun@VM-0-9-ubuntu operator % ./a.out [0] single number is : 6 ydqun@VM-0-9-ubuntu operator %
这里是运用了异或的特性2与特性3，1^2^2^1^6 = 1^1^2^2^6 = 0^0^6 = 6。
4.按位取反运算
按位取反运算符是把一个数的二进制照着每个位取反，即值为0的位变为1，值1的位变为0，但是我们要注意的是，要结合二进制数在内存中是以补码的形式存储的情况一起分析（不知道补码概念请看https://www.cnblogs.com/ydqblogs/p/13823206.html），接下来我们以10按位取反为例子。
假设我们有一个整型变量x = 10，在计算机中一个整型树为4个字节，而一个字节为8位，所以数字10在计算机中存储占32位，且为补码存储在内存中，即
原 码：00000000 00000000 00000000 00001010
补 码：00000000 00000000 00000000 00001010
按位取反：11111111 11111111 11111111 11110101
这时候，“~10”的二进制数的最高位是1表示它是一个负数，它是在内存的存储时的值（补码），我们需要求回原码。由补码求原码的操作跟由原码求补码的操作是一样的。
接着上述：11111111 11111111 11111111 11110101
反 码：10000000 00000000 00000000 00001010
补 码：10000000 00000000 00000000 00001011
二进制10000000 00000000 00000000 00001011对应十进制是-11，这时候我们推导出~10=-11，我们可以写一个程序测试一下我们的推导结果。
1 /************************************************************************* 2 > File Name: bit_reverse.c 3 > Author: yudongqun 4 > Mail: qq2841015@163.com 5 > Created Time: Tue 20 Oct 2020 09:25:50 AM CST 6 ************************************************************************/ 7 8 #include <stdio.h> 9 10 int main(void) { 11 printf("%d\n", ~10); 12 return 0; 13 }
ydqun@VM-0-9-ubuntu 20201017 % g++ bit_reverse.c [0] ydqun@VM-0-9-ubuntu 20201017 % ./a.out [0] ~10 = -11
由测试程序得出的结果，我们可以验证我们的推导是正确的，所以我们可以看出一个规律：正整数x，~x = -（x+1）。接下来我们来推导一下负整数按位取反的结果。
假设我们有一个负数-10，我们来推导一下按位取反后的结果。
原 码：10000000 00000000 00000000 1010
反 码：11111111 11111111 11111111 0101
补 码：11111111 11111111 11111111 0110
按位取反：00000000 00000000 00000000 1001
我们发现负数在内存中存储的值在按位取反，符号位为0，即变为了正数，我们知道正数的补码和原码是一样的，在内存中的补码就是在程序中实际的原码，由此得到：对于负数-x，~(-x) = x-1。同样我们可以写一个测试程序。
ydqun@VM-0-9-ubuntu 20201017 % g++ bit_reverse.c [1] ydqun@VM-0-9-ubuntu 20201017 % ./a.out [0] ~(-10) = 9
至此我们可以得出一个结论。
对于正整数x，~x = -（x + 1）;
对于负整数-x, ~（-x） = （x - 1）。
5.左移运算符 -- <<
左移运算符是一个计算机用语，用来将一个数的各二进制位全部左移若干位，移动的位数由右操作数指定，右操作数必须是非负值，其右边空出的位用0填补，高位左移一处则舍弃该高位。
接下来，我们来各自分析正数和负数的左移过程。
假设我们有一个正整型数x，值为2，我们要分析它左移2位后的值为多少，即求 2 << 2。
原 码：00000000 00000000 00000000 00000010
补 码：00000000 00000000 00000000 00000010
左移两位：00000000 00000000 00000000 00001000
二进制数00000000 00000000 00000000 00001000对应的十进制值为8，由此我们得知2 << 2 = 8，由此，我们能得到对于一个正整数x，每左移一位，x的值就变为原来的2倍。那么负整数呢？左移运算结果又是多少？其实跟正整型数是一样的结果，只不过我们在左移运算的时候要关心符号位，即左移不影响符号位，移动的都是数据域。
假设我们有一个十六进制的负整型数0xc0000001，对应十进制值为-2147483646，我们要求左移一位后该数值为多少？
原 码：11000000 00000000 00000000 00000001
反 码：10111111 11111111 11111111 11111110
补 码：10111111 11111111 11111111 11111111
左移一位：11111111 11111111 11111111 11111110
反 码：10000000 00000000 00000000 00000001
原 码：10000000 00000000 00000000 00000010
由此我们得到0xc0000001左移一位后值为0x80000002。我们可以写一个程序测试一下。
1 /************************************************************************* 2 > File Name: left_shift.c 3 > Author: yudongqun 4 > Mail: qq2841015@163.com 5 > Created Time: Tue 20 Oct 2020 01:29:00 PM CST 6 ************************************************************************/ 7 8 #include <stdio.h> 9 10 int main(void) { 11 int num = 0xc0000001; 12 printf("0x%x << 1 = 0x%x\n", num, num << 1); 13 return 0; 14 }
ydqun@VM-0-9-ubuntu 20201017 % ./a.out [0] 0xc0000001 << 2 = 0x80000002 ydqun@VM-0-9-ubuntu 20201017 %
在这里，关于一个数左移一位为什么是原来数的两倍，我这里有个人的理解，首先，有一个名词叫位的权值，对于二进制数，每一位的权值为2n ，其中n表示第几位，所以我们得知第i位的权值是2i ，而第i+1为的权值为2i+1，所以往左移动一位，权值变为原来的2倍，则数的值也为原来的两倍。十进制数也是同样的道理。
5.右移运算符 -- >>
右移运算符和左移运算符大致一样，唯一区别就是方向不同，另外对于有符号整型数右移，左边是补符号位；而对于无符号整型数右移，左边补0。在这里我们只分析有符号的负整型数。
假设我们有一个x值为-10，我们把其右移两位。
原 码：10000000 00000000 00000000 00001010
反 码：11111111 11111111 11111111 11110101
补 码：11111111 11111111 11111111 11110110
右移两位：11111111 11111111 11111111 11111101 -- 因为是有符号且为负数，所以补1。
反 码：10000000 00000000 00000000 00000010
原 码：10000000 00000000 00000000 00000011
由上述分析结果得(-10) >> 2 = -3。我们可以写测试程序测试一下结果。
1 /************************************************************************* 2 > File Name: right_shift.c 3 > Author: yudongqun 4 > Mail: qq2841015@163.com 5 > Created Time: Tue 20 Oct 2020 04:33:18 PM CST 6 ************************************************************************/ 7 8 #include <stdio.h> 9 10 int main(void) { 11 int num = -10; 12 printf("%d >> 2 = %d\n", num, num >> 2); 13 return 0; 14 }
ydqun@VM-0-9-ubuntu 20201017 % g++ right_shift.c [0] ydqun@VM-0-9-ubuntu 20201017 % ./a.out [0] -10 >> 2 = -3
到了这里，我们已经学习完C语言的所有位运算符，下面我们来给出一些位运算的综合运用。
6、位运算的综合运用
