The Embedded New Testament

The "Holy Bible" for embedded engineers

Project maintained by theEmbeddedGeorge Hosted on GitHub Pages — Theme by mattgraham

Bit Manipulation for Embedded Systems

Essential bit operations and manipulation techniques for embedded C programming

📋 Table of Contents

🎯 Overview

Concept: Bits are a contract with hardware and protocols

Bit operations must match datasheet-defined fields exactly; correctness and portability depend on using widths, masks, and shifts that are well-defined in C.

Why it matters in embedded

Minimal example: safe field update

#define REG (*(volatile uint32_t*)0x40000000u)
#define MODE_Pos  4u
#define MODE_Msk  (0x7u << MODE_Pos) // 3-bit field

static inline void reg_set_mode(uint32_t mode) {
  mode &= 0x7u;                // clamp
  uint32_t v = REG;
  v = (v & ~MODE_Msk) | (mode << MODE_Pos);
  REG = v;
}

Try it

  1. Implement get_mode() and verify round-trip for all values 0..7.
  2. Pack a struct into a uint32_t payload; send over UART; unpack and verify.

Takeaways

🧪 Guided Labs

1) Register field round-trip

2) Protocol pack/unpack

typedef struct { uint8_t type; uint16_t value; } msg_t;
uint32_t pack(const msg_t* m){ return ((uint32_t)m->type<<24)|((uint32_t)m->value<<8); }
void unpack(uint32_t w, msg_t* m){ m->type=(w>>24)&0xFF; m->value=(w>>8)&0xFFFF; }

✅ Check Yourself

🔗 Cross-links

Bit manipulation is crucial in embedded systems for:

Key Concepts

🤔 What is Bit Manipulation?

Bit manipulation is the process of working with individual bits within binary data. It involves operations that directly manipulate the binary representation of data at the bit level, rather than working with larger data units like bytes or words.

Core Concepts

Binary Representation:

Bit-Level Operations:

Memory Efficiency:

Binary Number System

Positional Notation:

Binary Number: 10110101
Bit Position:  76543210
Value:        128+32+16+4+1 = 181

Bit Position 7: 1 × 2^7 = 128
Bit Position 6: 0 × 2^6 = 0
Bit Position 5: 1 × 2^5 = 32
Bit Position 4: 1 × 2^4 = 16
Bit Position 3: 0 × 2^3 = 0
Bit Position 2: 1 × 2^2 = 4
Bit Position 1: 0 × 2^1 = 0
Bit Position 0: 1 × 2^0 = 1

Common Bit Patterns:

Power of 2:    1, 2, 4, 8, 16, 32, 64, 128
Binary:        00000001, 00000010, 00000100, 00001000, etc.

All bits set:  11111111 (255 for 8-bit)
All bits clear: 00000000 (0)

🎯 Why is Bit Manipulation Important?

Embedded System Requirements

Hardware Interaction:

Memory Constraints:

Performance Requirements:

Real-world Applications

Hardware Register Control:

// GPIO control
volatile uint32_t* const GPIO_ODR = (uint32_t*)0x40020014;
*GPIO_ODR |= (1 << 5);   // Set bit 5 (turn on LED)
*GPIO_ODR &= ~(1 << 5);  // Clear bit 5 (turn off LED)

Flag Management:

// Status flags
uint8_t status_flags = 0;
#define FLAG_ERROR     (1 << 0)  // Bit 0
#define FLAG_BUSY      (1 << 1)  // Bit 1
#define FLAG_COMPLETE  (1 << 2)  // Bit 2

// Set flags
status_flags |= FLAG_BUSY;
status_flags |= FLAG_ERROR;

// Check flags
if (status_flags & FLAG_ERROR) {
    // Handle error
}

// Clear flags
status_flags &= ~FLAG_BUSY;

Data Packing:

// Pack multiple values into single variable
uint32_t packed_data = 0;
uint8_t temperature = 25;    // 0-255 range
uint8_t humidity = 60;       // 0-255 range
uint16_t pressure = 1013;    // 0-65535 range

// Pack data
packed_data = (pressure << 16) | (humidity << 8) | temperature;

// Unpack data
temperature = packed_data & 0xFF;
humidity = (packed_data >> 8) & 0xFF;
pressure = (packed_data >> 16) & 0xFFFF;

When Bit Manipulation Matters

High Impact Scenarios:

Low Impact Scenarios:

🧠 Bit Manipulation Concepts

Bit-Level Thinking

Individual Bit Operations:

Bit Patterns:

Bit Position Conventions:

Memory Layout

Byte Organization:

8-bit byte:  [7][6][5][4][3][2][1][0]
16-bit word: [15][14][13][12][11][10][9][8][7][6][5][4][3][2][1][0]
32-bit dword: [31][30]...[2][1][0]

Endianness Considerations:

Performance Characteristics

Bit Operation Speed:

Optimization Opportunities:

🔧 Bitwise Operators

What are Bitwise Operators?

Bitwise operators perform operations on individual bits of their operands. They work at the binary level, comparing or manipulating bits position by position.

Operator Categories

Logical Operators:

Shift Operators:

Basic Operators

AND (&) Operator

// Bitwise AND - result bit is 1 only if both operands are 1
uint8_t a = 0b10101010;  // 170
uint8_t b = 0b11001100;  // 204
uint8_t result = a & b;   // 0b10001000 = 136

// Common uses
uint8_t mask_lower_nibble = 0x0F;  // 0b00001111
uint8_t value = 0xAB;              // 0b10101011
uint8_t lower_nibble = value & mask_lower_nibble;  // 0x0B

AND Applications:

OR (|) Operator

// Bitwise OR - result bit is 1 if either operand is 1
uint8_t a = 0b10101010;  // 170
uint8_t b = 0b11001100;  // 204
uint8_t result = a | b;   // 0b11101110 = 238

// Common uses
uint8_t set_bit_3 = 0x08;  // 0b00001000
uint8_t value = 0x01;      // 0b00000001
uint8_t result = value | set_bit_3;  // 0b00001001

OR Applications:

XOR (^) Operator

// Bitwise XOR - result bit is 1 if operands are different
uint8_t a = 0b10101010;  // 170
uint8_t b = 0b11001100;  // 204
uint8_t result = a ^ b;   // 0b01100110 = 102

// Common uses
uint8_t toggle_bit_2 = 0x04;  // 0b00000100
uint8_t value = 0x01;         // 0b00000001
uint8_t result = value ^ toggle_bit_2;  // 0b00000101

XOR Applications:

NOT (~) Operator

// Bitwise NOT - inverts all bits
uint8_t a = 0b10101010;  // 170
uint8_t result = ~a;      // 0b01010101 = 85

// Common uses
uint8_t mask = 0x0F;      // 0b00001111
uint8_t inverted_mask = ~mask;  // 0b11110000

NOT Applications:

Shift Operators

Left Shift («)

// Left shift - moves bits left, fills with zeros
uint8_t value = 0b00000001;  // 1
uint8_t result = value << 3;  // 0b00001000 = 8

// Common uses
uint8_t create_mask = 1 << 5;  // 0b00100000 (bit 5)
uint32_t multiply_by_8 = value << 3;  // Multiply by 8

Left Shift Applications:

Right Shift (»)

// Right shift - moves bits right, fills with zeros
uint8_t value = 0b10001000;  // 136
uint8_t result = value >> 3;  // 0b00010001 = 17

// Common uses
uint8_t extract_upper_nibble = value >> 4;  // Get upper 4 bits
uint32_t divide_by_8 = value >> 3;  // Divide by 8

Right Shift Applications:

📊 Bit Fields

What are Bit Fields?

Bit fields are named bit positions within structures that allow you to access individual bits or groups of bits by name rather than by position.

Bit Field Concepts

Named Access:

Memory Efficiency:

Hardware Mapping:

Bit Field Implementation

Basic Bit Fields

// Simple bit field structure
typedef struct {
    uint8_t error : 1;      // 1 bit for error flag
    uint8_t busy : 1;       // 1 bit for busy flag
    uint8_t complete : 1;   // 1 bit for complete flag
    uint8_t reserved : 5;   // 5 bits reserved
} status_flags_t;

// Usage
status_flags_t flags = {0};
flags.error = 1;        // Set error flag
flags.busy = 1;         // Set busy flag

if (flags.complete) {   // Check complete flag
    // Handle completion
}

Hardware Register Mapping

// GPIO configuration register
typedef struct {
    uint32_t mode : 2;      // GPIO mode (00=Input, 01=Output, 10=Alternate, 11=Analog)
    uint32_t pull_up : 1;   // Pull-up resistor
    uint32_t pull_down : 1; // Pull-down resistor
    uint32_t speed : 2;     // Output speed
    uint32_t reserved : 26; // Reserved bits
} gpio_config_t;

// Usage
gpio_config_t config = {0};
config.mode = 1;        // Output mode
config.pull_up = 1;     // Enable pull-up
config.speed = 2;       // High speed

Data Packing

// Pack multiple values into single variable
typedef struct {
    uint32_t temperature : 8;   // 8 bits for temperature (0-255)
    uint32_t humidity : 8;      // 8 bits for humidity (0-255)
    uint32_t pressure : 16;     // 16 bits for pressure (0-65535)
} sensor_data_t;

// Usage
sensor_data_t data = {0};
data.temperature = 25;   // Set temperature
data.humidity = 60;      // Set humidity
data.pressure = 1013;    // Set pressure

🎭 Bit Masks

What are Bit Masks?

Bit masks are patterns of bits used to select, modify, or test specific bits within a larger value. They provide a systematic way to work with individual bits or groups of bits.

Mask Concepts

Selection Patterns:

Mask Operations:

Mask Implementation

Single Bit Masks

// Define single bit masks
#define BIT_0  (1 << 0)   // 0b00000001
#define BIT_1  (1 << 1)   // 0b00000010
#define BIT_2  (1 << 2)   // 0b00000100
#define BIT_3  (1 << 3)   // 0b00001000
#define BIT_4  (1 << 4)   // 0b00010000
#define BIT_5  (1 << 5)   // 0b00100000
#define BIT_6  (1 << 6)   // 0b01000000
#define BIT_7  (1 << 7)   // 0b10000000

// Usage
uint8_t value = 0x42;    // 0b01000010
uint8_t bit_1 = value & BIT_1;  // Check if bit 1 is set
value |= BIT_3;          // Set bit 3
value &= ~BIT_5;         // Clear bit 5
value ^= BIT_2;          // Toggle bit 2

Multi-bit Masks

// Define multi-bit masks
#define NIBBLE_LOWER  0x0F    // 0b00001111 (lower 4 bits)
#define NIBBLE_UPPER  0xF0    // 0b11110000 (upper 4 bits)
#define BYTE_LOWER    0xFF    // 0b11111111 (lower 8 bits)
#define BYTE_UPPER    0xFF00  // 0b1111111100000000 (upper 8 bits)

// Usage
uint16_t value = 0x1234;
uint8_t lower_byte = value & BYTE_LOWER;   // 0x34
uint8_t upper_byte = (value & BYTE_UPPER) >> 8;  // 0x12

Range Masks

// Create masks for specific bit ranges
#define MASK_3_BITS(n)    ((1 << n) - 1)  // n consecutive bits starting from 0
#define MASK_RANGE(start, end) (((1 << (end - start + 1)) - 1) << start)

// Usage
#define MASK_BITS_2_4  MASK_RANGE(2, 4)   // 0b00011100
#define MASK_BITS_0_2  MASK_3_BITS(3)     // 0b00000111

uint8_t value = 0x5A;    // 0b01011010
uint8_t bits_2_4 = (value & MASK_BITS_2_4) >> 2;  // Extract bits 2-4

🔄 Bit Shifting

What is Bit Shifting?

Bit shifting moves bits left or right within a value, effectively multiplying or dividing by powers of 2. It’s a fundamental operation for bit manipulation and arithmetic optimization.

Shift Concepts

Direction:

Applications:

Shift Implementation

Arithmetic Operations

// Fast multiplication and division by powers of 2
uint32_t value = 10;
uint32_t multiplied = value << 2;   // 10 * 4 = 40
uint32_t divided = value >> 1;      // 10 / 2 = 5

// Power of 2 calculations
uint32_t power_of_2 = 1 << n;       // 2^n
uint32_t mask_for_n_bits = (1 << n) - 1;  // n consecutive 1s

Field Operations

// Extract and insert bit fields
uint32_t packed_value = 0x12345678;

// Extract 8-bit field starting at bit 8
uint8_t field = (packed_value >> 8) & 0xFF;

// Insert 8-bit value at bit 8
uint32_t new_value = (packed_value & ~(0xFF << 8)) | (field << 8);

Bit Position Operations

// Set bit at position n
uint32_t set_bit(uint32_t value, uint8_t position) {
    return value | (1 << position);
}

// Clear bit at position n
uint32_t clear_bit(uint32_t value, uint8_t position) {
    return value & ~(1 << position);
}

// Toggle bit at position n
uint32_t toggle_bit(uint32_t value, uint8_t position) {
    return value ^ (1 << position);
}

// Test bit at position n
bool test_bit(uint32_t value, uint8_t position) {
    return (value & (1 << position)) != 0;
}

🔧 Hardware Register Operations

What are Hardware Register Operations?

Hardware register operations involve manipulating individual bits in hardware registers to control device behavior, read status information, or configure hardware peripherals.

Register Operation Concepts

Memory-Mapped Registers:

Bit-Level Control:

Hardware Register Implementation

GPIO Control

// GPIO register definitions
volatile uint32_t* const GPIOA_ODR = (uint32_t*)0x40020014;
volatile uint32_t* const GPIOA_IDR = (uint32_t*)0x40020010;
volatile uint32_t* const GPIOA_CRL = (uint32_t*)0x40020000;

// GPIO control functions
void gpio_set_pin(uint8_t pin) {
    *GPIOA_ODR |= (1 << pin);
}

void gpio_clear_pin(uint8_t pin) {
    *GPIOA_ODR &= ~(1 << pin);
}

void gpio_toggle_pin(uint8_t pin) {
    *GPIOA_ODR ^= (1 << pin);
}

bool gpio_read_pin(uint8_t pin) {
    return (*GPIOA_IDR & (1 << pin)) != 0;
}

UART Configuration

// UART register definitions
volatile uint32_t* const UART_CR1 = (uint32_t*)0x40011000;
volatile uint32_t* const UART_CR2 = (uint32_t*)0x40011004;
volatile uint32_t* const UART_SR = (uint32_t*)0x40011000;

// UART control bits
#define UART_ENABLE      (1 << 13)
#define UART_TX_ENABLE   (1 << 3)
#define UART_RX_ENABLE   (1 << 2)
#define UART_TX_READY    (1 << 7)
#define UART_RX_READY    (1 << 5)

// UART configuration
void uart_enable(void) {
    *UART_CR1 |= UART_ENABLE | UART_TX_ENABLE | UART_RX_ENABLE;
}

void uart_disable(void) {
    *UART_CR1 &= ~(UART_ENABLE | UART_TX_ENABLE | UART_RX_ENABLE);
}

bool uart_tx_ready(void) {
    return (*UART_SR & UART_TX_READY) != 0;
}

bool uart_rx_ready(void) {
    return (*UART_SR & UART_RX_READY) != 0;
}

🎯 Common Bit Tricks

What are Bit Tricks?

Bit tricks are clever techniques that use bit manipulation to solve problems efficiently. They often provide faster or more memory-efficient solutions than traditional approaches.

Essential Bit Tricks

Counting Set Bits

// Count number of 1 bits in a value
uint32_t count_set_bits(uint32_t value) {
    uint32_t count = 0;
    while (value) {
        count += value & 1;
        value >>= 1;
    }
    return count;
}

// Fast method using lookup table
uint32_t count_set_bits_fast(uint32_t value) {
    static const uint8_t lookup[256] = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        // ... (complete lookup table)
    };
    
    return lookup[value & 0xFF] + 
           lookup[(value >> 8) & 0xFF] + 
           lookup[(value >> 16) & 0xFF] + 
           lookup[(value >> 24) & 0xFF];
}

Finding Lowest Set Bit

// Find position of lowest set bit
int find_lowest_set_bit(uint32_t value) {
    if (value == 0) return -1;
    return __builtin_ctz(value);  // Count trailing zeros
}

// Alternative method
int find_lowest_set_bit_alt(uint32_t value) {
    if (value == 0) return -1;
    return value & -value;  // Isolates lowest set bit
}

Power of 2 Check

// Check if value is power of 2
bool is_power_of_2(uint32_t value) {
    return value != 0 && (value & (value - 1)) == 0;
}

// Get next power of 2
uint32_t next_power_of_2(uint32_t value) {
    value--;
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    return value + 1;
}

Bit Reversal

// Reverse bits in a byte
uint8_t reverse_bits(uint8_t value) {
    value = ((value & 0x55) << 1) | ((value & 0xAA) >> 1);
    value = ((value & 0x33) << 2) | ((value & 0xCC) >> 2);
    value = ((value & 0x0F) << 4) | ((value & 0xF0) >> 4);
    return value;
}

⚡ Performance Considerations

What Affects Bit Operation Performance?

Bit operation performance depends on several factors including hardware support, compiler optimizations, and operation complexity.

Performance Factors

Hardware Support:

Compiler Optimizations:

Operation Complexity:

Performance Optimization

Use Built-in Functions

// Use compiler built-ins when available
uint32_t count_bits = __builtin_popcount(value);
uint32_t leading_zeros = __builtin_clz(value);
uint32_t trailing_zeros = __builtin_ctz(value);
uint32_t bit_reverse = __builtin_bitreverse32(value);

Optimize Common Patterns

// Optimize bit field operations
#define SET_BIT(reg, bit)    ((reg) |= (1 << (bit)))
#define CLEAR_BIT(reg, bit)  ((reg) &= ~(1 << (bit)))
#define TOGGLE_BIT(reg, bit) ((reg) ^= (1 << (bit)))
#define READ_BIT(reg, bit)   (((reg) >> (bit)) & 1)

// Use lookup tables for complex operations
static const uint8_t bit_count_table[256] = {
    // Pre-computed bit counts for all byte values
};

Memory Access Optimization

// Minimize memory accesses
uint32_t read_modify_write(uint32_t* reg, uint32_t mask, uint32_t value) {
    uint32_t current = *reg;
    current = (current & ~mask) | (value & mask);
    *reg = current;
    return current;
}

🔧 Implementation

Complete Bit Manipulation Example

#include <stdint.h>
#include <stdbool.h>

// Hardware register definitions
#define GPIOA_BASE    0x40020000
#define GPIOA_ODR     (GPIOA_BASE + 0x14)
#define GPIOA_IDR     (GPIOA_BASE + 0x10)
#define GPIOA_CRL     (GPIOA_BASE + 0x00)

// GPIO register pointers
volatile uint32_t* const gpio_odr = (uint32_t*)GPIOA_ODR;
volatile uint32_t* const gpio_idr = (uint32_t*)GPIOA_IDR;
volatile uint32_t* const gpio_crl = (uint32_t*)GPIOA_CRL;

// Bit manipulation macros
#define SET_BIT(reg, bit)    ((reg) |= (1 << (bit)))
#define CLEAR_BIT(reg, bit)  ((reg) &= ~(1 << (bit)))
#define TOGGLE_BIT(reg, bit) ((reg) ^= (1 << (bit)))
#define READ_BIT(reg, bit)   (((reg) >> (bit)) & 1)

// Status flags using bit fields
typedef struct {
    uint8_t error : 1;
    uint8_t busy : 1;
    uint8_t complete : 1;
    uint8_t timeout : 1;
    uint8_t reserved : 4;
} status_flags_t;

// GPIO control functions
void gpio_set_pin(uint8_t pin) {
    SET_BIT(*gpio_odr, pin);
}

void gpio_clear_pin(uint8_t pin) {
    CLEAR_BIT(*gpio_odr, pin);
}

void gpio_toggle_pin(uint8_t pin) {
    TOGGLE_BIT(*gpio_odr, pin);
}

bool gpio_read_pin(uint8_t pin) {
    return READ_BIT(*gpio_idr, pin);
}

// Bit counting functions
uint32_t count_set_bits(uint32_t value) {
    uint32_t count = 0;
    while (value) {
        count += value & 1;
        value >>= 1;
    }
    return count;
}

bool is_power_of_2(uint32_t value) {
    return value != 0 && (value & (value - 1)) == 0;
}

// Main function
int main(void) {
    status_flags_t flags = {0};
    
    // Set status flags
    flags.error = 1;
    flags.busy = 1;
    
    // GPIO operations
    gpio_set_pin(5);      // Turn on LED
    gpio_clear_pin(6);    // Turn off LED
    
    // Check GPIO state
    if (gpio_read_pin(0)) {
        // Button pressed
        gpio_toggle_pin(5);  // Toggle LED
    }
    
    // Bit counting example
    uint32_t test_value = 0x12345678;
    uint32_t bit_count = count_set_bits(test_value);
    
    // Power of 2 check
    if (is_power_of_2(64)) {
        // 64 is a power of 2
    }
    
    return 0;
}

⚠️ Common Pitfalls

1. Sign Extension Issues

Problem: Right shifting signed values can cause sign extension Solution: Use unsigned types for bit operations

// ❌ Bad: Sign extension with signed types
int32_t value = -1;
int32_t shifted = value >> 1;  // May not work as expected

// ✅ Good: Use unsigned types
uint32_t value = 0xFFFFFFFF;
uint32_t shifted = value >> 1;  // Works correctly

2. Undefined Behavior with Shifts

Problem: Shifting by negative amounts or beyond bit width Solution: Validate shift amounts

// ❌ Bad: Undefined behavior
uint32_t value = 1;
uint32_t result = value << 32;  // Undefined behavior

// ✅ Good: Validate shift amount
uint32_t safe_shift(uint32_t value, uint8_t shift) {
    if (shift >= 32) return 0;
    return value << shift;
}

3. Bit Field Portability

Problem: Bit field behavior varies between compilers Solution: Use explicit bit manipulation instead

// ❌ Bad: Non-portable bit fields
typedef struct {
    uint8_t field1 : 3;
    uint8_t field2 : 5;
} non_portable_t;

// ✅ Good: Explicit bit manipulation
#define FIELD1_MASK  0x07
#define FIELD2_MASK  0xF8
#define FIELD1_SHIFT 0
#define FIELD2_SHIFT 3

4. Endianness Issues

Problem: Bit operations may behave differently on different architectures Solution: Use portable bit manipulation

// ❌ Bad: Endianness-dependent code
uint32_t value = 0x12345678;
uint8_t byte = *(uint8_t*)&value;  // Depends on endianness

// ✅ Good: Portable bit extraction
uint8_t byte = (value >> 0) & 0xFF;  // Always gets least significant byte

✅ Best Practices

1. Use Appropriate Types

2. Validate Operations

3. Document Bit Layouts

4. Optimize for Performance

5. Ensure Portability

🎯 Interview Questions

Basic Questions

  1. What are the basic bitwise operators in C?
    • AND (&), OR ( ), XOR (^), NOT (~)
    • Left shift («), Right shift (»)
    • Each operator has specific use cases and behavior
  2. How would you set, clear, and toggle a specific bit?
    • Set: value = (1 « bit_position)
    • Clear: value &= ~(1 « bit_position)
    • Toggle: value ^= (1 « bit_position)
  3. What is the difference between logical and arithmetic shift?
    • Logical shift: Always fills with zeros
    • Arithmetic shift: Right shift may fill with sign bit
    • C standard doesn’t specify behavior for negative values

Advanced Questions

  1. How would you count the number of set bits in a value?
    • Loop method: Check each bit individually
    • Lookup table: Pre-computed bit counts
    • Built-in functions: __builtin_popcount()
    • Brian Kernighan’s algorithm: value &= (value - 1)
  2. How would you check if a number is a power of 2?
    • Use: (value != 0) && ((value & (value - 1)) == 0)
    • Power of 2 has exactly one set bit
    • Subtracting 1 clears the lowest set bit
  3. How would you reverse the bits in a value?
    • Byte reversal: Use lookup table or bit manipulation
    • Word reversal: Use built-in functions or divide-and-conquer
    • Consider endianness and data size

Implementation Questions

  1. Write a function to find the lowest set bit
  2. Implement a function to check if two numbers have opposite signs
  3. Write code to swap two variables without using a temporary variable
  4. Design a function to round up to the next power of 2

📚 Additional Resources

Books

Online Resources

Tools

Standards

Next Steps: Explore Structure Alignment to understand memory layout optimization, or dive into Inline Functions and Macros for performance optimization techniques.