OR for setting bits in Embedded C - Time & Space Complexity

Time Complexity: OR for setting bits

O(1)

Understanding Time Complexity

We want to understand how the time needed to set bits using OR changes as we work with more bits.

How does the number of operations grow when setting bits in a number?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int set_bits(unsigned int num, unsigned int mask) {
    return num | mask;
}
    

This code sets bits in num where mask has bits set, using the OR operation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise OR operation between two numbers.
• How many times: The OR operation is done once per call, affecting all bits simultaneously.

How Execution Grows With Input

The OR operation works on all bits at once, so the time does not increase with more bits in a noticeable way.

Input Size (bits)	Approx. Operations
8	1 operation
16	1 operation
32	1 operation

Pattern observation: The time stays about the same no matter how many bits are involved.

Final Time Complexity

Time Complexity: O(1)

This means the time to set bits using OR does not grow with input size; it stays constant.

Common Mistake

[X] Wrong: "Setting bits with OR takes longer if the number has more bits."

[OK] Correct: The OR operation works on all bits at once inside the processor, so it takes the same time regardless of bit size.

Interview Connect

Knowing that bitwise OR runs in constant time helps you explain efficiency clearly and shows you understand how low-level operations work.

Self-Check

"What if we used a loop to set bits one by one instead of OR? How would the time complexity change?"

Practice

1. What does the OR operation do when used to set bits in a variable in embedded C?

easy

A. It toggles specified bits from 0 to 1 or 1 to 0.

B. It clears specified bits to 0 without changing other bits.

C. It sets specified bits to 1 without changing other bits.

D. It shifts bits to the left by one position.

Solution

1. Step 1: Understand OR operation effect on bits

   The OR operation sets bits to 1 if either bit is 1, so it can set bits without clearing others.

2. Step 2: Apply to setting bits

   Using OR with a mask having 1s in desired positions sets those bits to 1, leaving others unchanged.

3. Final Answer:

   It sets specified bits to 1 without changing other bits. -> Option C

4. Quick Check:

   OR sets bits to 1 without clearing others [OK]

Hint: OR with mask sets bits to 1, leaves others unchanged [OK]

Common Mistakes:

• Confusing OR with AND operation
• Thinking OR clears bits instead of setting
• Assuming OR toggles bits
• Mixing OR with bit shifting

2. Which of the following is the correct syntax to set bits using OR in embedded C?

easy

A. variable |= mask;

B. variable = variable & mask;

C. variable = variable ^ mask;

D. variable &= ~mask;

Solution

1. Step 1: Identify syntax for setting bits with OR

   The operator '|=' is the shorthand for 'variable = variable | mask;', which sets bits.

2. Step 2: Check other options

   variable = variable & mask; uses AND, which clears bits; variable = variable ^ mask; uses XOR, which toggles bits; variable &= ~mask; clears bits using AND with negated mask.

3. Final Answer:

   variable |= mask; -> Option A

4. Quick Check:

   Use '|=' to set bits quickly [OK]

Hint: Use '|=' operator to set bits easily [OK]

Common Mistakes:

• Using '&' instead of '|' to set bits
• Confusing XOR (^) with OR (|)
• Forgetting shorthand '|=' syntax
• Using negation incorrectly

3. What is the value of flags after executing the following code?

unsigned char flags = 0x12;  // binary 00010010
unsigned char mask = 0x05;   // binary 00000101
flags = flags | mask;

medium

A. 0x05 (binary 00000101)

B. 0x17 (binary 00010111)

C. 0x10 (binary 00010000)

D. 0x07 (binary 00000111)

Solution

1. Step 1: Convert values to binary and apply OR

   flags = 00010010, mask = 00000101. OR operation sets bits where either is 1.

2. Step 2: Perform bitwise OR

   00010010 OR 00000101 = 00010111 (binary), which is 0x17 in hex.

3. Final Answer:

   0x17 (binary 00010111) -> Option B

4. Quick Check:

   0x12 | 0x05 = 0x17 [OK]

Hint: OR bits: 1 if either bit is 1 [OK]

Common Mistakes:

• Adding values instead of ORing
• Confusing OR with AND
• Misreading binary values
• Forgetting to convert hex to binary

4. Identify the error in the following code snippet that tries to set bits using OR:

unsigned int reg = 0x0F;
unsigned int mask = 0x30;
reg = reg & mask;

medium

A. Using '&' instead of '|' to set bits

B. Mask value is incorrect

C. Variable types should be 'char' not 'int'

D. Missing semicolon after mask declaration

Solution

1. Step 1: Understand the intended operation

   The code aims to set bits using OR, but uses '&' which clears bits instead.

2. Step 2: Identify correct operator

   To set bits, use '|' operator, so 'reg = reg | mask;' or 'reg |= mask;' is correct.

3. Final Answer:

   Using '&' instead of '|' to set bits -> Option A

4. Quick Check:

   Use '|' to set bits, '&' clears bits [OK]

Hint: Use '|' not '&' to set bits [OK]

Common Mistakes:

• Confusing AND with OR
• Assuming '&' sets bits
• Ignoring operator precedence
• Not testing code output

5. You have a 16-bit register reg initially set to 0x0000. You want to set bits 0, 3, and 15 to 1 without changing other bits. Which code correctly does this?

hard

A. reg = reg ^ ((1 << 0) | (1 << 3) | (1 << 15));

B. reg = reg & ((1 << 0) | (1 << 3) | (1 << 15));

C. reg |= (1 << 1) | (1 << 2) | (1 << 14);

D. reg |= (1 << 0) | (1 << 3) | (1 << 15);

Solution

1. Step 1: Identify bits to set and create mask

   Bits 0, 3, and 15 correspond to (1<<0), (1<<3), and (1<<15). OR them to create mask.

2. Step 2: Use OR assignment to set bits without changing others

   Use 'reg |= mask;' to set bits. reg |= (1 << 0) | (1 << 3) | (1 << 15); matches this.

3. Step 3: Check other options

   reg = reg & ((1 << 0) | (1 << 3) | (1 << 15)); uses AND which clears bits; reg |= (1 << 1) | (1 << 2) | (1 << 14); sets wrong bits; reg = reg ^ ((1 << 0) | (1 << 3) | (1 << 15)); toggles bits which may not be desired.

4. Final Answer:

   reg |= (1 << 0) | (1 << 3) | (1 << 15); -> Option D

5. Quick Check:

   Use OR with mask of bits to set [OK]

Hint: Use '|=' with bit-shifted mask for setting bits [OK]

Common Mistakes:

• Using '&' instead of '|' to set bits
• Setting wrong bit positions
• Using XOR which toggles bits
• Not combining bits into one mask