Bitwise NOT in C - Time & Space Complexity

Time Complexity: Bitwise NOT

O(n)

Understanding Time Complexity

Let's see how fast the bitwise NOT operation runs in a program.

We want to know how the time it takes changes when we use it on different input sizes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

unsigned int array_not(unsigned int arr[], int n) {
    unsigned int result = 0;
    for (int i = 0; i < n; i++) {
        result += ~arr[i];
    }
    return result;
}
    

This code flips all bits of each number in an array and sums the results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise NOT (~) applied to each array element.
• How many times: Once per element, so n times for an array of size n.

How Execution Grows With Input

Each element in the array gets its bits flipped once, so the work grows as the array grows.

Input Size (n)	Approx. Operations
10	10 bitwise NOT operations
100	100 bitwise NOT operations
1000	1000 bitwise NOT operations

Pattern observation: The number of operations grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the task grows in a straight line as the input size grows.

Common Mistake

[X] Wrong: "Bitwise NOT is slow because it changes every bit individually."

[OK] Correct: Bitwise NOT is a single fast operation done by the processor, so it takes constant time per element.

Interview Connect

Understanding how simple bitwise operations scale helps you explain efficiency clearly in interviews.

Self-Check

"What if we applied bitwise NOT inside a nested loop over the array? How would the time complexity change?"

Practice

1. What does the bitwise NOT operator ~ do to an integer in C?

easy

A. It adds 1 to the integer.

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

C. It sets all bits to zero.

D. It flips every bit of the integer, changing 0s to 1s and 1s to 0s.

Solution

1. Step 1: Understand the bitwise NOT operator

   The bitwise NOT operator ~ in C flips every bit of the integer. This means all 0 bits become 1, and all 1 bits become 0.

2. Step 2: Compare with other bitwise operations

   Unlike shifting or adding, ~ only toggles bits without changing their positions or values numerically.

3. Final Answer:

   It flips every bit of the integer, changing 0s to 1s and 1s to 0s. -> Option D

4. Quick Check:

   Bitwise NOT = flip bits [OK]

Hint: Remember: ~ flips bits, not shifts or adds [OK]

Common Mistakes:

• Confusing ~ with bit shift operators << or >>
• Thinking ~ adds or subtracts from the number
• Assuming ~ sets bits to zero instead of flipping

2. Which of the following is the correct syntax to apply bitwise NOT to an integer variable x in C?

easy

A. int y = ~x;

B. int y = not x;

C. int y = !x;

D. int y = x~;

Solution

1. Step 1: Recall the bitwise NOT operator syntax

   In C, the bitwise NOT operator is the tilde symbol ~ placed before the variable.

2. Step 2: Check each option

   int y = not x; uses not which is not valid in C. int y = !x; uses logical NOT !. int y = x~; has incorrect placement of ~. Only int y = ~x; correctly uses ~x.

3. Final Answer:

   int y = ~x; -> Option A

4. Quick Check:

   Bitwise NOT syntax = ~x [OK]

Hint: Use ~ before variable for bitwise NOT [OK]

Common Mistakes:

• Using 'not' instead of ~
• Confusing logical NOT (!) with bitwise NOT (~)
• Placing ~ after the variable

3. What is the output of the following C code?

int x = 5;
int y = ~x;
printf("%d", y);

medium

A. 5

B. -6

C. -5

D. 6

Solution

1. Step 1: Convert 5 to binary and apply bitwise NOT

   5 in binary (32-bit) is 00000000 00000000 00000000 00000101. Applying ~ flips bits to 11111111 11111111 11111111 11111010.

2. Step 2: Interpret the result as a signed integer

   The result is the two's complement representation of -6.

3. Final Answer:

   -6 -> Option B

4. Quick Check:

   ~5 = -6 in two's complement [OK]

Hint: ~x equals -(x+1) for signed integers [OK]

Common Mistakes:

• Thinking ~5 equals 6 instead of -6
• Ignoring two's complement representation
• Confusing bitwise NOT with logical NOT

4. Identify the error in the following C code snippet:

int x = 10;
int y = ~ x;
printf("%d", y);

medium

A. There is a syntax error due to space between ~ and x.

B. The code will print 9 instead of expected -11.

C. No error; the code works and prints -11.

D. The printf format specifier is incorrect.

Solution

1. Step 1: Check syntax of bitwise NOT usage

   In C, spaces between operators and operands are allowed. So ~ x is valid and equivalent to ~x.

2. Step 2: Verify output and printf usage

   Applying ~10 results in -11. The printf format specifier %d is correct for int.

3. Final Answer:

   No error; the code works and prints -11. -> Option C

4. Quick Check:

   Space allowed after ~, output = -11 [OK]

Hint: Spaces don't break ~ operator usage [OK]

Common Mistakes:

• Thinking space causes syntax error
• Expecting positive output instead of negative
• Confusing format specifier for int

5. Given a signed 8-bit integer n, which expression correctly computes the bitwise NOT of n and then adds 1, effectively calculating the two's complement negation of n in C?

hard

A. ~n + 1

B. ~(n + 1)

C. -~n

D. -n + 1

Solution

1. Step 1: Understand two's complement negation

   Two's complement negation of a number n is computed as ~n + 1.

2. Step 2: Analyze each option

   ~n + 1 matches the formula. ~(n + 1) negates after adding 1, which is incorrect. -~n negates the bitwise NOT, not the number. -n + 1 is arithmetic negation plus 1, which is not two's complement negation.

3. Final Answer:

   ~n + 1 -> Option A

4. Quick Check:

   Two's complement negation = ~n + 1 [OK]

Hint: Two's complement negation = ~n + 1 [OK]

Common Mistakes:

• Using -(~n) instead of ~n + 1
• Applying ~ after adding 1
• Confusing arithmetic negation with bitwise negation