位运算及诸技巧

位运算及诸技巧

位运算概念：基于二进制的位的运算
对于位运算，注意两点：
1.必须以二进制角度进行位运算
2.必须以补码角度进行位运算

位运算符：
(1) 按位取反 ~
求~1
具体过程
1的补码为：
0000 0000 0000 0000
0000 0000 0000 0001（补）
按位取反：
1111 1111 1111 1111
1111 1111 1111 1110（补）
变为原码：
1000 0000 0000 0000
0000 0000 0000 0010（原）
读数： -2

计算机验证

int n = 1;
printf("%d\n",~n);

输出结果为：-2

(2) 按位与 &
求12 & 5
具体过程
12的补码为：
0000 0000 0000 0000
0000 0000 0000 1100（补）
5的补码为：
0000 0000 0000 0000
0000 0000 0000 0101（补）
12&5：
0000 0000 0000 0000
0000 0000 0000 0100（原、补）
读数：4

计算机验证

printf("%d\n",12&5);

输出结果为：4

(3) 按位或 |
求12|5
具体过程
12的补码为：
0000 0000 0000 0000
0000 0000 0000 1100（补）
5的补码为：
0000 0000 0000 0000
0000 0000 0000 0101（补）
12|5：
0000 0000 0000 0000
0000 0000 0000 1101（原、补）
读数：13

计算机验证

printf("%d\n",12|5);

输出结果为：13

(4) 按位异或 ^
求12^5
具体过程
12的补码为：
0000 0000 0000 0000
0000 0000 0000 1100（补）
5的补码为：
0000 0000 0000 0000
0000 0000 0000 0101（补）
12^5：
0000 0000 0000 0000
0000 0000 0000 1001(原、补)
读数：9

计算机验证

printf("%d\n",12^5);

输出结果为：9

(5) 右移 >>
右移的概念：右移是指二进制数据整体右移，右移n位，最后的n位无论是几都去掉；最高位缺的部分需要补位；对于有符号数：最左侧缺的几位用符号位补齐；对于无符号数：最左侧缺的几位都用0补齐。
右移n位的本质为：除以2^n;
例子：求下列有符号数与无符号数右移两位后的值

char n = 0xAC;
具体过程
(1010 1100)补
n>>2 = (1110 1011)00(补)
（ 对于有符号数用符号位补齐）
变为原码：
1001 0101
读数：-21 十六进制补码表示：0xEB
计算机验证

  char n = 0xAC;
  printf("%d\n",n >> 2);

输出结果为：-21

unsigned char n = 0xAC;
具体过程
(1010 1100)补
n >> 2 = (0010 1011)00(补、原)
读数：43

计算机验证

  unsigned char n = 0xAC;
	printf("%d\n",n >> 2);

输出结果为：43

(6) 左移 <<
左移概念：不论左移几位，缺失的位有用0补齐。
左移n位的本质为:乘2^n
例子：输出1左移i位的值（i的范围为0~31）

	int n = 1;
	int i;

	for(i = 0;i < 32;i++) {
	printf("%d:%u %x\n",i,n << i,n << i);
	}

输出结果为：

位运算诸技巧

1.关于&
假设有一个数，现需要取这个数所对应的二进制的后三位。
如：n = 0100 0101
只想要后三位，&0 = 0；&1 = 本身
则n&7
0100 0101
& 0000 0111
n&7 0000 0101
进一步思考，从二进制角度看n%8也可取出后三位，但算术运算速度远低于逻辑运算速度（可以看成位运算）即用n&7代替n%8是为了加快运算速度。

2.关于异或
(1) 加密解密
加密：
明文 0100 1100
** 1000 0111
密文 1100 1011

解密：
若已知密文的加密方式及**，则可解密：
密文 1100 1011
** 1000 0111
铭文 0100 1100

(2) 局部按位取反
A B A^B
0 0 0
1 0 1
0 1 1
1 1 0
发现 A^0 = 本身
A^1 = !A
即想要取反的那位与1异或即可按位取反。
假设任意数num(假设是1B无符号数)，希望对b4b3b2按位取反，其他各位保持不变；特别提醒：1B数的每一位按照如下顺序命名：
b7b6b5b4b3b2b1b0
0 0 0 1 1 1 0 0
结果b7 b6 b5 !b4 !b3 !b2 b1 b0

3.设置某一位为0或1
设置某一位为1称为置位
设置某一位为0称为清位

被设置的位的范围在一个字节之内，即，在b0到b7范围内，为了操作方便，重新对一个字节的8位进行排列。
b0 b1 b2 b3 b4 b5 b6 b7

置位
已知num和i,num表示一个一字节数值，i表示从左向右这个字节的第i位，i取值从0到7，要求将num的第i位置位。

由于A|1 = 1； A|0 = 本身；让所要置位的那一位与1相或即可

xxxx xxxx
|
0000 0001
0000 0010
0000 0100
0000 1000
0001 0000
0010 0000
0100 0000
1000 0000

上述操作分别将num的第7位置位，第6位置位…第0位置位。相当于1 << 0，1<< 1 … 1<< 7.

观察发现：两列二进制数据后三位按位取反，回忆运算位技巧2中按位异或局部取反，即， 1 << (i^7)
用i把左移的位数表示出来！

总结：num不动,把1移到第i位，与num相或!即，((num) |=(1 << (i ^ 7 )))

清位

由于A&1 = 本身； A&0 = 0；让所要置位的那一位与0相与即可

xxxx xxxx
&
1111 1110
1111 1101
1111 1011
1111 0111
1110 1111
1101 1111
1011 1111
0111 1111

上述操作分别将num的第7位清位，第6位清位…第0位清位。相当于~（1 << 0），~（1<< 1） …~（ 1<< 7).

总结：num不动,把0移到第i位，与num相与!即，((num) &=（~(1 << (i ^ 7 )))）

取位

abcd efgh
&
0000 0001
取出最后一位：h

abcd efgn整体右移一位：
aabc defg
&
0000 0001
取出当前最后一位：g

以此类推得到结论： 将所取位移到数值的最右侧，然后和1相与，即可取出abcdefgh的每一位！即，(num >> ((i) ^ 7)) & 1