Bit Manipulation

In simple words

Computers store numbers as 0s and 1s. Bit operators let you work on those bits directly — very fast and often O(1) extra space.

& AND · | OR · ^ XOR (1 when bits differ) · ~ NOT · << left shift (×2) · >> right shift (÷2, keeps sign) · >>> unsigned right shift (Java-specific).

Key ideas

• (x & 1) == 1 → x is odd.
• x & (x - 1) removes the lowest 1-bit. x > 0 && (x & (x-1)) == 0 → x is a power of two.
• x ^ x = 0 and x ^ 0 = x → XOR of all numbers cancels the pairs (Single Number).
• Check bit i: (x >> i) & 1 · Set: x | (1 << i) · Clear: x & ~(1 << i) · Toggle: x ^ (1 << i).
• x & -x isolates the lowest set bit (used in Fenwick trees).
• Integer.bitCount(x) counts 1-bits. A mask from 0 to 2ⁿ−1 can represent every subset of n items.

Operations & cost

Java code

// Single Number: every number appears twice except one
int singleNumber(int[] nums) {
    int ans = 0;
    for (int x : nums) ans ^= x;   // pairs cancel out
    return ans;
}

// Count 1-bits (Brian Kernighan): runs once per set bit
int countOnes(int x) {
    int count = 0;
    while (x != 0) { x &= (x - 1); count++; }
    return count;
}

// All subsets using a bitmask
List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> cur = new ArrayList<>();
        for (int i = 0; i < n; i++)
            if (((mask >> i) & 1) == 1) cur.add(nums[i]);
        res.add(cur);
    }
    return res;
}

Interview traps to remember

• Precedence: x & 1 == 0 does not compile in Java. Write (x & 1) == 0.
• Shift distance: 1 << 32 is 1 for an int (only the last 5 bits of the shift are used). Use 1L << 32.
• >> vs >>>: -8 >> 1 is -4, but -8 >>> 1 is 2147483644. Use >>> for unsigned bits (Reverse Bits).
• Odd check: n % 2 == 1 fails for negatives because -3 % 2 is -1. Use (n & 1) == 1.
• Single Number (LeetCode 136): XOR everything: pairs cancel out, the unique number is left. O(n) time, O(1) space.

Spot it when

• 'Appears once / twice', 'without extra space'.
• n ≤ 20 and you need 'all subsets' → bitmask.
• 'Without using + or −' → XOR and carry.

Practice problems

Interview tip

★ Put parentheses around bit expressions. In Java == binds tighter than &, so x & 1 == 1 does not compile.