L2. Must Know Tricks in Bit Manipulation | Swap Two Numbers Without Third Variable

Mastering bit manipulation is crucial for writing high-performance, low-level code in Data Structures and Algorithms (DSA). This chapter covers essential bitwise operations, common tricks, and interview-favourite patterns ranging from swapping numbers without temporary variables to counting set bits efficiently.

1. Why Do We Need Bit Manipulation Tricks?

Computers natively process data at the binary level (zeros and ones). While arithmetic and logical operators (+, -, *, /) are intuitive, they involve multiple CPU cycles and abstraction layers.

Performance & Speed: Bitwise operations (&, |, ^, <<, >>) execute directly at the hardware/ALU level, making them significantly faster than standard arithmetic.
Memory Efficiency: Storing flags or states as individual bits within a single integer reduces memory overhead.
Interview Standard: Top tech companies frequently test bit manipulation patterns to evaluate a candidate's understanding of binary arithmetic, masking, and low-level optimization.

2. Core Mental Model: The XOR Operator (`^`)

The exclusive-OR (XOR) operator is the cornerstone of several advanced algorithms.

Rule of XOR

Even number of 1s across corresponding bits results in 0.
Odd number of 1s across corresponding bits results in 1.

Key Mathematical Properties of XOR

Self-Inverse: XORing a number with itself yields 0.

\text{A} \mathbin{\hat{}} \text{A} = 0

Proof (Analogy): If 5 is represented in binary as 101, doing 5 ^ 5 compares every column, resulting in zero 1s (an even number), yielding 0 0 0. 2. Identity: XORing any number with 0 returns the number itself.

\text{A} \mathbin{\hat{}} 0 = \text{A}

Commutative & Associative: Order does not matter.

\text{A} \mathbin{\hat{}} \text{B} \mathbin{\hat{}} \text{A} = (\text{A} \mathbin{\hat{}} \text{A}) \mathbin{\hat{}} \text{B} = 0 \mathbin{\hat{}} \text{B} = \text{B}

3. Problem 1: Swap Two Numbers Without a Third Variable

Problem Statement

Given two integer variables A and B (e.g., A = 5, B = 6), swap their values without using any temporary third variable (temp).

Naive vs. Better Approach

Naive Approach: Introduce a temp variable to hold A while reassigning A = B and B = temp. This requires extra memory (though minimal).
Optimal Approach (XOR Swap): Utilize the commutative and self-inverse properties of XOR to swap values in place within 3 lines of code.

Step-by-Step Evolution

Structure & Concept Flow

Initial state: A = 5 (101), B = 6 (110)

Step 1: A = A ^ B

|-- A becomes (5 ^ 6)

Step 2: B = A ^ B

|-- Substituting A: B = (5 ^ 6) ^ 6

|-- Since (6 ^ 6) = 0, B becomes 5 (Original value of A!)

Step 3: A = A ^ B

|-- Substituting values: A = (5 ^ 6) ^ 5

|-- Since (5 ^ 5) = 0, A becomes 6 (Original value of B!)

Code Implementation

JAVA

public void swap(int a, int b) {
    a = a ^ b; // Step 1
    b = a ^ b; // Step 2: B now holds original A
    a = a ^ b; // Step 3: A now holds original B
}

4. Problem 2: Check If the $i^{\text{th}}$ Bit is Set or Not

Problem Statement

Given an integer n and an index i (0-indexed from right to left), determine whether the $i^{\text{th}}$ bit is set (1) or unset (0). Return true if set, else false.

Example: Let n = 13 (1101 in binary).

For i = 2: Bits are 0 1 2 $\rightarrow$ The $2^{\text{nd}}$ bit is 1 (True).
For i = 1: The $1^{\text{st}}$ bit is 0 (False).

Method A: Using the Left Shift Operator (`<<`)

Create a mask by taking 1 and left-shifting it by i places: 1 << i. This places a single 1 at the $i^{\text{th}}$ position and 0 everywhere else.
Perform a bitwise AND between n and the mask.
If the resulting number is non-zero, the bit is set.

JAVA

public boolean checkIthBitLeftShift(int n, int i) {
    // (1 << i) creates a mask with 1 at the i-th position
    if ((n & (1 << i)) != 0) {
        return true;
    }
    return false;
}

Method B: Using the Right Shift Operator (`>>`)

Right-shift the number n by i places: n >> i. This pushes the $i^{\text{th}}$ bit all the way to the extreme right (position 0).
Perform a bitwise AND with 1: (n >> i) & 1.
If the result is 1, the bit is set; if 0, it is unset.

JAVA

public boolean checkIthBitRightShift(int n, int i) {
    // Shift the target bit to the 0th position and check against 1
    if (((n >> i) & 1) == 1) {
        return true;
    }
    return false;
}

5. Problem 3: Setting the $i^{\text{th}}$ Bit

Problem Statement

Given an integer n and an index i, turn the $i^{\text{th}}$ bit to 1 (if it isn't already) while keeping all other bits unchanged.

Solution Approach

Generate a mask with a 1 at the $i^{\text{th}}$ position using left shift: 1 << i.
Perform a bitwise OR (|) between n and the mask.
- Why OR? Any bit ORed with 0 remains unchanged, while 0 ORed with 1 becomes 1.

JAVA

public int setIthBit(int n, int i) {
    // Using the bitwise OR operator with the left-shifted mask
    return n | (1 << i);
}

6. Problem 4: Clearing the $i^{\text{th}}$ Bit

Problem Statement

Given an integer n and an index i, clear the $i^{\text{th}}$ bit (i.e., turn 1 into 0, or keep 0 as 0) while leaving all other bits intact.

Solution Approach

Create a mask by left-shifting 1 by i places: 1 << i.
Invert (negate) the mask using the NOT operator (~), resulting in 0 at the $i^{\text{th}}$ position and 1 everywhere else.
Perform a bitwise AND (&) between n and the negated mask.
- Why AND with 0? Anything ANDed with 0 becomes 0, while anything ANDed with 1 remains unchanged.

JAVA

public int clearIthBit(int n, int i) {
    // ~(1 << i) creates a mask with 0 at the i-th position and 1s elsewhere
    return n & ~(1 << i);
}

7. Problem 5: Toggling the $i^{\text{th}}$ Bit

Problem Statement

Given an integer n and an index i, toggle the $i^{\text{th}}$ bit. If it is 1, make it 0; if it is 0, make it 1.

Solution Approach

Create a mask using 1 << i.
Perform a bitwise XOR (^) between n and the mask.
- Why XOR? XORing with 1 flips the bit (since 1 ^ 1 = 0 and 0 ^ 1 = 1), whereas XORing with 0 leaves bits unchanged.

JAVA

public int toggleIthBit(int n, int i) {
    return n ^ (1 << i);
}

8. Problem 6: Removing the Last (Rightmost) Set Bit

Problem Statement

Given an integer n, remove its rightmost set bit (turn the lowest-order 1 into 0) while keeping all other bits unchanged.

Example:

n = 12 (1100) $\rightarrow$ Rightmost set bit is at position 2 $\rightarrow$ Result: 8 (1000).
n = 13 (1101) $\rightarrow$ Rightmost set bit is at position 0 $\rightarrow$ Result: 12 (1100).

The Crucial Observation: `n` vs. `n - 1`

When you subtract 1 from a number n:

The rightmost set bit in n becomes 0.
All bits to the right of that rightmost set bit (which were all 0s) get flipped to 1s.
All bits to the left of that rightmost set bit remain completely unchanged.

Structure & Concept Flow

Example with n = 40 (Binary: 101000)

--------------------------------------

n = 101000 (Rightmost set bit is at index 3)

n - 1 = 100111 (Bit 3 flipped to 0, trailing bits flipped to 1)

If we perform: n & (n - 1)

101000 (n)

& 100111 (n - 1)

----------------

100000 (Result: Rightmost set bit removed!)

Code Implementation

JAVA

public int removeLastSetBit(int n) {
    return n & (n - 1);
}

9. Problem 7: Check If a Number Is a Power of Two

Problem Statement

Given a positive integer n, determine if it is an exact power of two (e.g., 1, 2, 4, 8, 16, 32).

Core Insight

Every power of two has exactly one set bit in its binary representation.
Numbers that are not powers of two have two or more set bits.

Using the `n & (n - 1)` Trick

When you apply n & (n - 1) to a power of two, the single set bit is cleared, resulting in 0. If a number has multiple set bits, clearing the rightmost one leaves other bits intact, resulting in a non-zero value.

JAVA

public boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    // If n & (n - 1) is 0, it has only one set bit
    return (n & (n - 1)) == 0;
}

10. Problem 8: Counting the Number of Set Bits

Problem Statement

Given an integer n, return the total count of set bits (1s) in its binary representation.

Approach 1: Standard Division / Bit Shift (Brute Force)

Iterate through all bits by right-shifting n by 1 at each step (equivalent to dividing by 2) and checking the remainder using n & 1.

JAVA

public int countSetBitsBrute(int n) {
    int count = 0;
    while (n > 0) {
        if ((n & 1) == 1) {
            count++;
        }
        n = n >> 1; // Divide by 2
    }
    return count;
}

Time Complexity: $\mathcal{O}(\log n)$ or proportional to the total number of bits (32 iterations for an integer).

Approach 2: Brian Kernighan’s Algorithm (Optimal)

Instead of checking every single bit position, repeatedly clear the rightmost set bit using n = n & (n - 1) until n becomes 0. The loop runs exactly as many times as there are set bits.

JAVA

public int countSetBitsOptimal(int n) {
    int count = 0;
    while (n > 0) {
        n = n & (n - 1); // Clears the rightmost set bit
        count++;
    }
    return count;
}

Time Complexity: $\mathcal{O}(\text{number of set bits})$ , which is much faster in practice than checking all 32 bits.

Built-In C++ STL Alternative

In C++ competitive programming, you can use the built-in GCC compiler intrinsic to count set bits in $\mathcal{O}(1)$ hardware time:

C++

int totalBits = __builtin_popcount(n);

Summary and Key Takeaways

XOR Properties: A ^ A = 0 and A ^ 0 = A form the foundation of swap algorithms and toggling operations.
XOR Swap: Swap two variables without a temporary variable using a = a ^ b; b = a ^ b; a = a ^ b;.
Left Shift (<<): Used for masking and positioning bits (1 << i).
Right Shift (>>): Used for inspecting target bits by shifting them to the 0th position (n >> i).
Check Bit: Use (n & (1 << i)) != 0 or ((n >> i) & 1) == 1.
Set Bit: Use n | (1 << i).
Clear Bit: Use n & ~(1 << i).
Toggle Bit: Use n ^ (1 << i).
The Magic Trick (n & (n - 1)): Instantly removes the rightmost set bit, checks for powers of two, and powers Brian Kernighan's bit-counting algorithm.

L2. Must Know Tricks in Bit Manipulation | Swap two numbers without third variable

L2. Must Know Tricks in Bit Manipulation | Swap Two Numbers Without Third Variable

1. Why Do We Need Bit Manipulation Tricks?

2. Core Mental Model: The XOR Operator (^)

Rule of XOR

Key Mathematical Properties of XOR

3. Problem 1: Swap Two Numbers Without a Third Variable

Problem Statement

Naive vs. Better Approach

Step-by-Step Evolution

Code Implementation

4. Problem 2: Check If the ithi^{\text{th}}ith Bit is Set or Not

Problem Statement

Method A: Using the Left Shift Operator (<<)

Method B: Using the Right Shift Operator (>>)

5. Problem 3: Setting the ithi^{\text{th}}ith Bit

Problem Statement

Solution Approach

6. Problem 4: Clearing the ithi^{\text{th}}ith Bit

Problem Statement

Solution Approach

7. Problem 5: Toggling the ithi^{\text{th}}ith Bit

Problem Statement

Solution Approach

8. Problem 6: Removing the Last (Rightmost) Set Bit

Problem Statement

The Crucial Observation: n vs. n - 1

Code Implementation

9. Problem 7: Check If a Number Is a Power of Two

Problem Statement

Core Insight

Using the n & (n - 1) Trick

10. Problem 8: Counting the Number of Set Bits

Problem Statement

Approach 1: Standard Division / Bit Shift (Brute Force)

Approach 2: Brian Kernighan’s Algorithm (Optimal)

Built-In C++ STL Alternative

Summary and Key Takeaways

2. Core Mental Model: The XOR Operator (`^`)

4. Problem 2: Check If the $i^{\text{th}}$ Bit is Set or Not

Method A: Using the Left Shift Operator (`<<`)

Method B: Using the Right Shift Operator (`>>`)

5. Problem 3: Setting the $i^{\text{th}}$ Bit

6. Problem 4: Clearing the $i^{\text{th}}$ Bit

7. Problem 5: Toggling the $i^{\text{th}}$ Bit

The Crucial Observation: `n` vs. `n - 1`

Using the `n & (n - 1)` Trick