Data Structures and Algorithms in C (DSA)

📘 Chapter 41: Bit Manipulation and XOR Tricks

So far, we've treated numbers as abstract values, performing arithmetic operations and using them in various data structures and algorithms. However, beneath this abstraction, computers store and process all data, including numbers, as sequences of **bits** (binary digits, 0s and 1s). Bit manipulation is the art and science of directly operating on these individual bits. This technique is invaluable for optimizing code, managing flags efficiently, working with low-level hardware, and solving specific algorithmic problems with surprising elegance and speed. Mastering it can set you apart in technical interviews and competitive programming.

🧮 Understanding Basic Bitwise Operators

Bitwise operators perform operations on corresponding bits of their operands. Let's look at the fundamental ones:

A = 5  (0101)
B = 3  (0011)
-----
A & B = 1 (0001)

A = 5  (0101)
B = 3  (0011)
-----
A | B = 7 (0111)

A = 5  (0101)
B = 3  (0011)
-----
A ^ B = 6 (0110)

~5 (assuming 8-bit for visual, usually 32 or 64)
00000101
11111010  (Binary complement)
          = -6 (decimal, in 2's complement)

5 << 1
0101 << 1 = 1010 (10)

1 << k  (creates a mask with only the k-th bit set, 0-indexed)

5 >> 1
0101 >> 1 = 0010 (2)

🪄 Essential Bit Manipulation Tricks and Patterns

These are common idioms and techniques that leverage bitwise operations for efficiency and problem-solving:

• 1. Checking if the $k$-th bit is set:

  // Check if k-th bit (0-indexed) of num is 1
  bool is_set = (num & (1 << k)) != 0;
  // Alternative:
  // bool is_set = ((num >> k) & 1) != 0;

  The expression `(1 << k)` creates a mask with only the $k$-th bit set. `&` operation isolates that bit. If the result is non-zero, the bit was set.

• 2. Setting the $k$-th bit:

  // Set the k-th bit of num to 1
  num = num | (1 << k);

  Using `OR` with a mask ensures the $k$-th bit becomes 1, while other bits remain unchanged (because `X | 0 = X`).

• 3. Clearing the $k$-th bit:

  // Clear (set to 0) the k-th bit of num
  num = num & ~(1 << k);

  `~(1 << k)` creates a mask with all bits set to 1 *except* the $k$-th bit, which is 0. `AND`ing with this mask clears the $k$-th bit and preserves others.

• 4. Toggling the $k$-th bit:

  // Flip (toggle) the k-th bit of num
  num = num ^ (1 << k);

  XORing with a mask flips only the $k$-th bit (`X ^ 1 = ~X`) and leaves others unchanged (`X ^ 0 = X`).

• 5. Checking if a number is a power of 2:

  // For positive num:
  bool is_power_of_2 = (num > 0) && ((num & (num - 1)) == 0);

  A positive power of 2 (e.g., 4 (0100), 8 (1000)) has only one bit set. Subtracting 1 from it (e.g., 4-1=3 (0011)) flips that set bit to 0 and all trailing 0s to 1s. Their `AND` result is 0.

• 6. Counting set bits (Brian Kernighan's Algorithm):

  int countSetBits(int n) {
      int count = 0;
      while (n > 0) {
          n &= (n - 1); // Clears the least significant set bit
          count++;
      }
      return count;
  }

  This highly efficient algorithm runs in time proportional to the number of set bits. The operation `n & (n-1)` effectively turns off the rightmost (least significant) set bit.

• 7. Getting the Rightmost Set Bit:

  // For num = 12 (1100), result = 4 (0100)
  // For num = 6 (0110), result = 2 (0010)
  int rightmost_set_bit = num & (-num);

  In two's complement, `-num` is `~num + 1`. This trick leverages the properties of binary representation to isolate the lowest set bit. Critical in Fenwick Trees.

• 8. Swapping two numbers without a temporary variable (XOR Swap):

  int a = 5, b = 10;
  a = a ^ b; // a now holds (original_a ^ original_b)
  b = a ^ b; // b now holds (original_a ^ original_b) ^ original_b = original_a
  a = a ^ b; // a now holds (original_a ^ original_b) ^ original_a = original_b

  This works because XOR is commutative and associative, and $X \oplus X = 0$ and $X \oplus 0 = X$.

• 9. Finding the unique number in an array where all others appear twice:

  int findUnique(const vector<int>& nums) {
      int result = 0;
      for (int num : nums) {
          result ^= num; // XORing a number with itself cancels it out
      }
      return result; // The remaining number is the unique one
  }

  Since $X \oplus X = 0$ and $X \oplus 0 = X$, all pairs of numbers will cancel out, leaving only the unique element.

• 10. Finding the two unique numbers in an array where all others appear twice:

  // Example: nums = [1, 2, 1, 3, 2, 5]. Unique: 3, 5.
  pair<int, int> findTwoUnique(const vector<int>& nums) {
      int xor_sum = 0;
      for (int num : nums) {
          xor_sum ^= num; // xor_sum = unique1 ^ unique2
      }
  
      // Find a set bit in xor_sum (e.g., the rightmost set bit)
      // This bit must be different between unique1 and unique2
      int rightmost_set_bit_mask = xor_sum & (-xor_sum);
  
      int unique1 = 0;
      int unique2 = 0;
  
      // Partition numbers into two groups based on that set bit
      for (int num : nums) {
          if ((num & rightmost_set_bit_mask) != 0) {
              unique1 ^= num; // XOR all numbers with this bit set
          } else {
              unique2 ^= num; // XOR all numbers with this bit not set
          }
      }
      return {unique1, unique2};
  }

  This trick first finds the XOR sum of the two unique numbers. Then, it identifies *any* bit that is set in this XOR sum (meaning it's different between the two unique numbers). It then partitions the entire array into two groups: those that have this bit set and those that don't. XORing numbers within each group then reveals one unique number in each group, as all duplicates will still cancel out.

🎯 Applications and Real-World Use Cases

• Bitmasks for Set Representation:

  An integer can efficiently represent a set of items, where each bit corresponds to an item's presence or absence. This is common in problems involving subsets, power sets, or managing flags (e.g., user permissions, feature flags in a software system like UdaanPath). For instance, if a user has `READ`, `WRITE`, and `DELETE` permissions, they might be represented by `001`, `010`, `100` bits. A user's total permissions could be `READ | WRITE = 011`. Checking if a user has `READ` permission is simply `(user_permissions & READ_MASK) != 0`.

• Optimizing Algorithms and Data Structures:

  Data structures like Fenwick Trees (Binary Indexed Trees) heavily rely on the `x & (-x)` trick for efficient prefix sum queries and updates. Bitwise operations are also fundamental in some hashing algorithms and low-level graphics programming.

• Data Compression and Network Protocols:

  Efficiently packing and unpacking data into minimum storage (e.g., variable-length codes in Huffman coding) or parsing network packet headers (where specific fields occupy exact bit ranges) extensively uses bitwise shifts and masks.

• Cryptographic Operations:

  Many cryptographic algorithms (e.g., AES, SHA) are built upon complex sequences of bitwise operations, XORs, and shifts due to their speed and properties of confusion and diffusion.

• Performance Critical Code:

  Replacing division/multiplication by powers of 2 with bit shifts, or using bitwise operations for boolean logic, can sometimes offer marginal but important performance gains in hot paths.

✅ Summary: The Power of the Smallest Unit

• Bit Manipulation involves direct operations on the binary representation of numbers (0s and 1s).
• Key bitwise operators: `&` (AND), `|` (OR), `^` (XOR), `~` (NOT), `<<` (Left Shift), `>>` (Right Shift).
• Mastering these operators allows for highly efficient code and elegant solutions to specific problems.
• Common patterns include: checking/setting/clearing/toggling bits, powers of two checks, counting set bits (Brian Kernighan's), getting the rightmost set bit, and various XOR tricks for finding unique elements or swapping variables.
• Applications are vast, spanning from low-level systems and network protocols to competitive programming and real-world optimizations in platforms like UdaanPath for permissions, feature flags, and data handling.

📤 Coming Next: Interview Problems from FAANG Companies

With a solid foundation in fundamental data structures, algorithms, and optimization techniques, we're now ready to put your skills to the test. Our next chapter will delve into common and challenging Interview Problems frequently asked by FAANG (Facebook, Apple, Amazon, Netflix, Google) and other top tech companies. We'll analyze problem-solving strategies, discuss optimal approaches, and gain insights into what interviewers look for.