08 Bit Manipulation

1. Introduction to Bit Manipulation

1.1 What is Bit Manipulation?

Bit manipulation involves changing individual bits within a byte or a word (a fixed-sized group of bytes). This form of low-level programming allows you to precisely control the data your program uses. Bit manipulation is performed using bitwise operators, which treat their operands as sequences of bits rather than traditional numbers.

1.2 Importance in Embedded Systems

In the realm of embedded systems, bit manipulation is crucial for several reasons:

• Resource Efficiency: Embedded systems often have limited memory and processing power. Bit manipulation allows you to maximize the use of these resources.

• Direct Hardware Access: Much of embedded programming involves interacting directly with hardware. Hardware registers are often manipulated at the bit level for fine-grained control.

• Speed: Bit operations are generally faster than arithmetic operations, which can be vital in time-sensitive applications.

• Data Packing: When dealing with protocols or external sensors, you might need to pack multiple pieces of information into a single data word. Bit manipulation is perfect for this.

• Reduced Power Consumption: Efficient code execution can contribute to lower power consumption, a key concern in battery-powered embedded systems.

---

2. Basic Bitwise Operations

2.1 Bitwise AND (&)

The bitwise AND operation takes two equal-length bit patterns and performs the logical AND operation on each pair of corresponding bits.

uint8_t a = 0b11001100;
uint8_t b = 0b10101010;
uint8_t result = a & b;  // result = 0b10001000

2.2 Bitwise OR (|)

The bitwise OR operation takes two bit patterns and performs the logical OR operation on each pair of corresponding bits.

uint8_t a = 0b11001100;
uint8_t b = 0b10101010;
uint8_t result = a | b;  // result = 0b11101110

2.3 Bitwise XOR (^)

The bitwise XOR operation takes two bit patterns and performs the logical XOR operation on each pair of corresponding bits.

uint8_t a = 0b11001100;
uint8_t b = 0b10101010;
uint8_t result = a ^ b;  // result = 0b01100110

2.4 Bitwise NOT (~)

The bitwise NOT operation takes a single bit pattern and inverts each bit.

uint8_t a = 0b11001100;
uint8_t result = ~a;  // result = 0b00110011

2.5 Left Shift (<<)

The left shift operation takes a bit pattern and shifts it to the left by a specified number of bits, filling in zeros from the right.

uint8_t a = 0b11001100;
uint8_t result = a << 1;  // result = 0b10011000

2.6 Right Shift (>>)

The right shift operation takes a bit pattern and shifts it to the right by a specified number of bits, filling in zeros from the left.

uint8_t a = 0b11001100;
uint8_t result = a >> 1;  // result = 0b01100110

---

3. Compound Bitwise Operations

Compound bitwise operations are more specialized operations often used in embedded systems to manipulate individual bits within a data structure like a byte or a word. Let's look at some of them.

3.1 Bit Clear

Bit clear sets a specific bit to 0. It's generally done using bitwise AND with a negated bitmask.

uint8_t value = 0b11111111;
uint8_t bitMask = 0b00000100;  // We want to clear the 3rd bit
value &= ~bitMask;  // value becomes 0b11111011

3.2 Bit Set

Bit set sets a specific bit to 1. It is generally done using bitwise OR.

uint8_t value = 0b00000000;
uint8_t bitMask = 0b00000100;  // We want to set the 3rd bit
value |= bitMask;  // value becomes 0b00000100

3.3 Bit Toggle

Bit toggle flips the state of a specific bit. It is generally done using bitwise XOR.

uint8_t value = 0b00000100;  // Starting value with 3rd bit set
uint8_t bitMask = 0b00000100;  // We want to toggle the 3rd bit
value ^= bitMask;  // value becomes 0b00000000

---

4. Use Cases

4.1 Register Manipulation

Hardware registers in microcontrollers are often manipulated using bitwise operations. For example, setting or clearing specific bits enables or disables hardware features.

// Setting the 3rd bit to enable a hardware feature
REG |= 0b00000100;

4.2 Flags and Bit Masks

Flags can be efficiently represented and manipulated using bits. Bit masks are used to set, clear, or toggle multiple flags at once.

// Setting multiple flags
uint8_t flags = 0;
flags |= (FLAG_A | FLAG_B);

// Clearing multiple flags
flags &= ~(FLAG_C | FLAG_D);

4.3 Data Packing/Unpacking

Packing multiple smaller data into a single data structure is a common embedded systems trick to save memory.

// Packing two 4-bit numbers into a single byte
uint8_t packed = (num1 << 4) | num2;

4.4 Low-level Communication Protocols

Protocols like SPI, I2C, or custom serial interfaces often require bit-level manipulation for framing data packets.

// Sending a data frame with a start and stop bit
uint8_t frame = (START_BIT << 7) | data | (STOP_BIT << 0);

---

5. Advanced Topics

5.1 Rollover and Rotates

Sometimes you might need to shift bits and rollover the shifted-out bits back into the variable. This is known as rotating bits.

// Rotate left
uint8_t rotate_left(uint8_t value, int shift) {
    return (value << shift) | (value >> (8 - shift));
}

// Rotate right
uint8_t rotate_right(uint8_t value, int shift) {
    return (value >> shift) | (value << (8 - shift));
}

Using the rotate functions:

uint8_t value = 0b00001111;
uint8_t result = rotate_left(value, 2);  // result = 0b00111100
result = rotate_right(value, 2);  // result = 0b11000011

5.2 Counting Bits

Counting the number of set bits can be done with a variety of algorithms, from basic loops to more advanced methods like Brian Kernighan’s Algorithm.

// Brian Kernighan’s Algorithm to count set bits
int count_set_bits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

5.3 Portability Concerns

Bit manipulation can sometimes be non-portable because it can depend on the system architecture like endianness or word size. Always be aware of the target platform's specifics when dealing with bit-level manipulations.

For example, use language features or utility functions to handle endianness conversions to make sure your bit manipulations are portable across different architectures.

---

6. Optimization Techniques

6.1 Compiler Intrinsics for Bit Manipulation

Many modern compilers provide intrinsics or built-in functions optimized for bit manipulation, like __builtin_clz for counting leading zeros.

int leading_zeros = __builtin_clz(0x0F); // Compiler-specific

6.2 Lookup Tables vs. Arithmetic

For some operations, pre-computed lookup tables can be faster than arithmetic operations, especially in tight loops. However, they may consume more memory.

// Lookup table for a nibble
static const uint8_t Lookup[16] = {0, 1, 1, 2, 1, 2, 2, 3, ...};

---

7. Best Practices

7.1 When to Use Bit Manipulation

Bit manipulation is particularly useful for register manipulation, state machines, and protocols. Use it when you need to save memory, or when low-level hardware interaction is necessary.

7.2 Pitfalls and How to Avoid Them

Watch out for endianness, signed integer issues, and overflow errors. Use static code analysis tools to catch these issues early.

7.3 Coding Guidelines for Bit Operations

1. Prefer bit-fields or enums for better readability when working with hardware registers.
2. Use unsigned types for bit manipulation to avoid issues related to sign extension.
3. Always comment your code to make the intent clear when you're doing complex bit manipulations.

---

8. Q&A

1. Question: What are bitwise operators in C?

Answer: Bitwise operators are used to perform operations at the bit level. The primary bitwise operators in C are & (bitwise AND), | (bitwise OR), ^ (bitwise XOR), ~ (bitwise NOT), << (left shift), and >> (right shift).

---

2. Question: How do you set the nth bit of a number x?

Answer: To set the nth bit of a number x, you can use the bitwise OR operator with a value where only the nth bit is set.

x |= (1 << n);

---

3. Question: How do you clear the nth bit of a number x?

Answer: To clear the nth bit, you can use the bitwise AND operator with a value where all bits are set except the nth bit.

x &= ~(1 << n);

---

4. Question: How can you toggle the nth bit of a number x?

Answer: To toggle the nth bit, you can use the bitwise XOR operator with a value where only the nth bit is set.

x ^= (1 << n);

---

5. Question: What does the operation x << y do?

Answer: The operation x << y shifts the bits of x to the left by y positions. It fills the rightmost y bits with zeros. This is equivalent to multiplying x by $2^y$.

---

6. Question: What does the operation x >> y do?

Answer: The operation x >> y shifts the bits of x to the right by y positions. If x is an unsigned type, the leftmost bits will be filled with zeros. If x is a signed type and its most significant bit is 1 (indicating a negative number in two's complement), the leftmost bits will be filled with ones (arithmetic right shift). Otherwise, they will be filled with zeros.

---

7. Question: What is the result of the operation x ^ x for any integer x?

Answer: The result is always 0. XORing any number with itself always yields zero because every bit is the same and thus they cancel out.

---

8. Question: How can you determine if the nth bit of a number x is set?

Answer: You can use the bitwise AND operation. If (x & (1 << n)) is non-zero, then the nth bit is set.

if (x & (1 << n)) {
    // nth bit is set
}

---

9. Question: What is the significance of the ~ operator?

Answer: The ~ operator is a bitwise NOT. It inverts each bit of its operand. If a bit is 0, it becomes 1, and if it's 1, it becomes 0.

---

10. Question: How can you count the number of set bits (1s) in an integer?

Answer: While there are optimized algorithms to do this, a simple method involves iterating over each bit of the number and checking if it's set.

int count_set_bits(int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

---

11. Question: How can you determine if a number is a power of 2 using bitwise operations?

Answer: A number n is a power of 2 if it has only one set bit. A trick is that (n & (n-1)) will be 0 for numbers that are powers of 2.

if (n && !(n & (n - 1))) {
    // n is a power of 2
}

---

12. Question: How would you swap two numbers without using a temporary variable?

Answer: You can use bitwise XOR to swap two numbers:

a = a ^ b;
b = a ^ b;
a = a ^ b;

---

13. Question: What's the quickest way to determine the parity of a number (i.e., if it has an even or odd number of set bits)?

Answer: You can use the XOR operation in a loop:

int parity(int x) {
    int result = 0;
    while (x) {
        result ^= 1;
        x &= (x - 1); // clears the least significant set bit
    }
    return result; // returns 1 if odd number of set bits, 0 otherwise
}

---

14. Question: How can you isolate the least significant set bit of a number?

Answer: You can use the formula x & (-x).

int lsb = x & (-x);

---

15. Question: How would you reverse the individual bits of a byte?

Answer: You can do this using a loop and shifting:

unsigned char reverse_byte(unsigned char x) {
    unsigned char result = 0;
    for (int i = 0; i < 8; i++) {
        result <<= 1;
        result |= (x & 1);
        x >>= 1;
    }
    return result;
}

---

16. Question: How can you rotate the bits of a number to the left?

Answer: You can rotate the bits using the shift operators:

unsigned int rotate_left(unsigned int x, int n) {
    return (x << n) | (x >> (sizeof(x)*8 - n));
}

---

17. Question: What's a bitwise method to divide a number by 2?

Answer: Shifting the bits of a number to the right by one is equivalent to dividing it by 2.

int result = x >> 1;

---

18. Question: How can you compute the absolute value of an integer without branching?

Answer: Here's a trick using the sign bit and bitwise operations:

int mask = x >> (sizeof(int)*8 - 1);
int abs_value = (x + mask) ^ mask;

---

19. Question: How can you add two numbers without using arithmetic operators?

Answer: You can use bitwise operations. The XOR (^) gives the sum without carrying, and the AND (&) followed by a left shift (<<) gives the carry. Repeat until there's no carry.

int add(int a, int b) {
    while (b != 0) {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

---

20. Question: How can you quickly check if the sign bit is set in a number?

Answer: You can right-shift the number by the number of bits in the type minus one and check if the result is 1:

int sign_set = x >> (sizeof(int)*8 - 1);

---

21. Question: Given a system where integers are represented using 16 bits, how would you implement a function that finds the number of bits needed to represent a positive integer?

Answer: The number of bits needed can be found by counting the position of the highest set bit.

int num_bits(int x) {
    int count = 0;
    while (x) {
        count++;
        x >>= 1;
    }
    return count;
}

---

22. Question: How would you determine if two numbers have opposite signs using bit manipulation?

Answer: You can use the XOR operation on the sign bits.

int opposite_signs(int x, int y) {
    return ((x ^ y) < 0);
}

---

23. Question: How can you compute the minimum of two numbers without any comparison operators or branching?

Answer: This is a bit tricky but can be done using the sign bit:

int min(int x, int y) {
    int diff = x - y;
    int sign_bit = (diff >> (sizeof(int)*8 - 1)) & 1;
    return x - sign_bit * diff;
}

---

24. Question: How would you implement a function that counts all set bits in an integer?

Answer: Brian Kernighan’s algorithm can be used:

int count_set_bits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

---

25. Question: Given a number, how would you clear all bits from the most significant bit through i (including i), where i is given?

Answer: Use a mask.

int clear_msb_to_i(int num, int i) {
    int mask = (1 << i) - 1;
    return num & mask;
}

---

26. Question: How would you implement a function that swaps bits at positions i and j?

Answer: Here's a method using bitwise operations:

int swap_bits(int x, int i, int j) {
    int a = (x >> i) & 1;
    int b = (x >> j) & 1;
    if (a ^ b) {
        return x ^ ((1 << i) | (1 << j));
    }
    return x;
}

---

27. Question: If you wanted to set the ith bit of a number to 1, how would you do it?

Answer: Use the OR operation with a mask:

int set_ith_bit(int x, int i) {
    return x | (1 << i);
}

---

28. Question: How can you round a number up to the nearest power of 2?

Answer: This can be achieved using bit manipulation in multiple steps:

unsigned int roundUp(unsigned int v) {
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16; // Assuming 32-bit integer, remove this for 16-bit
    v++;
    return v;
}

---

29. Question: How would you detect if two integers would produce an overflow when added?

Answer: You can check by observing the sign bit:

int will_add_overflow(int x, int y) {
    return ((x > 0) && (y > 0) && (x + y < 0)) ||
           ((x < 0) && (y < 0) && (x + y >= 0));
}

---

30. Question: How can you extract the n least significant bits of a number?

Answer: Use a mask with n bits set:

int extract_bits(int x, int n) {
    return x & ((1 << n) - 1);
}

---

31. Question: Examine the function meant to count the number of set bits in an integer. What's wrong with it?

int count_set_bits(int n) {
    int count = 0;
    while (n > 0) {
        count += (n & 1);
        n >>= 1;
    }
    return count;
}

Answer: This function fails to correctly count set bits for negative numbers because the while loop terminates for negative values of n. For a correct implementation, the condition should simply check for n not being zero, i.e., while (n).

---

32. Question: The function below is supposed to set the ith bit of a number to 0. What's wrong?

int clear_ith_bit(int x, int i) {
    return x & (1 << i);
}

Answer: The mask being applied is actually setting all bits to 0 except the ith bit. To clear only the ith bit, the correct mask would be the complement of (1 << i).

---

33. Question: This code is meant to toggle the ith bit of a number. What's the error?

int toggle_ith_bit(int x, int i) {
    return x ^ ~(1 << i);
}

Answer: The error is in using the ~ operator. The code will not toggle the ith bit but rather perform an unexpected operation. The correct approach is: return x ^ (1 << i);.

---

34. Question: This function should return the least significant set bit of a number. Spot the mistake:

int least_significant_set_bit(int x) {
    return x & (x - 2);
}

Answer: The mistake is in the mask (x - 2). To obtain the least significant set bit, the mask should be (x - 1). Thus, the correct code is: return x & (x - 1);.

---

35. Question: The following function intends to check if an integer is a power of 2. What's the flaw?

int is_power_of_two(int n) {
    return n && (n & (n - 1) == 0);
}

Answer: The error is in the operator precedence. The bitwise AND operation will be evaluated after the comparison due to the lack of parentheses around (n & (n - 1)). The correct check is: return n && ((n & (n - 1)) == 0);.

---

36. Question: Look at this code aiming to swap two numbers without using a temporary variable. What's wrong?

void swap(int a, int b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

Answer: While the logic to swap the numbers using XOR is correct, the changes won't reflect outside the function since C passes parameters by value. For swapping to affect the original values, you'd need to pass pointers to the integers.

---

37. Question: This function claims to clear all bits from i through 0. Spot the error:

int clear_bits_i_through_0(int x, int i) {
    return x & ~((1 << i) - 1);
}

Answer: The function is correct. It's a trick question!

---

38. Question: What's wrong in this function meant to rotate bits to the left?

unsigned int rotate_left(unsigned int value, int shift) {
    return (value << shift) | (value >> (32 - shift));
}

Answer: Assuming a 32-bit integer, the function does not handle cases where the shift value is larger than 31 or negative. It should ideally take the modulus with 32 to handle such cases.

---

39. Question: This function is supposed to extract bits from position i to j. Can you spot the issue?

int extract_bits(int x, int i, int j) {
    return (x >> i) & ~((1 << (j - i + 1)) - 1);
}

Answer: The mask used to clear bits is incorrect. Instead of clearing, it should retain the bits. The correct mask should be: ((1 << (j - i + 1)) - 1).

---

40. Question: Here's a function aiming to set a range of bits from i to j. Find the problem:

int set_bit_range(int x, int i, int j) {
    return x | ((1 << (j - i)) - 1);
}

Answer: The mask does not correctly represent a range of bits from i to j. The correct mask should be shifted to the left by i positions: x | (((1 << (j - i + 1)) - 1) << i).