Module 2.4 ⏱ 30 min read ⚡ Strings & Bit Manipulation

Strings & Basic Bitwise Operations

Explore string immutability performance trade-offs and unlock hyper-efficient optimizations using core bitwise arithmetic operators.

1. String Immutability & Memory Trade-offs

In languages like Python and Java, strings are immutable—meaning their underlying character sequences cannot be modified in place. Every time you concatenate or modify a string using standard operators, the runtime allocates an entirely new block of memory and copies existing contents over, turning repeated concatenation loops into costly $O(n^2)$ bottlenecks.

To achieve optimal performance, use mutable alternatives like `StringBuilder` in Java, list joins in Python, or character vectors in C++ when performing iterative string construction.

2. Bitwise Operators & Fast Optimizations

Bitwise operators manipulate individual binary bits directly at the hardware level, providing extremely fast arithmetic and logical alternatives:

AND (`&`), OR (`|`), XOR (`^`): Logical operations performed bit-by-bit. XOR is especially powerful in interviews due to its unique property: any number XORed with itself results in zero ($x \mathbin{\hat{}} x = 0$), and any number XORed with zero yields itself ($x \mathbin{\hat{}} 0 = x$).

Shifting (`<<`, `>>`): Bit shifts multiply or divide numbers by powers of 2 in $O(1)$ time.

3. Single Number Identification Using XOR

By leveraging XOR commutativity and associativity, you can find a unique element in an array where every other element appears twice in $O(n)$ time and $O(1)$ auxiliary space.

// C++ Solution: Single Number using XOR Bitwise Operation
#include <vector>

class Solution {
public:
    int singleNumber(std::vector<int>& nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
};
            

# Python Solution: Single Number using XOR Bitwise Operation
class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        ans = 0
        for num in nums:
            ans ^= num
        return ans
            

// Java Solution: Single Number using XOR Bitwise Operation
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
}
            

4. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for Valid Anagram checks (using frequency arrays or hash maps) and Single Number Identification using bitwise XOR.

Quick Check: Test Your Intuition

What is the result of performing the bitwise XOR operation on any integer `x` with itself ($x \mathbin{\hat{}} x$)?