Bitwise operators in Rust - Time & Space Complexity

Time Complexity: Bitwise operators

O(n)

Understanding Time Complexity

Bitwise operators work directly on the bits of numbers. Understanding their time complexity helps us know how fast these operations run as numbers get bigger.

We want to see how the time to do bitwise operations changes when the size of the number changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn bitwise_and(a: u32, b: u32) -> u32 {
    a & b
}

fn bitwise_or(a: u32, b: u32) -> u32 {
    a | b
}

fn bitwise_xor(a: u32, b: u32) -> u32 {
    a ^ b
}
    

This code performs simple bitwise AND, OR, and XOR operations on two 32-bit unsigned integers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise operation on each bit of the input numbers.
• How many times: Once per bit, so 32 times for u32 numbers.

How Execution Grows With Input

Each bitwise operation checks each bit once. If the number size doubles, the bits double, so the work doubles too.

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

Pattern observation: The operations grow linearly with the number of bits in the input.

Final Time Complexity

Time Complexity: O(n)

This means the time to do bitwise operations grows in a straight line with the number of bits in the numbers.

Common Mistake

[X] Wrong: "Bitwise operations always run instantly, no matter the number size."

[OK] Correct: Bitwise operations run once per bit, so bigger numbers with more bits take more time.

Interview Connect

Knowing bitwise operation time helps you understand low-level code speed and is useful when optimizing or working with hardware-level tasks.

Self-Check

"What if we used 128-bit numbers instead of 32-bit? How would the time complexity change?"

Practice

1. Which bitwise operator in Rust returns 1 only if both bits are 1?
Example: 5 & 3

easy

A. AND (&)

B. OR (|)

C. XOR (^)

D. NOT (!)

Solution

1. Step 1: Understand the AND operator

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

2. Step 2: Compare with other operators

   OR (|) returns 1 if either bit is 1, XOR (^) returns 1 if bits differ, NOT (!) flips bits.

3. Final Answer:

   AND (&) -> Option A

4. Quick Check:

   AND returns 1 only if both bits are 1 [OK]

Hint: AND is the only operator needing both bits as 1 [OK]

Common Mistakes:

• Confusing AND with OR which returns 1 if either bit is 1
• Thinking XOR returns 1 if both bits are 1
• Using NOT (!) as a binary operator instead of unary

2. Which of the following is the correct syntax for a bitwise XOR operation in Rust between variables a and b?

easy

A. a ! b

B. a & b

C. a | b

D. a ^ b

Solution

1. Step 1: Recall XOR operator symbol

   In Rust, the bitwise XOR operator is represented by the caret symbol (^).

2. Step 2: Check other operators

   & is AND, | is OR, and ! is unary NOT, so only a ^ b is correct for XOR.

3. Final Answer:

   a ^ b -> Option D

4. Quick Check:

   XOR uses ^ symbol in Rust [OK]

Hint: XOR uses ^ symbol, not & or | [OK]

Common Mistakes:

• Using & or | instead of ^ for XOR
• Trying to use ! as a binary operator
• Confusing syntax with other languages

3. What is the output of this Rust code?

let x = 0b1010;  // binary 10
let y = 0b1100;  // binary 12
let result = x | y;
println!("{:04b}", result);

medium

A. 1000

B. 1110

C. 0110

D. 1010

Solution

1. Step 1: Convert binary to bits and apply OR

   x = 1010, y = 1100. OR (|) returns 1 if either bit is 1. 1010 | 1100 = 1110

2. Step 2: Print result in 4-bit binary

   Result is 1110 in binary, which matches 1110.

3. Final Answer:

   1110 -> Option B

4. Quick Check:

   Bitwise OR of 1010 and 1100 = 1110 [OK]

Hint: OR sets bits where either input bit is 1 [OK]

Common Mistakes:

• Mixing up OR with AND results
• Reading binary digits incorrectly
• Forgetting to print in binary format

4. Identify the error in this Rust code snippet:

let a = 0b1010;
let b = 0b0101;
let c = a && b;
println!("{}", c);

medium

A. Incorrect binary literal syntax

B. Missing semicolon after let b

C. Using && instead of & for bitwise AND

D. println! macro missing format specifier

Solution

1. Step 1: Check operator usage

   The code uses && which is a logical AND, not bitwise AND. Bitwise AND uses &.

2. Step 2: Verify other syntax

   Semicolons are present, binary literals are correct, and println! has a format specifier, so no errors there.

3. Final Answer:

   Using && instead of & for bitwise AND -> Option C

4. Quick Check:

   Bitwise AND uses & not && [OK]

Hint: Use & for bitwise AND, && is logical AND [OK]

Common Mistakes:

• Confusing logical AND (&&) with bitwise AND (&)
• Assuming binary literals need prefix changes
• Missing format specifier in println! macro

5. Given a number n, which Rust expression flips (toggles) the 3rd bit (counting from 0) of n using bitwise operators?

hard

A. n ^ (1 << 3)

B. n & (1 << 3)

C. n | (1 << 3)

D. ~n & (1 << 3)

Solution

1. Step 1: Understand bit flipping with XOR

   XOR (^) with 1 flips the bit: if bit is 0 it becomes 1, if 1 it becomes 0. Shifting 1 by 3 sets the mask for the 3rd bit.

2. Step 2: Analyze other options

   & with mask clears bits except the 3rd bit, | sets the 3rd bit to 1, ~n & mask is unrelated to flipping a single bit.

3. Final Answer:

   n ^ (1 << 3) -> Option A

4. Quick Check:

   XOR with bit mask flips that bit [OK]

Hint: XOR with 1 at bit position flips that bit [OK]

Common Mistakes:

• Using & or | which clear or set bits instead of flipping
• Confusing ~ (NOT) usage
• Not shifting 1 to correct bit position