Bit field structures in Embedded C - Time & Space Complexity

Time Complexity: Bit field structures

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run code with bit field structures changes as the input grows.

Specifically, we ask: how does using bit fields affect the number of steps the program takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Flags {
  unsigned int flag1 : 1;
  unsigned int flag2 : 1;
  unsigned int flag3 : 1;
};

void setFlags(struct Flags *f, int n) {
  for (int i = 0; i < n; i++) {
    f->flag1 = 1;
    f->flag2 = 0;
    f->flag3 = 1;
  }
}
    

This code sets three bit flags repeatedly in a loop that runs n times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Setting three bit fields inside the loop.
• How many times: The loop runs n times, so these three bit assignments happen n times.

How Execution Grows With Input

Each time the loop runs, it does the same three bit assignments.

Input Size (n)	Approx. Operations
10	30 (3 assignments x 10)
100	300 (3 assignments x 100)
1000	3000 (3 assignments x 1000)

Pattern observation: The number of operations grows directly with n, meaning if n doubles, operations double.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the code grows in a straight line as the input size increases.

Common Mistake

[X] Wrong: "Bit field operations are always constant time, so the loop doesn't affect time complexity."

[OK] Correct: While each bit assignment is quick, the loop repeats these assignments n times, so total time grows with n.

Interview Connect

Understanding how loops with bit field operations scale helps you explain performance clearly and shows you grasp how low-level data affects program speed.

Self-Check

"What if we added another nested loop inside that runs m times? How would the time complexity change?"

Practice

1. What is the main purpose of using bit field structures in embedded C?

easy

A. To improve floating-point calculations

B. To create large arrays of integers

C. To store multiple small data values efficiently using specific bits

D. To allocate memory dynamically

Solution

1. Step 1: Understand bit field structures

   Bit field structures allow storing data in a compact form by specifying the number of bits each field uses.

2. Step 2: Identify the main purpose

   This helps save memory by packing multiple small values into fewer bytes, useful for flags or hardware registers.

3. Final Answer:

   To store multiple small data values efficiently using specific bits -> Option C

4. Quick Check:

   Bit fields save memory by using bits = A [OK]

Hint: Bit fields pack small data into bits to save memory [OK]

Common Mistakes:

• Thinking bit fields create large arrays
• Confusing bit fields with floating-point optimization
• Assuming bit fields allocate memory dynamically

2. Which of the following is the correct syntax to declare a bit field of 3 bits named flags inside a struct?

easy

A. unsigned int flags(3);

B. unsigned int flags = 3;

C. unsigned int : flags 3;

D. unsigned int flags : 3;

Solution

1. Step 1: Recall bit field syntax

   Bit fields use a colon after the variable name to specify the number of bits, e.g., flags : 3.

2. Step 2: Check each option

   unsigned int flags : 3; correctly uses unsigned int flags : 3;. Others have invalid syntax.

3. Final Answer:

   unsigned int flags : 3; -> Option D

4. Quick Check:

   Bit field syntax uses colon = D [OK]

Hint: Bit field size follows colon after variable name [OK]

Common Mistakes:

• Using equals sign instead of colon
• Placing size before variable name
• Using parentheses instead of colon

3. Given the struct definition:

struct S {
  unsigned int a : 2;
  unsigned int b : 3;
  unsigned int c : 3;
};

struct S s = {3, 5, 7};
printf("%u %u %u", s.a, s.b, s.c);

What is the output?

medium

A. 3 5 3

B. 3 5 7

C. 3 1 7

D. 3 5 0

Solution

1. Step 1: Understand bit field sizes and value limits

   Field a has 2 bits (max 3), b has 3 bits (max 7), c has 3 bits (max 7).

2. Step 2: Check assigned values and truncation

   Values assigned: a=3 (fits 2 bits), b=5 (fits 3 bits), c=7 (fits 3 bits). However, the value 7 assigned to c (3 bits) will be truncated if it exceeds the max value. Since 3 bits can hold max 7, 7 fits exactly, so no truncation. But the initializer list {3,5,7} assigns 7 to c, which is 3 bits wide. However, in practice, some compilers truncate values exceeding the bit field size modulo 2^n. Since 7 fits 3 bits, it should print 7. But the question's options suggest otherwise.

3. Step 3: Re-examine the options

   3 5 3 is "3 5 3", which suggests truncation of 7 to 3, which is incorrect. 3 5 7 is "3 5 7", which matches the expected output.

4. Final Answer:

   3 5 7 -> Option B

5. Quick Check:

   Bit fields store values truncated to their bit size; 7 fits 3 bits = 3 5 7 [OK]

Hint: Check max value for bits; values truncate if too big [OK]

Common Mistakes:

• Assuming 7 truncates to 3
• Ignoring bit size limits
• Confusing decimal and binary values

4. Identify the error in this bit field struct declaration:

struct Flags {
  unsigned int flag1 : 1;
  int flag2 : 2;
  unsigned flag3 : 3;
};

medium

A. No error; this is valid syntax

B. Missing bit size for flag3

C. Using signed int for bit field is not allowed

D. Mixing signed and unsigned bit fields causes error

Solution

1. Step 1: Check bit field type rules

   Bit fields can be signed or unsigned integers. Using int or unsigned int is allowed.

2. Step 2: Verify bit size for each field

   All fields specify bit sizes: flag1:1, flag2:2, flag3:3. The type unsigned is shorthand for unsigned int.

3. Final Answer:

   No error; this is valid syntax -> Option A

4. Quick Check:

   Signed and unsigned bit fields allowed = C [OK]

Hint: Signed or unsigned int bit fields both allowed [OK]

Common Mistakes:

• Assuming signed bit fields are invalid
• Thinking unsigned must be 'unsigned int'
• Missing bit size causes error, but here all sizes present

5. You want to store the status of 10 different flags (each 1 bit) and a 6-bit error code in a struct using bit fields. Which struct layout uses the least memory on a 32-bit system?

hard

A. struct { unsigned int flags : 10; unsigned int error : 6; };

B. struct { unsigned int flag1 : 1; unsigned int flag2 : 1; unsigned int flag3 : 1; unsigned int flag4 : 1; unsigned int flag5 : 1; unsigned int flag6 : 1; unsigned int flag7 : 1; unsigned int flag8 : 1; unsigned int flag9 : 1; unsigned int flag10 : 1; unsigned int error : 6; };

C. struct { unsigned char flags : 10; unsigned char error : 6; };

D. struct { unsigned short flags : 10; unsigned short error : 6; };

Solution

1. Step 1: Understand bit field packing

   Bit fields are packed into the base type size. Using one unsigned int for all bits packs them tightly.

2. Step 2: Compare options

   struct { unsigned int flags : 10; unsigned int error : 6; }; packs all 16 bits (10 flags + 6 error) into one unsigned int (32 bits). struct { unsigned int flag1 : 1; unsigned int flag2 : 1; unsigned int flag3 : 1; unsigned int flag4 : 1; unsigned int flag5 : 1; unsigned int flag6 : 1; unsigned int flag7 : 1; unsigned int flag8 : 1; unsigned int flag9 : 1; unsigned int flag10 : 1; unsigned int error : 6; }; declares each flag separately, but still packed into unsigned int, so similar size but more verbose. struct { unsigned char flags : 10; unsigned char error : 6; }; uses unsigned char (8 bits), but 10 bits can't fit in 8 bits, so likely uses more space due to alignment. struct { unsigned short flags : 10; unsigned short error : 6; }; uses unsigned short (16 bits), which fits 16 bits exactly, but alignment may cause padding.

3. Final Answer:

   struct { unsigned int flags : 10; unsigned int error : 6; }; -> Option A

4. Quick Check:

   Pack all bits in one unsigned int for minimal size = B [OK]

Hint: Group bits in one unsigned int to minimize memory [OK]

Common Mistakes:

• Using multiple small types causing padding
• Assuming unsigned char can hold 10 bits
• Declaring each flag separately wastes space