C 语言提取位

位操作是编程中的一个基本方面，尤其是在系统编程、嵌入式系统和对性能要求严格的应用中。位操作的一个常见操作是从数据中提取特定位。在 C 编程语言中，使用位运算符可以高效地处理位提取，使程序员能够直接与数据的二进制表示进行交互。此操作对于解析二进制文件格式、管理硬件寄存器、优化数据存储和实现加密算法等任务至关重要。

从本质上讲，位提取涉及在整数或类似数据类型中隔离特定位。最基本形式的此操作是提取单个位，这可以通过按位移位（'>>'）和按位 AND（'&'）操作的组合来实现。例如，要确定数字中某个特定位的值，可以使用按位移位运算符将目标位移动到最低有效位位置，然后与 '1' 进行 AND 操作以隔离该位的值。

更复杂的情况涉及提取多个位，通常是连续的位，以从数据字中获取子字段。这在网络中很常见，数据包中的标头包含打包在二进制结构中的各种字段。在这里，可以使用掩码来清除不需要的位，只留下感兴趣的位。通过将所需的低位设置为 '1' 并移位数据后应用按位 AND 操作来创建此掩码。

C 语言中的位操作不仅仅是访问或修改低级别数据；它还涉及效率和可移植性的考虑。例如，字节序（数据存储的字节顺序）会影响位如何被提取和解释，尤其是在具有不同硬件架构的系统中。因此，对底层硬件的透彻理解和对数据表示的仔细处理至关重要。

方法一：位运算

提取单个位

要从整数中的特定位置提取单个位，我们使用按位右移（'>>'）和按位 AND（'&'）操作的组合。

程序

输出

 
Extracting single Bit:
Number: 172 (Binary: %08b), Position: 172
Shifted Number: 21 (Binary: %08b)
Extracted Bit: 1
Extracting single Bit:
Number: 218 (Binary: %08b), Position: 218
Shifted Number: 6 (Binary: %08b)
Extracted Bit: 0
Extracting multiple bits:
Number: 172 (Binary: %08b), Start: 172, Number of Bits: 2
Mask: 15 (Binary: %08b)
Shifted Number: 43 (Binary: %08b)
Extracted Bits: 11 (Binary: %04b)
Extracting multiple bits:
Number: 218 (Binary: %08b), Start: 218, Number of Bits: 1
Mask: 7 (Binary: %08b)
Shifted Number: 109 (Binary: %08b)
Extracted Bits: 5 (Binary: %03b)
Results:
Single Bit from number1 at position 3: 1
Single Bit from number2 at position 5: 0
4 Bits from number1 starting at position 2: 11
3 Bits from number2 starting at position 1: 5   

说明

提供的 C 代码演示了使用位运算从整数中提取单个位和多个位。它包含两个主要函数：一个用于提取单个位，另一个用于提取多个位，并提供类似日志的输出以显示这些操作的内部状态和结果。

• 提取单个位的函数
  函数 extract_single_bit(int number, int position) 接受两个参数：number（要从中提取位的整数）和 position（要提取的位位置）。该函数使用位运算来隔离并返回指定位置的位的值。
  右移（'>>'）：输入数字右移 position 位，将目标位移动到最低有效位（LSB）位置。此操作会有效地丢弃目标位右边的所有位。
  按位 AND（'&'）：右移的结果然后与 1（二进制 0001）进行 AND 操作。此操作会清除除 LSB 之外的所有位，从而隔离感兴趣的位。之后，提取的位会被记录下来并由函数返回。
  函数中的日志语句以十进制和二进制格式打印原始数字、移位后的数字以及提取的位。这提供了对位操作过程和中间值的清晰视图。
• 提取多个位的函数
  函数 extract_multiple_bits(int number, int start, int num_bits) 从输入整数中提取位范围。参数是 number（要从中提取位的整数）、start（起始位位置）和 num_bits（要提取的位数）。
  掩码创建：使用表达式 (1 << num_bits) - 1 创建一个包含 num_bits 个连续 1 的掩码。此掩码稍后将用于从移位后的数字中隔离所需的位。
  右移（'>>'）：与单比特提取类似，该函数将输入数字右移 start 位。此操作会将目标位范围与 LSB 对齐。
  按位 AND（'&'）：使用 AND 操作将掩码应用于移位后的数字。此步骤会将除对应于掩码的位之外的所有位清零，从而有效地提取所需的位范围。
  该函数以十进制和二进制形式记录原始数字、掩码、移位后的数字以及提取的位。这有助于说明按位运算如何隔离特定位。
• 主函数和测试用例
  主函数设置了两个示例整数（number 1 和 number 2）并测试提取函数。它演示了从不同位置提取单个位以及提取多个位。将打印结果（包括提取位的值），从而提供位提取过程的端到端示例。

复杂度分析

时间复杂度

时间复杂度衡量代码执行的操作数与输入大小的关系。在这种情况下，输入大小与整数中的位数有关。

提取单个位

函数 extract_single_bit(int number, int position) 涉及

右移操作（'>>'）：此操作将整数的位向右移位。右移操作的时间复杂度为O(1)，因为它是一项基本操作，由处理器以恒定时间执行，与移位的位数无关。

按位 AND 操作（'&'）：此操作的时间复杂度也为 O(1)，因为它只是比较数字和掩码（在这种情况下为 1）的相应位。

提取单个位的总体时间复杂度为 O(1)，因为右移和按位AND 操作均以恒定时间执行。

提取多个位

函数 extract_multiple_bits(int number, int start, int num_bits) 涉及

掩码创建：使用 (1 << num_bits) - 1 创建掩码。这涉及位移和减法操作。位移的复杂度为 O(1)，因为它取决于处理器的字大小，而不是 num_bits 的实际值。

右移操作（'>>'）：与单比特提取类似，此操作将整数移位恒定的位数，导致O(1)复杂度。

按位 AND 操作（'&'）：将掩码应用于移位后的数字以隔离感兴趣的位也是一个 O(1) 操作。

因此，提取多个位的时间复杂度也为 O(1)，因为所有操作（按位移位、掩码创建和按位 AND）都是恒定时间操作。

空间复杂度

空间复杂度是指算法所需的内存量与输入大小的关系。

提取单个位

提取单个位的空间复杂度为 O(1)，因为只使用了少数几个额外的整数变量（number、position 和 extracted_bit）。这些变量占用恒定的内存空间，与输入大小无关。

提取多个位

同样，提取多个位的空间复杂度也为 O(1)。该函数使用几个整数变量（number、start、num_bits、mask 和 extracted_bits），所有这些变量都占用恒定的内存空间。这些变量的大小不取决于提取的位数或输入整数的大小。

主函数

主函数初始化了几个整数并调用了位提取函数。这些整数和函数调用的内存使用量也为 O(1)。函数本身不创建大量额外的数据结构或分配动态内存，从而确保总体空间复杂度保持恒定。

方法二：C 语言中的联合体进行类型双关

C 语言中的联合体是一种特殊的数据结构，它允许不同的数据类型共享同一内存位置。这意味着联合体可以存储不同类型的数据，但一次只能存储一种类型。其最大成员的大小决定了联合体的大小，并且可以随时访问任何成员，根据成员的数据类型解释内存的底层字节。

联合体的这一特性可用于类型双关，这是一种通过不同类型访问或解释相同数据​​的技术。类型双关在低级编程中特别有用，例如系统编程、嵌入式系统以及处理硬件接口时，其中需要直接操作底层数据表示。

联合体如何工作？

在联合体中，所有成员都从相同的内存地址开始，这意味着它们是重叠的。在向一个成员写入后访问另一个成员可能会改变数据的解释，从而提供对组成该值的原始位的视图。

程序

输出

 
Using union to interpret float as int:
Float value: 3.141590
Interpreted as integer: 1078530000
Raw bytes: d0 0f 49 40 
Using union to interpret int as float:
Integer value: 1078530016
Interpreted as float: 3.141594
Raw bytes: e0 0f 49 40 
Byte array from float 3.141590:
d0 0f 49 40 
Float value obtained from a byte array:
Float value: 3.141590   

说明

• 联合体定义和目的
  联合体 DataUnion 定义了三个成员：一个整数 (i)、一个浮点数 (f) 和一个字符数组 (bytes)。所有这些成员都占用相同的内存空间，这允许对相同二进制数据进行不同的解释。联合体的大小由其最大成员决定，在本例中是 4 字节的 bytes 数组。这种设置使我们能够通过不同的格式查看和操作相同的数据。
  函数描述
  将浮点数打印为整数
  printFloatAsInt 函数演示了浮点数如何在内存中存储以及如何将其解释为整数。它在联合体中设置浮点值并打印它。由于共享内存空间，浮点数的位模式也被解释为整数。此函数输出
  浮点数位模式的整数表示显示了字节是如何被不同解释的。原始字节值提供浮点数位模式的十六进制视图。
  这对于理解浮点数是如何在二进制中表示的以及它们的位模式如何被视为整数很有用。
  将整数打印为浮点数
  printIntAsFloat 函数通过在联合体中设置整数值然后将其解释为浮点数来反转此过程。此函数
  显示整数值。
  显示将相同位模式解释为浮点数的结果的浮点值。打印整数的原始字节表示。
  此函数说明如何将整数的位模式重新解释为浮点数，这有助于理解数据编码和类型之间的转换。
• 字节数组转换函数
  convertBytesToFloat 和convertFloatToBytes 函数促进了浮点值和字节数组之间的转换。这些函数使用 memcpy 在联合体的 bytes 数组和其他数据类型之间传输数据
  1. convertFloatToBytes 函数将表示浮点值的字节复制到字节数组中。它对于序列化或需要原始字节格式的数据传输等任务很有用。
  2. convertBytesToFloat 函数将一个字节数组复制到联合体中并检索相应的浮点值。此函数有助于从字节流中重构数据或解释从二进制文件中读取的数据。
• 主函数
  主函数作为对先前定义的函数的实际演示
  之后，它使用printIntAsFloat 来演示如何将一个整数（1078530016）视为浮点数，包括其原始字节表示。接下来，它将浮点数转换为字节数组并打印字节值。
  最后，它将字节数组转换回浮点数并打印结果，展示了数据类型和字节表示之间的往返转换。

复杂度分析

时间复杂度

时间复杂度衡量算法或程序运行时间随输入大小的变化情况。

联合体操作

设置和访问联合体成员：像将值赋给联合体成员（data.f = value）和访问联合体成员（data.i 或 data.bytes）这样的操作都是在恒定时间 O(1) 下执行的。这是因为访问联合体的任何成员都涉及直接内存访问，而无需迭代或复杂的操作。

打印操作

打印值：使用 printf 函数输出值。printf 的时间复杂度取决于格式化和输出操作的复杂性。但是，在此代码的上下文中，每个 printf 语句都以恒定时间 O(1) 执行，因为涉及的操作（打印整数、浮点数和字节）很简单，并且不依赖于数据的大小。

字节操作函数

memcpy 函数：memcpy 函数用于在联合体的 bytes 数组和其他变量之间复制字节。其时间复杂度为O(n)，其中 n 是复制的字节数。在此代码中，memcpy 始终对固定大小（4 字节）进行操作，因此在实践中复杂度可视为 O(1)。

由联合体操作、printf 和 memcpy 函数执行的所有操作都是恒定时间操作，因为所涉及的数据大小是固定的（联合体成员为 4 字节）。因此，代码的总体时间复杂度为 O(1)，这意味着执行时间是恒定的，并且不会随输入大小而扩展，因为操作是在固定大小的数据上执行的。

空间复杂度

空间复杂度衡量程序相对于其输入大小使用的内存量。

联合体存储

DataUnion 联合体包含三个成员（int、float 和 char[4]），但它们共享相同的内存。联合体的大小由其最大成员决定，在本例中为 4 字节（char[4] 数组的大小）。因此，联合体的空间复杂度为O(1)，因为所需的内存是恒定且固定的。

临时变量

printFloatAsInt 和 printIntAsFloat 等函数使用恒定的本地变量内存。这些变量所需的空间不取决于输入的大小，因此它们的空间复杂度为 O(1)。

字节数组

转换函数中使用的字节数组（char byteArray[4]）是固定大小的（4 字节），因此这些数组所需的空间是恒定的 O(1)。

固定的联合体和临时变量决定了程序的空间复杂度。由于没有执行动态内存分配，并且使用的空间不随输入大小而变化，因此代码的总体空间复杂度为O(1)。