Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Rust

Mental Model

Bit manipulation changes numbers by flipping or moving their tiny on/off switches called bits.

Analogy: Imagine a row of light switches where each switch can be on (1) or off (0). Bit operations turn switches on, off, flip them, or slide the whole row left or right.

Number: 13
Bits:  0 0 0 0 1 1 0 1
Index: 7 6 5 4 3 2 1 0

Dry Run Walkthrough

Input: number1 = 13 (00001101), number2 = 10 (00001010)

Goal: Show how AND, OR, XOR, NOT, left shift, and right shift change bits of these numbers

Step 1: Perform AND between number1 and number2

00001101 (13) AND 00001010 (10) = 00001000 (8)

Why: AND keeps bits on only if both numbers have that bit on

Step 2: Perform OR between number1 and number2

00001101 (13) OR 00001010 (10) = 00001111 (15)

Why: OR turns bits on if either number has that bit on

Step 3: Perform XOR between number1 and number2

00001101 (13) XOR 00001010 (10) = 00000111 (7)

Why: XOR turns bits on only if exactly one number has that bit on

Step 4: Perform NOT on number1

NOT 00001101 (13) = 11110010 (in 8-bit, equals 242 unsigned)

Why: NOT flips every bit from on to off or off to on

Step 5: Left shift number1 by 2 bits

00001101 (13) << 2 = 00110100 (52)

Why: Left shift moves bits left, adding zeros on the right, multiplying by 4

Step 6: Right shift number1 by 2 bits

00001101 (13) >> 2 = 00000011 (3)

Why: Right shift moves bits right, dropping bits on the right, dividing by 4

Result:

AND result: 00001000 (8)
OR result: 00001111 (15)
XOR result: 00000111 (7)
NOT result: 11110010 (242 unsigned)
Left shift result: 00110100 (52)
Right shift result: 00000011 (3)

Annotated Code

DSA Rust

fn main() {
    let number1: u8 = 13; // 00001101
    let number2: u8 = 10; // 00001010

    let and_result = number1 & number2; // AND operation
    let or_result = number1 | number2;  // OR operation
    let xor_result = number1 ^ number2; // XOR operation
    let not_result = !number1;           // NOT operation
    let left_shift_result = number1 << 2; // Left shift by 2
    let right_shift_result = number1 >> 2; // Right shift by 2

    println!("AND result: {:08b} ({})", and_result, and_result);
    println!("OR result: {:08b} ({})", or_result, or_result);
    println!("XOR result: {:08b} ({})", xor_result, xor_result);
    println!("NOT result: {:08b} ({})", not_result, not_result);
    println!("Left shift result: {:08b} ({})", left_shift_result, left_shift_result);
    println!("Right shift result: {:08b} ({})", right_shift_result, right_shift_result);
}

let and_result = number1 & number2;

Perform AND to keep bits on only if both bits are on

let or_result = number1 | number2;

Perform OR to turn bits on if either bit is on

let xor_result = number1 ^ number2;

Perform XOR to turn bits on if exactly one bit is on

let not_result = !number1;

Flip all bits using NOT

let left_shift_result = number1 << 2;

Shift bits left by 2, adding zeros on right

let right_shift_result = number1 >> 2;

Shift bits right by 2, dropping bits on right

Output

AND result: 00001000 (8)

OR result: 00001111 (15)

XOR result: 00000111 (7)

NOT result: 11110010 (242)

Left shift result: 00110100 (52)

Right shift result: 00000011 (3)

Complexity Analysis

Time: O(1) because bit operations work on fixed-size numbers instantly

Space: O(1) because no extra memory grows with input size

vs Alternative: Bit manipulation is much faster and uses less memory than arithmetic or loops for these operations

Edge Cases

number is zero

AND, OR, XOR with zero behave normally; NOT flips all bits from zero to all ones

DSA Rust

let not_result = !number1;

left shift causes bits to move out of range

bits shifted out are lost, result may wrap or become zero

DSA Rust

let left_shift_result = number1 << 2;

right shift on zero

result remains zero, no bits to shift

DSA Rust

let right_shift_result = number1 >> 2;

When to Use This Pattern

When you see problems asking to flip bits, check if bits match, or multiply/divide by powers of two, use bit manipulation for fast, simple solutions.

Common Mistakes

Mistake: Confusing left shift with multiplication by 2 without considering overflow
Fix: Remember left shift multiplies by powers of two only if bits don't overflow the fixed size

Mistake: Using NOT without considering number size causing unexpected large values
Fix: Use fixed-size types and understand NOT flips all bits including leading zeros

Summary

Bit manipulation changes numbers by turning bits on/off, flipping them, or shifting their positions.

Use it when you need fast, low-level control over numbers or to solve problems involving bits.

The key insight is that numbers are just switches (bits) that you can control directly for efficient operations.

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