跳到主要内容

逻辑操作

早期的计算机设计和指令集主要针对整字（即整个数据单元）进行算术和逻辑运算操作。然而，在实际应用中，尤其是随着计算机技术的发展和软件复杂性的增加，对数据更精细的控制变得日益重要。

例如:

  • 位级操作: 在计算机硬件和软件层面支持对一个字中的单个或一组位进行操作，这对于实现诸如错误检测（如奇偶校验、CRC校验）、数据压缩、编码解码（如ASCII到EBCDIC转换）、权限控制（如访问控制位）以及硬件接口信号处理等任务至关重要。

  • 布尔逻辑: 逻辑门电路的设计和数字逻辑的应用也要求能够对位进行AND、OR、NOT等逻辑操作，这在计算机内部的控制电路中是基础性的工作。

  • 打包和拆包: 在通信协议、数据格式化等领域，经常需要将多个小的数据元素（比如单个字符或标志位）组合成一个较大的字，或者从一个字中提取特定的位字段，这些操作都依赖于位级操作指令。

    打包(Packing): 假设有一个结构体，包含两个8位的字符变量（在C语言中）

    struct {
        unsigned char a: 4; // 使用了4位
        unsigned char b: 3; // 使用了3位
        unsigned char c: 1; // 使用了1位
    } bit_fields;

    // 打包操作：将这三个独立的位字段组合到一个完整的字节中
    bit_fields.a = 10; // 设置a为十进制的10，即二进制的1010
    bit_fields.b = 5;  // 设置b为十进制的5，即二进制的101
    bit_fields.c = 1;  // 设置c为1

    // 此时，整个字节可能是这样的（具体取决于编译器的实现方式）:
    // 二进制表示: 1010 101 1，这个字节包含了三个位字段的数据 (或者 1 101 1010)
    C

    拆包(Unpacking): 反向的过程就是从一个字节中提取出特定的位字段:

    unsigned char packed_byte = ...; // 假设这是上面打包得到的字节

    // 拆包操作：从packed_byte中获取各个位字段的值
    bit_fields.a = (packed_byte >> 4) & 0x0F; // 右移4位并按位与，得到a的值
    bit_fields.b = (packed_byte >> 1) & 0x07; // 右移1位并按位与，得到b的值
    bit_fields.c = packed_byte & 0x01; // 直接按位与，得到c的值

    // 这样就从原始的packed_byte中分离出了三个独立的位字段信息
    C

    以上例子展示了如何通过位操作对数据进行打包和拆包，这种技术常用于优化存储空间、处理网络协议数据包以及硬件接口通信等方面。

因此，现代计算机的指令集架构中通常包含了丰富的位操作指令，允许程序员直接对数据的各个位进行操作，极大地增强了程序设计的灵活性和效率。

位操作​

位操作(Bitwise Operation): 位操作是对整数或其他二进制表示的数据的每个位进行单独操作。常见的位操作包括:

按位与(&)(AND): 同1为1​

运算法则: 同1为1

例如: x & 1 = x, x & 0 = 0 ( xx 是一个比特位)

作用:

  1. 保留某些位

    • 例如: 0b0010'1010, 需要保留低四位:
      • 0b0010'1010&0b0000'1111

  2. 清除某些位

    • 保留某些位 == 清除某些位

  3. 检查标志位

    • 例如: 检查第五位是否为1?
      • if(0b0010'1010&0b0001'0000) // true 则为1, 否则必是零

  4. 网络地址和子网掩码计算

    • 例如一个ipv4可以使用一个u_int32(32位无符号整数)表示, 然后每8位可以这样表示:255.255.255.255, 然后使用作用[1][2]即可计算子网掩码等

  5. 硬件接口控制

    • 许多硬件寄存器或端口通过特定位来控制功能或读取状态信息，程序员可以通过按位与操作读取或修改这些位字段。

  6. 数据有效性校验

    • 例如奇偶校验, x & 1 == 1则是奇数, 反之偶数, 等等

按位或(|)(OR): 有1为1​

运算法则: 有1为1

例如: x | 1 = 1, x | 0 = x ( xx 是一个比特位)

作用:

  1. 设置标志位

    • 例如把x的第k位设置为1:
      • x |= 1 << k

  2. 合并数据

    • 当需要合并两个独立的数据集但不关心彼此冲突的位时，可以用按位或操作将它们结合在一起。比如，存储用户权限时，不同的权限可以通过各自的位表示，多个权限通过按位或组合到一起形成完整的权限集合。

    例如，在计算机科学中，我们常常需要管理一组标志或属性，每个属性用一个单独的比特位来表示是否存在（1代表存在，0代表不存在）。

    假设你有一个用户权限系统，其中:

    权限A对应于第0位（即2^0=1）
    权限B对应于第1位（即2^1=2）
    权限C对应于第2位（即2^2=4）
    C

    如果用户1拥有权限A和权限C，则其权限可以表示为:

    user1_permissions = 0b0101 // 这是一个二进制数，等价于十进制的5
    C

    另一个用户2可能只拥有权限B:

    user2_permissions = 0b0010 // 这是一个二进制数，等价于十进制的2
    C

    现在，如果你想合并这两个用户的权限，使得结果包含他们各自的所有权限，你可以使用按位或运算符|:

    merged_permissions = user1_permissions | user2_permissions
    C

    计算后得到:

    merged_permissions = 0b0111 // 这是一个二进制数，等价于十进制的7
    C

    在这个例子中，通过按位或运算，结果中的每一位都是原两个用户权限对应的位中有1的那个位置上的值。因此，合并后的权限包括了所有原始的权限位——权限A、权限B和权限C。这样，我们就完成了对两个数据集（这里指两个用户的权限集合）的合并操作。

  3. 条件赋值

    • 可以用来实现条件性的修改整数值。例如，在某些场景下，可能希望仅当某个条件成立时才改变某个位置的比特，这时可以先对原始值进行非条件的按位与运算清除目标位，然后与新值按位或起来完成条件赋值。

  4. 硬件接口控制

    • 在与硬件通信时，设备寄存器通常有各种功能控制位，通过向这些寄存器写入经过按位或运算后的值，可以同时开启或关闭多个硬件特性或模式。

按位异或(^)(XOR): 不同为1​

运算规则: 不同为1

按位异或的性质:

  1. 满足交换律: a ^ b ^ c == a ^ c ^ b

  2. 满足结合率: a ^ (b ^ c) == (a ^ b) ^ c

  3. 自反性:

    • a ^ a == 0

  4. 与零不变性:

  • a ^ 0 == a

作用:

  1. 不改变原始数据进行翻转特定位

    • 例如: Q1-3120. 统计特殊字母的数量 I中实现的位运算版本的字符字母大小写转换
    • 如果 原本的位是 1, 则变 0
    • 如果 原本的位是 0, 则变 1
      • 例如: 0b0010'1010^0b0000'1000可以翻转第四位

  2. 交换两个变量的值(无需临时变量)

    • 即:
    // 交换 a, b 的值
    void swap(int& a, int& b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
    C++
    • 以下是推导过程:
    // 现在假设 a实际值为x, b实际值为y

    a = a ^ b = x ^ y;
    b = a ^ b = (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x; // 自反性
    a = a ^ b = (x ^ y) ^ x = x ^ x ^ y = y;

    // 得: a = y, b = x
    C++
    • 可以写成偷懒的高深的形式:
    void swap(int& a, int& b) { // 这个是ok的
        a ^= b;
        b ^= a;
        a ^= b;
    }

    // 不确定可用性, GPT-3.5 和 4.0(必应) 都说这个是未定义行为, 但是oi-wiki是这样写的qwq... // -> https://oi-wiki.org/math/bit/#%E4%BA%A4%E6%8D%A2%E4%B8%A4%E4%B8%AA%E6%95%B0
    void swap(int& a, int& b) {
        a ^= b ^= a ^= b;
    }
    C++

    对于临时变量法，每次赋值只要读取一个变量的值到寄存器，然后再从寄存器写回到另一个变量中即可，前后涉及两次内存写入操作；但是对于异或运算操作，每次都需要读取两个数据到寄存器中，再进行运算操作，之后把结果写回到变量中，前后共需要三次内存写入操作。另外一点，异或操作的代码可读性差。[菜鸟教程 C 关于使用异或运算交换两数的值]

  3. 计算奇偶校验位

    • 在数据传输和存储时，异或运算常用于生成奇偶校验位，比如单个位的奇校验或偶校验。所有数据位通过异或运算得到的结果即为校验位，当数据在传输过程中发生错误时，可以通过重新计算并比较校验位来检测错误。

按位取反(~)(NOT/Complement)​

作用:

  1. 反转二进制位
  2. 计算数值的补码形式
  3. 创建掩码

    • 如果想要设置整数的特定位，可以使用一个只有特定位置为1的位掩码，并将其与整数进行按位或操作。例如，要设置整数 x 的最低位，您可以使用 x|= 1;。

    • 要清除整数的特定位，可以使用一个除了特定位为0外其他位都为1的位掩码，并将其与整数进行按位与操作。例如，要清除整数 x 的最低位，可以使用x &= ~1;或者 x &= 0xFE; (假设整数是8位)。

    • 在进行位级逻辑操作时，也可以用按位与常用于生成位掩码，用于清除或设置特定的位。比如想要清除一个整数的所有位（即将其设置为0），应该使用x &= 0;

    • 总之，位掩码是通过按位逻辑操作（如按位与、按位或、按位非等）来设置、清除或翻转整数的特定位的一种有效方法。

  4. 判断奇偶性

左移(<<)(Left Shift)​

将一个数的所有位向左移动指定次数，空出的低位补零。

作用:

  1. 乘以2的幂
  2. 设置标志位
  3. 优化内存访问
    • 对于某些类型的数组或数据结构，左移可能用于根据索引快速定位元素，特别是在处理按固定字节宽度存储的数据时。

右移(>>)(Right Shift)​

将一个数的所有位向右移动指定次数，高位是符号位时，可能补符号位(算术右移)，也可能补0(逻辑右移)。

作用:

  1. 除以2的幂
    • 注: 右移是向下取整, 而C/C++的整除/是向0取整! (特别注意右移一个负数的情况! (-5 >> 1 == -3, -5 / 2 == -2))[1]
  2. 快速除法和乘法
  3. 提取低阶位信息

逻辑操作(Logical Operation)​

逻辑操作(Logical Operation): 在更广义的范畴内，逻辑操作通常指的是布尔逻辑运算，包括与、或、非三种基本逻辑关系。在计算机编程中，这些逻辑操作既可以应用于位操作，也可以应用于更高层次的数据结构和变量（如条件判断语句中的真值）。例如，在C语言中，&&、||和!运算符就是进行逻辑与、逻辑或和逻辑非操作。

具体略

虽然逻辑操作和位操作有区别，但在处理二进制位级别的数据时，二者往往是交织使用的。例如，通过位与操作可以实现 掩码(masking) 和 清除特定位 的功能；位或操作可用于设置特定位；而异或操作在某些情况下可以用于交换两个变量的值，或者进行简单的错误校验等。

标注​

[1]​

对于 C/C++ 语言, 移位运算中如果出现如下情况，则其行为未定义:

  1. 右操作数（即移位数）为负值；
  2. 右操作数大于等于左操作数的位数；

例如，对于int类型的变量a，a << -1和a << 32都是未定义的。 对于左移操作，需要确保移位后的结果能被原数的类型容纳，否则行为也是未定义的。1 对一个负数执行左移操作也未定义。2

对于右移操作，右侧多余的位将会被舍弃，而左侧较为复杂：对于无符号数，会在左侧补 0；而对于有符号数，则会用最高位的数（其实就是符号位，非负数为 0，负数为 1）补齐。3

  1. 适用于 C++14 以前的标准。在 C++14 和 C++17 标准中，若原值为带符号类型，且移位后的结果能被原类型的无符号版本容纳，则将该结果 转换 为相应的带符号值，否则行为未定义。在 C++20 标准中，规定了无论是带符号数还是无符号数，左移均直接舍弃移出结果类型的位。

  2. 适用于 C++20 以前的标准。

  3. 这种右移方式称为算术右移。在 C++20 以前的标准中，并没有规定带符号数右移运算的实现方式，大多数平台均采用算术右移。在 C++20 标准中，规定了带符号数右移运算是算术右移。

来源: io-wiki 位运算

编辑此页
最后由 Heng_Xin_666 于 更新
请作者喝奶茶:
Alipay IconQR Code
Alipay IconQR Code
本文遵循 CC CC 4.0 BY-SA 版权协议, 转载请标明出处
Loading Comments...
0%