Extract Bits In C

More intricate situations arise when extracting multiple consecutive sections to derive a subfield from a data word. This is frequently seen in networking, particularly in data packets where headers hold different fields compacted in a binary format. In this context, a mask proves useful in filtering out unnecessary bits, retaining solely the relevant ones. To create this mask, one sets the specified lower bits to '1' and then performs a bitwise AND operation after shifting the data to the right.

Working with bits in the C programming language extends beyond basic data access and modification; it encompasses efficiency and cross-device compatibility. Byte order, known as endianness, plays a crucial role in how bits are read and understood, particularly in diverse hardware environments. Therefore, a comprehensive grasp of hardware intricacies and meticulous data management are vital for effective programming practices.

Approach-1: Bitwise Operations

Extracting a single-bit

To retrieve a solitary bit from a designated location within an integer, we employ a blend of the bitwise right shift (>>) and bitwise AND (&) operations.

Program:

#include <stdio.h>

// Function to extract a single bit at the given position

int extract_single_bit(int number, int position) {

  // Right Shift the number and mask with 1 to isolate the Bit at the given position

  int extracted_bit = (number >> position) & 1;

  printf("Extracting single bit:\n");

  printf("Number: %d (Binary: %08b), Position: %d\n", number, number, position);

  printf("Shifted Number: %d (Binary: %08b)\n", number >> position, number >> position);

  printf("Extracted Bit: %d\n\n", extracted_bit);

  return extracted_bit;

}

// Function to extract a range of bits (starting from the 'start' position, 'num_bits' long)

int extract_multiple_bits(int number, int start, int num_bits) {

  // Create a mask with the specified number of bits set to 1

  int mask = (1 << num_bits) - 1;

  // Shift the number right and apply the mask to extract the desired bits

  int extracted_bits = (number >> start) & mask;

  printf("Extracting multiple bits:\n");

  printf("Number: %d (Binary: %08b), Start: %d, Number of Bits: %d\n", number, number, start, num_bits);

  printf("Mask: %d (Binary: %08b)\n", mask, mask);

  printf("Shifted Number: %d (Binary: %08b)\n", number >> start, number >> start);

  printf("Extracted Bits: %d (Binary: %0*b)\n\n", extracted_bits, num_bits, extracted_bits);

  return extracted_bits;

}

int main() {

  // Test data

  int number1 = 0b10101100; // Example binary number

  int number2 = 0b11011010; // Another example binary number

  // Extract single bits

  int single_bit_1 = extract_single_bit(number1, 3);

  int single_bit_2 = extract_single_bit(number2, 5);

  // Extract multiple bits

  int multiple_bits_1 = extract_multiple_bits(number1, 2, 4); // Extract 4 bits starting from position 2

  int multiple_bits_2 = extract_multiple_bits(number2, 1, 3); // Extract 3 bits starting from position 1

  // Output results

  printf("Results:\n");

  printf("Single Bit from number1 at position 3: %d\n", single_bit_1);

  printf("Single Bit from number2 at position 5: %d\n", single_bit_2);

  printf("4 Bits from number1 starting at position 2: %d\n", multiple_bits_1);

  printf("3 Bits from number2 starting at position 1: %d\n", multiple_bits_2);

  return 0;

}

Output:

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

Explanation:

The provided C code demonstrates the extraction of single and multiple bits from an integer using bitwise operations. It includes two primary functions: one for extracting a single bit and another for extracting multiple bits, along with logging-like output to show the internal state and results of these operations.

• ✅ Function to Extract a Single Bit The function extractsinglebit(int number, int position) takes two arguments: number (the integer from which a bit is to be extracted) and position (the bit position to extract). The function uses bitwise operations to isolate and return the value of the Bit at the specified position. Right Shift (>>): The input number is right-shifted by position places, moving the target bit to the least significant Bit (LSB) position. This operation effectively discards all bits to the right of the target bit. Bitwise AND (&): The result of the right Shift is then AND with 1 (binary 0001). This operation clears all bits except the LSB, isolating the Bit of interest. After that, the extracted Bit is logged and returned by the function. The logging statements in the function print the original number in both decimal and binary formats, the shifted number, and the extracted Bit. This provides a clear view of the bit manipulation process and the intermediate values.
• ✅ Function to Extract Multiple Bits The function extractmultiplebits(int number, int start, int numbits) extracts a range of bits from the input integer. The arguments are number (the integer to extract bits from), start (the starting bit position), and numbits (the number of bits to extract). Mask Creation: The function creates a mask with numbits consecutive 1s using the expression (1 << numbits) - 1. This mask will later be used to isolate the desired bits from the shifted number. Right Shift (>>): Similar to the single-bit extraction, the function shifts the input number right by start positions. This operation aligns the target bit range with the LSB. Bitwise AND (&): The mask is applied to the shifted number using the AND operation. This step zeros out all bits except those corresponding to the mask, effectively extracting the desired bit range. The function logs the original number, the mask, the shifted number, and the extracted bits in both decimal and binary forms. This helps illustrate how the bitwise operations isolate the specific bits.
• ✅ Main Function and Test Cases The main function sets up two example integers (number 1 and number 2) and tests the extraction functions. It demonstrates extracting a single bit from different positions and extracting multiple bits. The results, including the values of the extracted bits, are printed out, providing an end-to-end example of the bit extraction process.

Complexity Analysis:

Time Complexity

Time complexity quantifies the amount of operations executed by the code in proportion to the input scale, where the input size is directly linked to the bit count of the integer.

Extracting a single-bit

The function extractsinglebit(int number, int position) entails:

The right shift operation (>>): This operation moves the bits of the integer towards the right. The time complexity of a right shift operation is O(1) as it is a fundamental operation executed by the processor in a fixed amount of time, irrespective of the number of bits being shifted.

Performing a bitwise AND operation (&): This operation maintains a time complexity of O(1) by directly evaluating the matching bits between the number and the mask (in this scenario, set as 1).

The total time complexity for retrieving a single bit remains O(1) as the right shift and bitwise AND operations are executed in constant time.

Extracting Multiple Bits

The function extractmultiplebits(int number, int start, int num_bits) is responsible for retrieving multiple bits from an integer.

Mask Creation: The mask gets generated by employing (1 << numbits) - 1. This involves a bit shift and a subtraction operation. The bit shift's complexity is O(1) because it depends on the processor's word size and not on the actual value of numbits.

Right Shift Operation (>>): Comparable to the process of extracting a single bit, this action involves moving the integer by a fixed number of positions, leading to a complexity of O(1).

Performing the bitwise AND Operation (&): Utilizing the mask on the shifted number to extract the specific bits is likewise a constant time (O(1)) operation.

Therefore, the time efficiency for retrieving multiple bits remains O(1) since all actions (bitwise shifts, generating masks, and bitwise AND) are executed in constant time.

Space Complexity

Space complexity pertains to the quantity of memory that the algorithm necessitates in relation to the size of the input.

Extracting a single-bit

The space efficiency for retrieving a single bit remains at O(1) as it involves minimal usage of extra integer variables such as number, position, and extracted_bit. These variables consistently occupy a fixed amount of space, irrespective of the size of the input.

Extracting Multiple Bits

Likewise, the spatial efficiency for retrieving various bits stands at O(1). This process involves several integer variables (such as number, start, numbits, mask, and extractedbits) that each require a fixed amount of memory. The memory footprint of these variables remains consistent regardless of the quantity of bits extracted or the magnitude of the integer input.

Main Function

The primary function initializes several integer variables and is referred to as the Bit extraction function. The memory allocated for these variables and function invocations also remains constant, denoted as O(1). The functions do not introduce substantial new data structures or request memory dynamically, thus preserving a consistent space complexity.

Approach-2: Unions for Type Punning in C

Unions in C represent a unique data structure enabling various data types to occupy a common memory location. Consequently, a union can accommodate diverse data types, albeit only one type at a time. The union's size is dictated by its largest member, allowing access to any member while interpreting memory bytes based on the respective data type.

This characteristic of unions is applicable for type punning, a method that involves accessing or interpreting the same data in various ways using different types. Type punning can be especially advantageous in low-level programming scenarios like systems programming, embedded systems, and tasks involving hardware interfaces, where direct alteration of the fundamental data representation is essential.

How does unions work?

Within a union, all members share a common memory location, causing them to intersect. Modifying one member and then accessing another can alter how the data is perceived, offering insight into the underlying binary representation of the value.

Program:

#include <stdio.h>

#include <string.h>

// Define a union that allows different interpretations of the same memory location

union DataUnion {

  int i;       // Integer representation

  float f;      // Floating-point representation

  char bytes[4];   // Byte array representation (for 4-byte data)

};

// Function to print the bits of a float as an integer

void printFloatAsInt(float value) {

  union DataUnion data;

  data.f = value; // Set the float value

  printf("Float value: %f\n", data.f);

  printf("Interpreted as integer: %d\n", data.i);

  printf("Raw bytes: ");

  for (int j = 0; j < sizeof(data.bytes); j++) {

    printf("%02x ", (unsigned char)data.bytes[j]);

  }

  printf("\n\n");

}

// Function to print the bits of an integer as a float

void printIntAsFloat(int value) {

  union DataUnion data;

  data.i = value; // Set the integer value



  printf("Integer value: %d\n", data.i);

  printf("Interpreted as float: %f\n", data.f);

  printf("Raw bytes: ");

  for (int j = 0; j < sizeof(data.bytes); j++) {

    printf("%02x ", (unsigned char)data.bytes[j]);

  }

  printf("\n\n");

}

// Function to convert a byte array to a float

void convertBytesToFloat(const char* byteArray, float* result) {

  union DataUnion data;

  memcpy(data.bytes, byteArray, sizeof(data.bytes));

  *result = data.f;

}

// Function to convert a float to a byte array

void convertFloatToBytes(float value, char* byteArray) {

  union DataUnion data;

  data.f = value;

  memcpy(byteArray, data.bytes, sizeof(data.bytes));

}

int main() {

  // Example usage of the union for type punning

  float floatValue = 3.14159f;

  int intValue = 1078530016; // Example integer value

  printf("Using union to interpret float as int:\n");

  printFloatAsInt(floatValue);

  printf("Using union to interpret int as float:\n");

  printIntAsFloat(intValue);

  // Example of converting between float and byte array

  char byteArray[4];

  convertFloatToBytes(floatValue, byteArray);

  printf("Byte array from float %f:\n", floatValue);

  for (int i = 0; i < sizeof(byteArray); i++) {

    printf("%02x ", (unsigned char)byteArray[i]);

  }

  printf("\n\n");

  float convertedFloat;

  convertBytesToFloat(byteArray, &convertedFloat);

  printf("Float value obtained from byte array:\n");

  printf("Float value: %f\n", convertedFloat);

  return 0;

}

Output:

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

Explanation:

• ✅ Union Definition and Purpose The union DataUnion is defined with three members: an integer (i), a float (f), and a character array (bytes). All these members occupy the same memory space, which allows different interpretations of the same binary data. The size of the union is determined by its largest member, which in this case is the bytes array of 4 bytes. This setup enables us to view and manipulate the same data through different formats. Function Descriptions Printing a Float as an Integer The printFloatAsInt function demonstrates how a floating-point number is stored in memory and how it can be interpreted as an integer. It sets the float value in the union and prints it. Due to the shared memory space, the float's bit pattern is also interpreted as an integer. This function outputs: The integer representation of the float's bit pattern shows how the bytes are interpreted differently. The raw byte values provide a hexadecimal view of the float's bit pattern. This is useful for understanding how floating-point numbers are represented in binary and how their bit patterns can be viewed as integers. Printing an Integer as a Float The printIntAsFloat function reverses the process by setting an integer value in the union and then interpreting it as a float. This function: Displays the integer value. Shows the float value that results from interpreting the same bit pattern as a float. Prints the raw byte representation of the integer. This function illustrates how an integer's bit pattern can be reinterpreted as a floating-point number, which helps in understanding data encoding and conversions between types.
• ✅ Byte Array Conversion Functions The convertBytesToFloat and convertFloatToBytes functions facilitate the conversion between float values and byte arrays. These functions use memcpy to transfer data between the union's bytes array and other data types: The convertFloatToBytes function copies the bytes representing a float value into a byte array. It is useful for tasks such as serialization or data transmission where raw byte formats are needed. The convertBytesToFloat function copies a byte array into the union and retrieves the corresponding float value. This function is helpful for reconstructing data from a byte stream or interpreting data read from binary files.
• ✅ Main Function The main function serves as a practical demonstration of the previously defined functions: After that, it uses printIntAsFloat to demonstrate how an integer (1078530016) can be viewed as a float, including its raw byte representation. Next, it converts a float to a byte array and prints the byte values. Finally, it converts the byte array back to a float and prints the result, showcasing the round-trip conversion between data types and byte representations.
• ✅ The convertFloatToBytes function copies the bytes representing a float value into a byte array. It is useful for tasks such as serialization or data transmission where raw byte formats are needed.
• ✅ The convertBytesToFloat function copies a byte array into the union and retrieves the corresponding float value. This function is helpful for reconstructing data from a byte stream or interpreting data read from binary files.

Complexity Analysis:

Time Complexity

Time complexity evaluates how the efficiency of an algorithm or program changes as the input size increases.

Union Operations:

Assigning a value to a union member, for example, data.f = value, and accessing a union member like data.i or data.bytes, are executed in constant time, denoted as O(1). This efficiency is achieved because accessing any union member entails direct memory access without the need for iterative or intricate procedures.

Printing Operations:

Printing Data: The printf function serves the purpose of displaying values. The efficiency of printf relies on the intricacy of formatting and output tasks. Nevertheless, within this code's scope, each printf command runs in constant time, denoted as O(1), as the tasks performed (such as printing integers, floats, and bytes) are straightforward and unaffected by data size variations.

Byte Manipulation Functions:

The memcpy function is employed for duplicating bytes between the union's bytes array and different variables. Its computational complexity is O(n), where n represents the quantity of bytes duplicated. In the context of this code, memcpy consistently functions with a constant size (4 bytes), thus making the complexity practically O(1).

All actions carried out by the union manipulation, printf, and memcpy functions are instant operations because they involve fixed-size data (4 bytes for the union members). Thus, the code's time complexity is O(1), signifying that the processing time remains constant and is not influenced by input size, as the tasks are conducted on data of a fixed size.

Space Complexity

Space complexity evaluates the memory consumption of a program in relation to the scale of its inputs.

Union Storage:

The DataUnion union comprises three elements (int, float, and char[4]), yet they all utilize the same memory. The union's size is dictated by its largest element, which in this instance is 4 bytes (the size of the char[4] array). Consequently, the union's space complexity is O(1) as the memory allocation remains consistent and unchanging.

Temporary Variables:

The functions printFloatAsInt and printIntAsFloat have a fixed memory usage for local variables. This memory allocation remains constant regardless of the input size, indicating a space complexity of O(1).

Byte Arrays:

The fixed-size byte array (char byteArray[4]) employed in the conversion functions ensures a constant space requirement of O(1) for these arrays.

The space complexity of the program is mainly influenced by the fixed-size union and temporary variables. As there is no dynamic memory allocation involved and the space utilized remains constant irrespective of the input size, the code's overall space complexity is O(1).