【C语言】->位运算详细解析->位运算的使用

Ⅰ 位运算的定义

我们知道程序中的所有数据，都是以二进制的方式存储在计算机中的。位运算就是基于二进制的位进行的运算，直接对整数的二进制位进行操作。因此考虑位运算有两个锚点：二进制，补码。
注意：计算机中所有的运算都没有位运算快

Ⅱ 位运算的符号

C语言中有以下六种位运算：

1. ~ ： 按位取反（单目运算）
2. & ： 按位与
3. | ： 按位或
4. ^ : 按位异或
5. << : 左移
6. >> : 右移

Ⅲ 位运算的验证及分析

a.按位取反 ~

以下为测试代码：????

#include <stdio.h>

int main() {
	int a = 1;
	int b = ~a;

	printf("a:%d b:%d\n", a, b);

	return 0;
}

我们令a = 1,对其取反，得到结果如下????

可以看到，对1取反结果是-2，为什么会这样？我们通过二进制和补码两个锚点做以下分析。

1为int类型，即32位，所以1的补码为：
(0000 0000 0000 0000 0000 0000 0000 0001)_补
对其按位取反，得到以下补码：
(1111 1111 1111 1111 1111 1111 1111 1110)_补
将这个补码化成原码，第一位为字符位，其余按位取反末位加1：
(1000 0000 0000 0000 0000 0000 0000 0010)_原 = -2

这便是-2的来历。

b.按位与 &

以下为测试代码????

#include <stdio.h>

int main() {
	int a = 1;
	int b = 0;

	printf("a & b = %d\n", a & b);
	printf("~a & b = %d\n", ~a & b);
	printf("a & ~b = %d\n", a & ~b);
	printf("~a & ~b = %d\n", ~a & ~b);

	return 0;
}

结果如下????

对于前三个结果我想大家应该都比较清楚，最后这个-2就很迷惑了，按照惯常想法，1和0的与结果要么是0要么是1，那我就再对这个结果进行以下分析????

根据第一个按位取反，我们可以直接写出~1和 ~0的结果：
(~1) _补 = (1111 1111 1111 1111 1111 1111 1111 1110)_补
(~0) _补 = (1111 1111 1111 1111 1111 1111 1111 1111)_补
将这两个补码进行按位与，得
(1111 1111 1111 1111 1111 1111 1111 1110)_补
将其化成原码得
(1000 0000 0000 0000 0000 0000 0000 0010)_原 = -2

c.按位或 |

以下为测试代码????

#include <stdio.h>

int main() {
	int a = 1;
	int b = 0;

	printf("a | b = %d\n", a | b);
	printf("~a | b = %d\n", ~a | b);
	printf("a | ~b = %d\n", a | ~b);
	printf("~a | ~b = %d\n", ~a | ~b);

	return 0;
}

结果如下????

运算规则和上面一样，我们可以发现 1 | ~0 = -1，所以位运算和逻辑运算是很不一样的，即使（ | ）和 （ || ）样子差别不大，但是用法差别很大，这点需要注意，验证过程我不再赘述。

d.按位异或 ^

验证代码如下????

#include <stdio.h>

int main() {
	int a = 1;
	int b = 0;

	printf("a ^ b = %d\n", a ^ b);
	printf("!a ^ b = %d\n", !a ^ b);
	printf("a ^ !b = %d\n", a ^ !b);
	printf("!a ^ !b = %d\n", !a ^ !b);

	return 0;
}

这次我们将~变成！，我们只看他们的逻辑关系，其本质还是一样的，是按照补码进行按位异或，结果如下????

e.左移 <<

测试代码如下????

#include <stdio.h>

int main() {
	int a = 8;
	int b;
	int c;

	b = a << 2;
	c = a << 3;

	printf("8 << 2 = %d\n", b);
	printf("8 << 3 = %d\n", c);

	return 0;
}

结果如下????

可以看到 8 << 2 = 32 , 8 << 3 = 64,分析如下????

(8)_补= (0000 0000 0000 0000 0000 0000 0000 1000)_补
8 << 2 = (0000 0000 0000 0000 0000 0000 0010 0000)_补
=32
所以结论是，当把一个数左移n时， 实质上是对这个数乘以2ⁿ。即，a << b = a * 2^b

f.右移 >>

测试代码如下????

#include <stdio.h>

int main() {
	int a = 7;
	int d = -32;
	int b;
	int c;

	b = a >> 2;
	c = d >> 2;

	printf("7 >> 2 = %d\n", b);
	printf("-32 >> 2 = %d\n", c);

	return 0;
}

结果如下????

根据左移的规则可以得出：a >> b = a / 2^b
但是右移有一个需要注意的地方，即右移的时候，在原来位置需要补的是符号位，即是正数则补0，是负数则补1，但是有几种特殊情况，比如单片机的程序，右移时在原来位置补0， 且恒补0，在这种场合中，可以将相关变量或者值，定义或强转成无符号数。

我们以 -32 >> 2 = -8为例，说明右移。

(-32)_原 = (1000 0000 0000 0000 0000 0000 0010 0000)_原
(-32)_补 = (1111 1111 1111 1111 1111 1111 1110 0000)_补
-32 >> 2 = (1111 1111 1111 1111 1111 1111 1111 1000)_补 = -8
/* 注意，我们在原来位置补的是1，因为符号位为1 */

Ⅳ 位运算的技巧

a.与运算

与运算的一个应用场合：子网掩码
与运算可以从一个字节中取出指定位的数据。
比如x的补码为(b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀)_补, 要取出b₂ ，b₁， b₀的数据，只需要x & 7。即(b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀)_补 & (0000 0111),结果就可以得到b₂ ，b₁， b₀的数据。

b.或运算

或运算可以将一个字节中的指定位设置为1
还是用x来举例，比如我们要将x的b₆，b₃ ，b₁设置为1，则
(b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀) | (0100 1010)
= ((b₇ 1 b₅ b₄ 1 b₂ 1 b₀)

c.异或运算

异或运算可以将一个字节中的指定位设置为其反
还是用x来举例，比如我们要将x的b₆，b₃ ，b₁设置为其反，则
(b₇ b₆ b₅ b₄ b₃ b₂ b₁ b₀) ^ (0100 1010)
= (b₇ !b₆ b₅ b₄ !b₃ b₂ !b₁ b₀)

d.左移右移

计算机中，所有的运算都不如位运算快。
这里提一个概念，计算机硬件中存在指令周期，一条指令的全过程称为一个指令周期，是由若干个时钟周期组成，不同指令的指令周期不同。位运算指令周期基本都是1时钟周期，四则运算基本都是16~32 时钟周期，乘法运算大概是加减运算的2-4倍。
比如 x * 94 = x * (64 + 32 - 2) = x * 64 + x * 32 - x * 2
= (x << 6) + (x << 5) - (x << 1)
所需要的时钟周期从16*3 = 48 变成了 1 + 1 + 1 + 16 + 16 = 35，虽然是微小的差距，但是在解决极致问题时能提供很多时间的节省空间。

Ⅴ 位运算的重要应用

位运算有三个基本操作，置位，清位及取位。其在比如哈夫曼压缩解压缩中十分重要，我会分别进行分析并将其写成代码，以便以后的使用。

a.置位

置位即将某一字节的指定位上置为1。

根据之前的内容可知，我们可以用按位或运算来进行置位。设index为需要置为1的位，value为需要置位的字节的十进制值，t为value通过其置位的补码的十进制值。

下标	0123 4567
	xxxx xxxx

                                                   按位或????

对下标为0置位	1000 0000
对下标为1置位	0100 0000
对下标为2置位	0010 0000
对下标为3置位	0001 0000

以上的表就是对各个位置位的规律， 即(value | 1 << (7-index))，其中，
7-index = index ^ 7，各位可以自行验证。所以最终，value |= 1 << (index ^ 7),即可完成value中对index位的置位。
我们可以将其写成一个宏，写到自己常用的头文件里。

#define SET(value, index)  (value |= 1 << (index ^ 7))

b.清位

清位即将某一字节的指定位置为0。

下标	0123 4567
	xxxx xxxx

                                                    按位与????

对下标为0清位	0111 1111
对下标为1清位	1011 1111
对下标为2清位	1101 1111
对下标为3清位	1110 1111

同样我们找出下标index与t的关系，可以得到：
value &= ~(1 << (index ^ 7))

#define CLEAR(value, index)  (value &= ~(1 << (index ^ 7)))

c.取位

取位即得到某个字节的指定位的数据。

下标	0123 4567
	xxxx xxxx

                                                    按位与????

对下标为0取位	1000 0000
对下标为1取位	0100 0000
对下标为2取位	0010 0000
对下标为3取位	0001 0000

所以取位所用的t和置位是一样的，我们只需要增加一个逻辑判断，即
(value) & (1 << (index ^ 7)) != 0
前面的位运算可以得到该位的值，后面!= 0的逻辑判断，便可以将这个表达式的值变得和所要的位的值相同。

#define GET(value, index)    ((value) & (1 << (index ^ 7)) != 0)

以上就为位运算的分析及应用介绍，之后我会写利用哈夫曼编码将文件压缩及解压缩的程序，其中便会用到这三个宏。