Master DSA: Bitwise Operations (All Operators & Patterns)

Bitwise operations are operations that directly manipulate the binary representation of integers at the level of individual bits (0s and 1s). Because computers natively store and process data in binary, bitwise operations are incredibly fast and execution-efficient, making them indispensable for low-level programming, performance optimization, graphics, and algorithmic problem-solving.

1. Understanding Binary Representation

To perform bitwise operations, we must first understand how integers are represented in binary (base-2). Any decimal integer can be decomposed into a sum of powers of 2.

Mathematical Conversion

For an 8-bit binary number, the positions represent powers of 2 from right to left:

Example: Converting Decimal 5 to Binary

The binary representation of $5$ is 0101 (using 4 bits):

Example: Converting Decimal 3 to Binary

The binary representation of $3$ is 0011 (using 4 bits):

2. Core Bitwise Operators & Truth Tables

Bitwise operators compare the corresponding bits of two operands to produce a new value. The table below synthesizes the behavior of the five primary bitwise operators:

Fundamental XOR Properties

The XOR (^) operator has unique algebraic properties that make it highly useful in algorithm design:

1. Self-Cancellation: $x \oplus x = 0$ (Any number XORed with itself results in 0).
2. Identity: $x \oplus 0 = x$ (Any number XORed with 0 remains unchanged).
3. Commutativity & Associativity: $a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b$.

3. Step-by-Step Operator Walkthroughs

Let us evaluate how these operators behave using the numbers $5$ ($0101_2$) and $3$ ($0011_2$).

Bitwise AND (&)

Result: $5 \ \& \ 3 = 1$

Bitwise OR (|)

Result: $5 \ \vert \ 3 = 7$

Bitwise XOR (^)

Result: $5 \ \wedge \ 3 = 6$

4. Shift Operators: Left Shift (<<) and Right Shift (>>)

Shift operators move the bit pattern of a number to the left or right by a specified number of positions.

Left Shift (<<)

The left shift operator shifts bits to the left and fills empty spaces on the right with 0. Shifting a binary number left by $n$ positions is mathematically equivalent to multiplying the number by $2^n$.

Right Shift (>>)

The right shift operator shifts bits to the right. The bits shifted past the rightmost position are discarded. Shifting a number right by $n$ positions is mathematically equivalent to performing integer division by $2^n$.

5. Practical Bitwise Tricks

Trick 1: Checking Even or Odd

Instead of using the modulo operator (n % 2 == 1), we can inspect the least significant bit (LSB). If the LSB is 1, the number is odd. If it is 0, the number is even. We isolate this bit using n & 1.

Code Implementation

public static boolean isOdd(int n) {
    return (n & 1) == 1;
}

Trick 2: Fast Multiplication and Division by Powers of Two

• Multiply by 2: n << 1
• Divide by 2: n >> 1

6. Swapping Two Numbers Without a Temporary Variable

Using the self-canceling properties of XOR, we can swap two variables in-place without allocating any auxiliary memory.

The Algorithm

a = a ^ b;  // Step 1
b = b ^ a;  // Step 2
a = a ^ b;  // Step 3

Mathematical Proof

Let the initial values of the variables be $A$ and $B$.

Step 1: a = A ^ B
        The variable 'a' now holds the combined XOR state of both numbers.

Step 2: b = B ^ a
        Substitute the value of 'a' from Step 1:
        b = B ^ (A ^ B)
        Using commutativity: b = (B ^ B) ^ A
        Since B ^ B = 0:    b = 0 ^ A = A
        The variable 'b' now holds the original value of 'a' (A).

Step 3: a = a ^ b
        Substitute the current values of 'a' (A ^ B) and 'b' (A):
        a = (A ^ B) ^ A
        Using commutativity: a = (A ^ A) ^ B
        Since A ^ A = 0:    a = 0 ^ B = B
        The variable 'a' now holds the original value of 'b' (B).

7. Querying and Modifying the $i$-th Bit

In bit manipulation, we often need to inspect or modify a specific bit at index $i$ (0-indexed, starting from the right).

1. Get the $i$-th Bit

To check if the $i$-th bit of a number $n$ is set (1) or unset (0), we construct a bitmask where only the $i$-th bit is 1. We do this using 1 << i, and then perform a bitwise AND.

Code Implementation

public static int getBit(int n, int i) {
    return ((n & (1 << i)) != 0) ? 1 : 0;
}

2. Set the $i$-th Bit

To "set" a bit means to force its value to be 1, regardless of whether it was 0 or 1 originally. We use a bitmask with the $i$-th bit set to 1 and perform a bitwise OR (|).

Code Implementation

public static int setBit(int n, int i) {
    return n | (1 << i);
}

8. Checking if a Number is a Power of Two

A number that is a power of two has exactly one set bit in its binary representation.

• $2 = 0010_2$
• $4 = 0100_2$
• $8 = 1000_2$

The $n \ \& \ (n - 1)$ Trick

Subtracting 1 from a power of two flips the single set bit to 0, and flips all subsequent trailing 0s to 1s.

For example, if $n = 8$ ($1000_2$), then $n - 1 = 7$ ($0111_2$).

If we perform a bitwise AND between $n$ and $n - 1$, the result will be exactly 0 if and only if $n$ is a power of two (and $n > 0$).

Code Implementation

public static boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

9. Counting Set Bits (Brian Kernighan's Algorithm)

The naive way to count set bits is to iterate through all 32 bits of an integer and check each one. However, Brian Kernighan’s Algorithm optimizes this by only looping as many times as there are set bits.

Intuition

The expression n & (n - 1) clears the rightmost set bit of $n$. By repeatedly applying this operation and counting how many times we can do it before $n$ becomes 0, we get the exact count of set bits.

Workflow:
Count set bits in n = 13 (1101_2)

Iteration 1:
  n     = 13  (1 1 0 1)
  n - 1 = 12  (1 1 0 0)
  n = n & (n - 1) => 1101 & 1100 = 1100 (12)
  Count = 1

Iteration 2:
  n     = 12  (1 1 0 0)
  n - 1 = 11  (1 0 1 1)
  n = n & (n - 1) => 1100 & 1011 = 1000 (8)
  Count = 2

Iteration 3:
  n     = 8   (1 0 0 0)
  n - 1 = 7   (0 1 1 1)
  n = n & (n - 1) => 1000 & 0111 = 0000 (0)
  Count = 3

n is now 0. Stop. Total set bits = 3.

Code Implementation

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

10. Finding the Single Non-Repeating Element

Problem Statement

Given an array of integers where every element appears exactly twice except for one element which appears once, find that single non-repeating element in $O(N)$ time complexity and $O(1)$ space complexity.

Intuition

Because XOR is commutative ($a \wedge b = b \wedge a$) and self-canceling ($a \wedge a = 0$), XORing all elements in the array will cancel out all duplicate pairs, leaving only the unique element.

Array: [1, 1, 2, 4, 4, 3, 3]

XOR Accumulation:
Result = 1 ^ 1 ^ 2 ^ 4 ^ 4 ^ 3 ^ 3
       = (1 ^ 1) ^ (4 ^ 4) ^ (3 ^ 3) ^ 2
       = 0 ^ 0 ^ 0 ^ 2
       = 2

Code Implementation

public static int findSingleElement(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

Summary and Key Takeaways

• Direct Manipulation: Bitwise operations work directly on the binary representation of integers, making them highly performant.
• Even/Odd Check: Use (n & 1) == 0 to check for even numbers and (n & 1) == 1 for odd numbers.
• Bit Shifts: Left shifting (<< n) multiplies an integer by $2^n$, while right shifting (>> n) divides it by $2^n$.
• XOR Swap: You can swap two variables without extra space using three consecutive XOR operations: a ^= b; b ^= a; a ^= b;.
• Bit Masking: Use 1 << i to create a mask with a single set bit at index $i$. Combine this with & to get a bit, or | to set a bit.
• Power of Two: A positive integer n is a power of two if and only if (n & (n - 1)) == 0.
• Brian Kernighan's Algorithm: Count set bits efficiently in $O(K)$ time (where $K$ is the number of set bits) by repeatedly clearing the rightmost set bit with n & (n - 1).
• Duplicate Cancellation: XORing a series of numbers cancels out identical pairs, which is highly useful for finding unique elements in arrays.