Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Rust - 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 bits of numbers.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn bit_operations(x: u32, y: u32) -> (u32, u32, u32, u32, u32, u32) {
    let and = x & y;          // AND
    let or = x | y;           // OR
    let xor = x ^ y;          // XOR
    let not_x = !x;           // NOT
    let left_shift = x << 2;  // Left shift by 2
    let right_shift = y >> 3; // Right shift by 3
    (and, or, xor, not_x, left_shift, right_shift)
}
    

This code performs basic bit operations on two 32-bit numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single bitwise operations on fixed-size integers.
• How many times: Each operation processes all bits in parallel internally, but from code perspective, each is one operation.

How Execution Grows With Input

Bitwise operations work on fixed-size numbers, so time does not grow with input size in typical use.

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

Pattern observation: Time stays constant because hardware handles all bits at once.

Final Time Complexity

Time Complexity: O(1)

This means bit operations take the same time regardless of the number size within fixed limits.

Common Mistake

[X] Wrong: "Bitwise operations take longer on bigger numbers because they have more bits."

[OK] Correct: Hardware processes all bits in parallel for fixed sizes like 32 or 64 bits, so time stays constant.

Interview Connect

Knowing bit operations are constant time helps you write efficient code and answer questions confidently.

Self-Check

"What if we used bit operations on very large numbers stored as arrays of bits? How would the time complexity change?"

Practice

1. What is the result of the bitwise AND operation between 0b1101 and 0b1011?

easy

A. 0b1001

B. 0b1111

C. 0b0101

D. 0b0011

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: Apply AND to each bit of 0b1101 and 0b1011

   Bits: 1&1=1, 1&0=0, 0&1=0, 1&1=1, so result is 0b1001.

3. Final Answer:

   0b1001 -> Option A

4. Quick Check:

   1101 & 1011 = 1001 [OK]

Hint: AND keeps bits set only if both are 1 [OK]

Common Mistakes:

• Confusing AND with OR operation
• Mixing bit positions when calculating
• Forgetting binary format in answer

2. Which of the following is the correct Rust syntax to perform a bitwise XOR between variables a and b?

easy

A. let c = a & b;

B. let c = a && b;

C. let c = a ^ b;

D. let c = a | b;

Solution

1. Step 1: Recall Rust bitwise XOR operator

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

2. Step 2: Check each option's operator

   The options use: & (bitwise AND), && (logical AND), | (bitwise OR), ^ (bitwise XOR). Only ^ is correct.

3. Final Answer:

   let c = a ^ b; -> Option C

4. Quick Check:

   Bitwise XOR in Rust uses ^ [OK]

Hint: XOR uses ^ symbol in Rust [OK]

Common Mistakes:

• Using && instead of ^ for XOR
• Confusing bitwise OR (|) with XOR
• Using logical operators instead of bitwise

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

let x: u8 = 0b0011_1100;
let y: u8 = 0b0000_1101;
let z = x | y;
println!("{:08b}", z);

medium

A. 00111101

B. 00110001

C. 00001101

D. 00111100

Solution

1. Step 1: Understand bitwise OR operation

   Bitwise OR returns 1 if at least one bit is 1 in either number.

2. Step 2: Apply OR to each bit of x and y

   x = 00111100, y = 00001101; OR bits: 0|0=0,0|0=0,1|0=1,1|0=1,1|1=1,1|1=1,0|0=0,0|1=1; result = 00111101.

3. Final Answer:

   00111101 -> Option A

4. Quick Check:

   00111100 | 00001101 = 00111101 [OK]

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

Common Mistakes:

• Mixing OR with AND operation
• Misreading binary digits
• Ignoring leading zeros in output

4. Identify the error in this Rust code snippet that attempts to left shift a variable:

let a: u8 = 0b0001_0001;
let b = a << 8
println!("{:08b}", b);

medium

A. Incorrect use of << operator, should be >>

B. Shift amount exceeds variable bit size causing overflow

C. Cannot print binary format with {:08b}

D. Missing semicolon after variable declaration

Solution

1. Step 1: Check for syntax errors

   The declaration 'let b = a << 8' is missing a semicolon (;).

2. Step 2: Verify other parts

   << is correct for left shift; Rust masks large shift amounts without panic/overflow error; {:08b} works for binary output.

3. Final Answer:

   Missing semicolon after variable declaration -> Option D

4. Quick Check:

   Missing ; after let causes compile error [OK]

Hint: Rust statements must end with semicolon [OK]

Common Mistakes:

• Omitting semicolons after let statements
• Confusing left shift with right shift
• Assuming shifts panic on large amounts

5. Given a 16-bit unsigned integer num, which Rust expression correctly clears (sets to 0) the 5th bit (counting from 0 at the right) without affecting other bits?

hard

A. num | (1 << 5)

B. num & !(1 << 5)

C. num ^ (1 << 5)

D. num << 5

Solution

1. Step 1: Understand clearing a bit

   To clear a bit, use AND with a mask that has 0 at target bit and 1 elsewhere.

2. Step 2: Create mask for 5th bit

   1 << 5 creates a mask with 1 at 5th bit; negating it with ! flips bits, making 0 at 5th bit.

3. Step 3: Apply mask with AND

   num & !(1 << 5) clears 5th bit, keeps others unchanged.

4. Final Answer:

   num & !(1 << 5) -> Option B

5. Quick Check:

   Clear bit 5 using AND with inverted mask [OK]

Hint: Clear bit with AND and inverted mask [OK]

Common Mistakes:

• Using OR instead of AND to clear bits
• Using XOR which toggles bits
• Shifting num instead of mask