Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA C# - Time & Space Complexity

Time Complexity: Bit Manipulation Basics AND OR XOR NOT Left Right Shift

O(1)

Understanding Time Complexity

Bit manipulation operations are very fast and work directly on the binary form of numbers.

We want to understand how the time to perform these operations changes as the number size grows.

Scenario Under Consideration

Analyze the time complexity of the following bit manipulation operations.

int a = 5;          // 0101 in binary
int b = 9;          // 1001 in binary
int andResult = a & b;   // AND operation
int orResult = a | b;    // OR operation
int xorResult = a ^ b;   // XOR operation
int notResult = ~a;      // NOT operation
int leftShift = a << 2;  // Left shift by 2 bits
int rightShift = b >> 1; // Right shift by 1 bit
    

This code performs basic bitwise operations on two integers.

Identify Repeating Operations

Bitwise operations work on each bit of the numbers.

• Primary operation: Processing each bit of the integer.
• How many times: Once per bit in the integer (usually 32 or 64 bits).

How Execution Grows With Input

Each operation looks at every bit once, so the time grows with the number of bits.

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

Pattern observation: The time grows linearly with the number of bits in the number.

Final Time Complexity

Time Complexity: O(1)

This means bitwise operations take constant time because the number of bits is fixed by the system.

Common Mistake

[X] Wrong: "Bitwise operations take longer as the number value grows."

[OK] Correct: The time depends on the number of bits, not the value size. The bit count is fixed (like 32 or 64 bits), so time stays constant.

Interview Connect

Understanding bitwise operations and their constant time nature helps you write efficient low-level code and answer common interview questions confidently.

Self-Check

"What if we used a custom big integer type with thousands of bits? How would the time complexity change?"

Practice

1. What does the bitwise AND operator (&) do when applied to two bits?

easy

A. Returns 0 only if both bits are 0

B. Returns 1 if either bit is 1

C. Flips the bits from 0 to 1 and 1 to 0

D. Returns 1 only if both bits are 1

Solution

1. Step 1: Understand bitwise AND operation

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

2. Step 2: Apply to example bits

   For bits 1 & 1, result is 1; for 1 & 0 or 0 & 1 or 0 & 0, result is 0.

3. Final Answer:

   Returns 1 only if both bits are 1 -> Option D

4. Quick Check:

   AND = 1 only if both bits 1 [OK]

Hint: AND returns 1 only when both bits are 1 [OK]

Common Mistakes:

• Confusing AND with OR operator
• Thinking AND flips bits
• Assuming AND returns 1 if either bit is 1

2. Which of the following is the correct syntax to perform a left shift by 2 on an integer variable x in C#?

easy

A. x >> 2;

B. x << 2;

C. x <<< 2;

D. x >> 2 <<;

Solution

1. Step 1: Recall left shift operator syntax in C#

   The left shift operator is << and used as x << n to shift bits left by n places.

2. Step 2: Identify correct syntax among options

   x << 2; uses x << 2; which is correct. x >> 2; is right shift, C uses invalid operator, D is invalid syntax.

3. Final Answer:

   x << 2; -> Option B

4. Quick Check:

   Left shift syntax is x << n [OK]

Hint: Use << for left shift, >> for right shift [OK]

Common Mistakes:

• Using >>> which is invalid in C#
• Confusing left shift with right shift
• Adding extra symbols after shift operator

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

int a = 5; // binary 0101
int b = 3; // binary 0011
int c = a ^ b;
Console.WriteLine(c);

medium

A. 2

B. 7

C. 6

D. 8

Solution

1. Step 1: Convert numbers to binary and apply XOR

   5 in binary is 0101, 3 is 0011. XOR (^) returns 1 if bits differ, else 0.

2. Step 2: Calculate XOR bit by bit

   0101 ^ 0011 = 0110 (binary), which is 6 in decimal.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   5 ^ 3 = 6 [OK]

Hint: XOR sets bits where inputs differ [OK]

Common Mistakes:

• Confusing XOR with OR or AND
• Calculating decimal sum instead of XOR
• Misreading binary values

4. Identify the error in the following C# code snippet that attempts to invert bits of an integer num:

int num = 12;
int inverted = ~num();
Console.WriteLine(inverted);

medium

A. Using parentheses after variable name num()

B. Using bitwise NOT operator incorrectly

C. Missing semicolon after int num = 12

D. Console.WriteLine cannot print integers

Solution

1. Step 1: Check usage of variable num

   The code uses num() which looks like a function call but num is an integer variable, so parentheses are invalid.

2. Step 2: Confirm bitwise NOT operator usage

   The bitwise NOT operator ~ is correctly used before the variable, so no error there.

3. Final Answer:

   Using parentheses after variable name num() -> Option A

4. Quick Check:

   Variables don't use () [OK]

Hint: Variables are not functions; no () after variable names [OK]

Common Mistakes:

• Thinking ~num() is valid syntax
• Assuming missing semicolon error
• Believing Console.WriteLine can't print integers

5. Given an integer n = 8, which expression correctly checks if n is a power of two using bit manipulation in C#?

hard

A. (n & (n - 1)) == 0

B. (n | (n - 1)) == 0

C. (n ^ (n - 1)) == 0

D. (~n & (n - 1)) == 0

Solution

1. Step 1: Understand the power of two property

   A number is a power of two if it has exactly one bit set to 1 in binary.

2. Step 2: Apply bitwise trick

   For such numbers, n & (n - 1) clears the lowest set bit. If result is 0, n was a power of two.

3. Final Answer:

   (n & (n - 1)) == 0 -> Option A

4. Quick Check:

   Power of two check uses n & (n-1) == 0 [OK]

Hint: Power of two if n & (n-1) equals zero [OK]

Common Mistakes:

• Using OR or XOR instead of AND
• Forgetting to compare result to zero
• Misunderstanding bitwise NOT usage