NOT for inverting bits in Embedded C - Time & Space Complexity

Time Complexity: NOT for inverting bits

O(1)

Understanding Time Complexity

We want to understand how long it takes to invert bits using the NOT operator in embedded C.

How does the time needed change when we invert more bits?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int invert_bits(unsigned int x) {
    return ~x;
}
    

This code uses the NOT operator (~) to flip all bits of the input number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single bitwise NOT operation on the input number.
• How many times: Exactly once, no loops or repeated steps.

How Execution Grows With Input

Explain the growth pattern intuitively.

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

Pattern observation: The operation count stays the same no matter how many bits the input has.

Final Time Complexity

Time Complexity: O(1)

This means the time to invert bits using NOT does not grow with input size; it takes the same time always.

Common Mistake

[X] Wrong: "Inverting bits with NOT takes longer for bigger numbers because there are more bits to flip."

[OK] Correct: The NOT operator works on the whole number at once in hardware, so it does not take more time for bigger inputs.

Interview Connect

Knowing that bitwise NOT runs in constant time helps you understand how low-level operations behave efficiently in embedded systems.

Self-Check

"What if we inverted bits one by one using a loop instead of the NOT operator? How would the time complexity change?"

Practice

1.

What does the ~ operator do in embedded C?

easy

A. It flips every bit of the operand (bitwise NOT).

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

C. It adds one to the operand.

D. It compares two values for equality.

Solution

1. Step 1: Understand the ~ operator

   The ~ operator is the bitwise NOT operator in C, which flips every bit of its operand.

2. Step 2: Compare with other options

   Other options describe different operations: shifting, addition, and comparison, which are not what ~ does.

3. Final Answer:

   It flips every bit of the operand (bitwise NOT). -> Option A

4. Quick Check:

   ~ operator = bitwise NOT [OK]

Hint: Remember ~ flips bits, like turning 0s to 1s and vice versa [OK]

Common Mistakes:

• Confusing ~ with shift operators
• Thinking ~ adds or subtracts
• Mixing ~ with logical NOT (!)

2.

Which of the following is the correct syntax to invert bits of an unsigned integer x in embedded C?

unsigned int x = 5;
unsigned int y = ?;

easy

A. y = x++;

B. y = !x;

C. y = ~x;

D. y = x & ~x;

Solution

1. Step 1: Identify the bit inversion syntax

   To invert bits, use the bitwise NOT operator ~ directly on the variable.

2. Step 2: Check other options for correctness

   y = !x; uses logical NOT, which returns 0 or 1, not bit inversion. y = x++; increments x, not invert bits. y = x & ~x; ANDs x with its inverse, resulting in zero.

3. Final Answer:

   y = ~x; -> Option C

4. Quick Check:

   Bit inversion syntax = y = ~x; [OK]

Hint: Use ~ directly on variable to invert bits [OK]

Common Mistakes:

• Using ! instead of ~
• Using increment operators by mistake
• Combining & with ~ incorrectly

3.

What is the output of the following code snippet?

unsigned char x = 0b00001111;
unsigned char y = ~x;
printf("%u", y);

medium

A. 240

B. 15

C. 0

D. 255

Solution

1. Step 1: Understand the initial value of x

   x is 0b00001111, which is decimal 15.

2. Step 2: Apply bitwise NOT to x

   ~x flips bits: 00001111 becomes 11110000 in 8 bits, which is decimal 240.

3. Final Answer:

   240 -> Option A

4. Quick Check:

   ~15 (8-bit) = 240 [OK]

Hint: Invert bits of 00001111 to get 11110000 = 240 decimal [OK]

Common Mistakes:

• Confusing logical NOT (!) with bitwise NOT (~)
• Forgetting unsigned type size
• Assuming output is 15 or 255

4.

Find the error in the following code that attempts to invert bits of num and print the result:

int num = 5;
int inverted = ~num;
printf("%u", inverted);

medium

A. The variable inverted should be unsigned char.

B. The ~ operator cannot be used on int types.

C. Missing semicolon after variable declaration.

D. Using %u to print a signed int causes incorrect output.

Solution

1. Step 1: Check the type and format specifier

   Variable inverted is signed int, but printed with %u (unsigned). This mismatch can cause wrong output.

2. Step 2: Verify other options

   The ~ operator works on int types. Semicolons are present. Changing to unsigned char is not necessary but can clarify output.

3. Final Answer:

   Using %u to print a signed int causes incorrect output. -> Option D

4. Quick Check:

   Format specifier must match variable type [OK]

Hint: Match printf format (%d for int, %u for unsigned) [OK]

Common Mistakes:

• Using wrong printf format specifier
• Thinking ~ can't be used on int
• Ignoring signed vs unsigned mismatch

5.

You want to invert bits of a 16-bit unsigned integer val but only for the lower 8 bits, leaving the upper 8 bits unchanged. Which code snippet correctly does this?

unsigned short val = 0xABCD;
unsigned short result = ?;

hard

A. result = ~val & 0xFFFF;

B. result = (val & 0xFF00) | (~val & 0x00FF);

C. result = ~val | 0xFF00;

D. result = val ^ 0xFFFF;

Solution

1. Step 1: Understand the requirement

   Invert only the lower 8 bits of val, keep upper 8 bits as is.

2. Step 2: Analyze each option

   result = (val & 0xFF00) | (~val & 0x00FF); keeps upper 8 bits (val & 0xFF00) and inverts lower 8 bits (~val & 0x00FF), then combines them. result = ~val & 0xFFFF; inverts all 16 bits. result = ~val | 0xFF00; incorrectly sets upper bits to 1. result = val ^ 0xFFFF; flips all bits (XOR with 0xFFFF).

3. Final Answer:

   result = (val & 0xFF00) | (~val & 0x00FF); -> Option B

4. Quick Check:

   Mask upper bits, invert lower bits, combine [OK]

Hint: Mask upper bits, invert lower bits, then combine [OK]

Common Mistakes:

• Inverting all bits instead of just lower 8
• Using OR instead of AND for masking
• Forgetting to combine masked parts