日常使用和刷题所积累下来的一些关于位操作经验技巧

1. 掩码

在对有些寄存器操作的时候没有办法改变单一位的值，比如说十六个io口用一个十六进制的数来表示，端口当对应的值为1的时候输出高电平，反之则输出低电平，如何只改变其中的某些端口的输出电平而不改变其他端口的电平呢？这就需要用到掩码了，比如是初始值为0xFF需要将其变成0xFE，可以定义一个掩码为0xFE，将其与0xFF进行与运算即可获得想要的数字了

int source = 0xFF;
int mask = 0xFE;
printf("%x\n", source & mask)

输出为0xFE，这个是通过掩码清零指定的位，如果需要置高指定位则需要使用与操作了，比如是要把0xFE变成0xFF则需要定义一个掩码0x01来与0xFE相与

int source = 0xFE;
int mask = 0x01;
printf("%x\n", source | mask);

输出结果为0xFF。

2. 将最后一个高位置零

int result = source & (source -1);

练习

前 n 个数字二进制中 1 的个数

3. 获取最后一位高位

int result = source & (-source);

4. 通过移位来实现乘法与除法

这部分是在CSAPP中学到的，由于乘法与除法在CUP中的计算指令执行时间较长所以通常编译器会使用移位操作和加法操作来代替一般的乘法或除法操作，优化程序执行速度

4.1 除法

将一个数向右移动$n$个单位则是将其除以$2^n$，比如

int source = 100;
int result = source >> 2;
printf("result = %d\n", result);

输出结果为25，就相当于是100除以$2^2 = 4$ 。

4.2 乘法

乘法与除法类似只是移动方向相反，将一个数向左移动$n$个的那位则是将其乘以$2^n$, 比如

int source = 3;
int result = source << 1;
printf("reslut = %d\n", result);

输出结果为6，就相当于6乘以$2^1 = 2$ 。

5. 异或操作的一些性质

There are 4 very important properties of XOR that we will be making use of. These are formal mathematical terms but actually the concepts are very simple.

1. Commutative : A ⊕ B = B ⊕ A

   This is clear from the definition of XOR: it doesn’t matter which way round you order the two inputs.

2. Associative : A ⊕ ( B ⊕ C ) = ( A ⊕ B ) ⊕ C

   This means that XOR operations can be chained together and the order doesn’t matter. If you aren’t convinced of the truth of this statement, try drawing the truth tables.

3. Identity element : A ⊕ 0 = A

   This means that any value XOR ’d with zero is left unchanged.

4. Self-inverse : A ⊕ A = 0

   This means that any value XOR ’d with itself gives zero.

These properties hold not only when XOR is applied to a single bit, but also when it is applied bitwise to a vector of bits (e.g. a byte).

练习

single element in a sorted array