Bitwise AND, OR, XOR in C - Time & Space Complexity

Time Complexity: Bitwise AND, OR, XOR

O(n)

Understanding Time Complexity

We want to understand how the time it takes to do bitwise AND, OR, and XOR changes as the size of the numbers grows.

How does the number of steps grow when we work with bigger numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int bitwise_operations(unsigned int a, unsigned int b) {
    unsigned int and_result = a & b;
    unsigned int or_result = a | b;
    unsigned int xor_result = a ^ b;
    return and_result + or_result + xor_result;
}
    

This code performs bitwise AND, OR, and XOR on two unsigned integers and returns the sum of the results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise operations on each bit of the input numbers.
• How many times: Once per bit in the numbers (usually fixed, like 32 or 64 bits).

How Execution Grows With Input

Each bit in the input numbers is processed once. If the number size grows, the steps grow linearly with the number of bits.

Input Size (bits)	Approx. Operations
8	8 steps
32	32 steps
64	64 steps

Pattern observation: The number of steps grows directly with the number of bits in the input numbers.

Final Time Complexity

Time Complexity: O(n)

This means the time to do bitwise AND, OR, and XOR grows linearly with the number of bits in the input numbers.

Common Mistake

[X] Wrong: "Bitwise operations are instant and take the same time no matter the number size."

[OK] Correct: While bitwise operations are very fast, they still process each bit. Larger numbers with more bits take proportionally more steps.

Interview Connect

Understanding how bitwise operations scale helps you reason about low-level code efficiency and is a useful skill in many programming tasks.

Self-Check

"What if we used bitwise operations on arrays of numbers instead of single numbers? How would the time complexity change?"

Practice

1. Which bitwise operator in C returns 1 only if both corresponding bits of two numbers are 1?
a & b means:

easy

A. Bitwise AND

B. Bitwise OR

C. Bitwise XOR

D. Logical AND

Solution

1. Step 1: Understand bitwise AND operation

   Bitwise AND compares each bit of two numbers and returns 1 only if both bits are 1.

2. Step 2: Compare with other operators

   Bitwise OR returns 1 if either bit is 1, XOR returns 1 if bits differ, and logical AND is different (works on boolean values).

3. Final Answer:

   Bitwise AND -> Option A

4. Quick Check:

   AND = & = Bitwise AND [OK]

Hint: AND means both bits must be 1 to get 1 [OK]

Common Mistakes:

• Confusing bitwise AND with logical AND (&&)
• Mixing AND with OR or XOR operators
• Thinking bitwise AND returns 1 if either bit is 1

2. Which of the following is the correct syntax to perform bitwise XOR on two integers a and b in C?

easy

A. a ^ b

B. a && b

C. a | b

D. a & b

Solution

1. Step 1: Identify bitwise XOR operator

   In C, the caret symbol (^) is used for bitwise XOR operation.

2. Step 2: Differentiate from other operators

   && is logical AND, | is bitwise OR, & is bitwise AND, so only ^ is XOR.

3. Final Answer:

   a ^ b -> Option A

4. Quick Check:

   ^ means XOR in C [OK]

Hint: XOR uses ^ symbol in C [OK]

Common Mistakes:

• Using && instead of ^ for XOR
• Confusing | (OR) with ^ (XOR)
• Using & (AND) instead of ^ (XOR)

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

int a = 6;  // binary 0110
int b = 11; // binary 1011
printf("%d", a & b);

medium

A. 3

B. 15

C. 7

D. 2

Solution

1. Step 1: Convert numbers to binary

   6 in binary is 0110, 11 in binary is 1011.

2. Step 2: Perform bitwise AND

   0110 & 1011 = 0010 (only bits where both are 1 remain 1).

3. Step 3: Convert result back to decimal

   0010 in decimal is 2.

4. Final Answer:

   2 -> Option D

5. Quick Check:

   6 & 11 = 2 [OK]

Hint: AND keeps bits set in both numbers only [OK]

Common Mistakes:

• Confusing AND with OR or XOR results
• Not converting binary back to decimal correctly
• Mixing up bit positions

4. Identify the error in this C code snippet that tries to perform bitwise OR:

int a = 5;
int b = 9;
int c = a | b;
printf("%d", c);

medium

A. Missing semicolon after variable declarations

B. Incorrect operator used for bitwise OR

C. No error, code will print correct output

D. printf format specifier should be %x for bitwise OR

Solution

1. Step 1: Check syntax correctness

   All lines have semicolons; operator | is correct for bitwise OR.

2. Step 2: Verify printf usage

   %d is correct to print integer decimal value; no error present.

3. Final Answer:

   No error, code will print correct output -> Option C

4. Quick Check:

   Bitwise OR uses | and %d prints decimal [OK]

Hint: Bitwise OR uses | and %d prints decimal [OK]

Common Mistakes:

• Thinking | is wrong operator for OR
• Believing %x is mandatory for bitwise results
• Missing semicolons (not the case here)

5. Given two integers x = 12 and y = 10, which expression toggles the bits of x where y has bits set, using bitwise XOR?

hard

A. x | y

B. x ^ y

C. x & y

D. ~x ^ y

Solution

1. Step 1: Understand toggling bits with XOR

   Bitwise XOR toggles bits where the second operand has 1s.

2. Step 2: Analyze each option

   x & y keeps bits set in both; x | y sets bits set in either; ~x ^ y is unrelated toggling with complement.

3. Final Answer:

   x ^ y -> Option B

4. Quick Check:

   XOR toggles bits where second operand has 1 [OK]

Hint: XOR toggles bits where second number has 1s [OK]

Common Mistakes:

• Using AND or OR instead of XOR for toggling
• Confusing complement operator ~ with XOR
• Not understanding toggling effect of XOR