Bitwise Operations Fundamentals

1. Introduction: Under the Hood

Before you can master advanced bit manipulation tricks, you must understand the basic building blocks. Every piece of data in a computer—images, text, objects, and numbers—is ultimately stored as binary digits (bits): 0s and 1s.

A Bitwise Operation is a calculation that operates on these bits directly, rather than on the integer as a whole. While human math uses base-10 operations like +, -, *, /, computer hardware inherently uses logic gates like AND, OR, and NOT.

Understanding these operators gives you superpowers. You can compress arrays of booleans into a single integer, perform lightning-fast division, and solve complex algorithms using almost no memory.

2. Core Concept: The Six Bitwise Operators

In Java, all integers are 32-bit signed numbers. There are six primary bitwise operators:

1. AND (&): Compares two bits. Returns 1 if both are 1. Otherwise 0.
   • 1011 & 1101 = 1001
2. OR (|): Compares two bits. Returns 1 if at least one is 1. Otherwise 0.
   • 1010 | 1100 = 1110
3. XOR (^): Compares two bits. Returns 1 if they are different. Returns 0 if they are the same.
   • 1010 ^ 1100 = 0110
4. NOT (~): Unary operator. Flips every bit. 0 becomes 1, 1 becomes 0.
   • ~0101 = 1010
5. Left Shift (<<): Shifts bits to the left, filling the right side with 0s. This is mathematically equivalent to multiplying by $2^k$.
   • 3 << 2 (Shift 3 left by 2) $\rightarrow 3 \times 2^2 = 12$
6. Signed Right Shift (>>): Shifts bits to the right. Preserves the sign bit (leftmost bit). Mathematically equivalent to dividing by $2^k$.
   • 12 >> 2 (Shift 12 right by 2) $\rightarrow 12 / 2^2 = 3$
7. Unsigned Right Shift (>>>): Exclusive to Java. Shifts right, but forces the new left bits to be 0, regardless of whether the number was negative or positive.

3. Beginner Code Example: The 4 Core Bit Tasks

The absolute most common use of bitwise operations is modifying specific bits within an integer. We use a shifted 1 (like 1 << i) to target a specific position i.

public class BitBasics {
    
    // 1. Check if the i-th bit is set (is it a 1?)
    public static boolean checkBit(int num, int i) {
        // Shift 1 to the i-th position, and AND it with the number.
        // If the result is NOT 0, the bit was a 1.
        return (num & (1 << i)) != 0;
    }
    
    // 2. Set the i-th bit (force it to 1)
    public static int setBit(int num, int i) {
        // Shift 1 to the i-th position, and OR it. 
        // 1 OR anything is 1.
        return num | (1 << i);
    }
    
    // 3. Clear the i-th bit (force it to 0)
    public static int clearBit(int num, int i) {
        // Shift 1 to the i-th position, then INVERT it (so it's 111...0...111).
        // AND it with the number. 0 AND anything is 0.
        return num & ~(1 << i);
    }
    
    // 4. Toggle the i-th bit (flip it)
    public static int toggleBit(int num, int i) {
        // Shift 1 to the i-th position, and XOR it.
        // 1 XOR 1 is 0. 0 XOR 1 is 1.
        return num ^ (1 << i);
    }

    public static void main(String[] args) {
        int num = 10; // Binary: 1010
        System.out.println("Bit 1 is set? " + checkBit(num, 1)); // true
        System.out.println("Set bit 2: " + setBit(num, 2));      // 14 (1110)
        System.out.println("Clear bit 1: " + clearBit(num, 1));  // 8 (1000)
    }
}

Time & Space: All these operations execute in $O(1)$ time and take $O(1)$ space.

4. Intermediate Code Example: Odd/Even and Multiplication

You can use bitwise operations to replace standard arithmetic for minor performance gains in low-level systems.

Checking Odd or Even: An even number in binary ALWAYS ends in 0. An odd number ALWAYS ends in 1. Instead of doing num % 2 == 0 (modulo is actually a slow CPU instruction), you can do a bitwise AND with 1.

public class BitMath {
    public static boolean isOdd(int num) {
        // If the lowest bit is 1, the number is odd.
        return (num & 1) == 1;
    }
    
    public static boolean isEven(int num) {
        return (num & 1) == 0;
    }
    
    public static int multiplyByTwo(int num) {
        // Left shift by 1 multiplies by 2^1
        return num << 1;
    }
    
    public static int divideByTwo(int num) {
        // Right shift by 1 divides by 2^1
        return num >> 1;
    }
}

5. Advanced Code Example: Reverse Bits

Problem Statement: (LeetCode 190) Reverse bits of a given 32-bit unsigned integer.

The Insight: We can build the reversed number bit-by-bit. We extract the rightmost bit from the original number n, push it into our result, and then shift n to the right and result to the left. We repeat this 32 times.

public class ReverseBits {
    public static int reverseBits(int n) {
        int result = 0;
        
        for (int i = 0; i < 32; i++) {
            // 1. Shift the result left to make room for the new bit
            result <<= 1;
            
            // 2. Extract the rightmost bit of 'n' using (n & 1)
            // 3. Add it to the result using OR
            result |= (n & 1);
            
            // 4. Shift 'n' right to process the next bit.
            // MUST use Unsigned Right Shift (>>>) in Java to handle negative numbers!
            n >>>= 1;
        }
        
        return result;
    }
}

Complexity Analysis:

• Time Complexity: $O(1)$. The loop runs exactly 32 times, performing constant-time bitwise operations.
• Space Complexity: $O(1)$.

6. Common Mistakes Beginners Make

1. Using >> on Negative Numbers when Reversing/Extracting

   • The Mistake: Using the standard right shift n >>= 1 in algorithms that process all 32 bits (like the example above).
   • Why it's wrong: If n is negative, the highest bit is 1. The standard arithmetic shift >> preserves this sign by padding the left with 1s. If you do this in a while (n != 0) loop, the loop will never terminate because the number becomes a solid block of 1s (-1).
   • The Fix: In Java, ALWAYS use the unsigned right shift >>> when you want to treat the integer as raw binary data rather than a mathematical number.

2. Off-by-One in Bit Shifts

   • The Mistake: Shifting by 32 expecting it to clear the integer. int x = 5; x = x << 32;
   • Why it's wrong: Java masks the shift amount to the lower 5 bits (i.e., shift % 32). Shifting a 32-bit integer by 32 actually shifts it by 0! The number remains unchanged.

7. Interview Q&A

Q1: Why do competitive programmers write arr.length & 1 instead of arr.length % 2 != 0? Answer: It is a micro-optimization. The modulo operator requires division hardware circuitry, which takes multiple clock cycles. Bitwise AND & executes in a single cycle. While modern compilers usually optimize % 2 into & 1 under the hood anyway, writing & 1 guarantees the fastest possible execution.

Q2: How are negative numbers represented in binary? Answer: Java uses Two's Complement. To get the negative version of a binary number:

1. Invert all the bits (using NOT ~).
2. Add 1. For example, 5 is 0...0101. ~5 is 1...1010. Add 1 to get 1...1011, which is -5.

Q3: Can we add two numbers using only bitwise operators? Answer: Yes! (LeetCode 371). The XOR operator ^ acts as addition without carrying. The AND operator & acts as the carry bit. We can calculate a ^ b for the sum, and (a & b) << 1 for the carry, and loop until the carry is 0.

8. Practice Problems

1. Number of 1 Bits (LeetCode 191)
   • Goal: Count set bits using standard shifts.
2. Reverse Bits (LeetCode 190)
   • Goal: Master the unsigned right shift >>>.
3. Missing Number (LeetCode 268)
   • Hint: XOR ^ all indices, and XOR all values. The missing number will remain.

9. Summary

• Operators: & (AND), | (OR), ^ (XOR), ~ (NOT), << (Left Shift), >> (Signed Right Shift), >>> (Unsigned Right Shift).
• Modification: You can Check, Set, Clear, and Toggle specific bits using the (1 << i) masking trick.
• Java Specifics: Because Java does not have unsigned integers, >>> is critically important when extracting bits from potentially negative numbers.
• Optimization: Bitwise operations are mathematically equivalent to powers of 2, allowing for lightning-fast multiplication, division, and odd/even checks.