关于位操作的一些使用技巧

2022/04/13

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

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);
decimal source source-1 result
3 0011 0010 0010
5 0101 0100 0100
4 0100 0011 0000

练习

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

3. 获取最后一位高位

int result = source & (-source);
decimal source -source result
3 0011 1101 0001
5 0101 1011 0001
4 0100 1100 0100

4. 通过位运算实现加减乘除

由于乘法与除法在CUP中的计算指令执行时间较长所以通常编译器会使用移位操作和加法操作来代替一般的乘法或除法操作,优化程序执行速度。加法与减法是再刷Leetcode的时候遇到的,实际编程中应该用不到,可以了解一下。

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\)

4.3 加法

位运算的加法与我们在数学课上将两个数相加一样,对每个对应位相加然后,然后有进位的就进位。这里可以通过异或(XOR)计算忽略进位的相加,然后用AND左移一位计算进位,通过迭代使最后的进位为0,就完成计算。

int add(int a, int b) {
    while (b) {
        int x =  a ^ b;     // XOR(1 1 0, 0 0 0)
        b = a & b;      // 重新计算进位
        a = x;
        b = (unsigned)b << 1;       // 进位不可以为负数
    }
    return a;
}

4.4 减法

明白了上面的加法之后减法就非常简单了,直接使用b = -b就可以了

int sub(int a, int b) {
    b = -b;
    while (b) {
        int x =  a ^ b;     // XOR(1 1 0, 0 0 0)
        b = a & b;      // 重新计算进位
        a = x;
        b = (unsigned)b << 1;       // 进位不可以为负数
    }
    return a;
}

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

剑指 Offer 56 - I. 数组中数字出现的次数