Bit Tricks Visualization for Coding Interviews

By Rahul Kumar · Senior Software Engineer · Updated May 2026 · Category: Bit Manipulation

popcount, is-power-of-2, lowest-set-bit, XOR swap, subset enumeration.

Concept

Bit manipulation tricks are the small, reusable idioms that let you treat a 32- or 64-bit integer as a compact set, a flags vector, a fixed-width counter, or a packed tuple. They matter because bitwise operations cost a single CPU cycle, branch-free, and because a single 64-bit word can replace a boolean[64] or a HashSet<Integer> of small keys. In interviews, bit tricks show up in subset enumeration for dynamic programming on sets, fast parity and popcount in hashing and Bloom filters, hardware-aligned flag fields in network protocols, packed color and pixel math, low-level data structure internals (e.g., Fenwick trees pulling the lowest set bit), bitmap-backed rank/select structures, and mask-based graph problems like the Traveling Salesman DP. Mastering the canonical set of tricks, popcount, isPowerOfTwo, lowest set bit, bit toggle/set/clear, XOR swap, and subset enumeration, unlocks clean, branch-free solutions and often turns an O(n) inner loop into a single instruction.

Bit Tricks — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive Bit Tricks visualization — animated algorithm, step-through, and live data-structure updates.

How it works

The atomic operations are AND, OR, XOR, NOT, and shifts. A single bit i of n is read by (n >> i) & 1. It is set by n | (1 << i), cleared by n & ~(1 << i), and toggled by n ^ (1 << i). Because x & -x isolates the lowest set bit (using two's complement, -x = ~x + 1), we can peel off set bits one at a time in loops. A number is a power of two when x != 0 and x & (x-1) == 0, because subtracting one flips the lowest set bit and every bit below it, so exactly one set bit leaves zero after AND. Popcount, the count of set bits, can be computed by Kernighan's loop (n &= n-1 until zero) in time proportional to the number of set bits, or in constant time on the JVM via Integer.bitCount, which compiles to the POPCNT instruction on modern CPUs. XOR gives a three-operation in-place swap without a temporary: a ^= b; b ^= a; a ^= b. Subset enumeration of a mask iterates every submask s of mask using s = (s - 1) & mask starting from s = mask, terminating when s becomes zero after the final iteration, which visits each subset exactly once in O(2^popcount(mask)) total across all submasks.

Implementation

BitTricks utility class

import java.util.*;

public final class BitTricks {
    private BitTricks() {}

    /** Kernighan's population count. */
    public static int popcount(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

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

    /** Returns the mask of the lowest set bit, or 0 if n == 0. */
    public static int lowestSetBit(int n) {
        return n & -n;
    }

    /** In-place XOR swap of pair[0] and pair[1]. */
    public static void xorSwap(int[] pair) {
        if (pair[0] == pair[1]) return; // guard: same slot aliasing
        pair[0] ^= pair[1];
        pair[1] ^= pair[0];
        pair[0] ^= pair[1];
    }

    public static int setBit(int n, int i)    { return n |  (1 << i); }
    public static int clearBit(int n, int i)  { return n & ~(1 << i); }
    public static int toggleBit(int n, int i) { return n ^  (1 << i); }

    /**
     * Enumerates every non-empty submask of the given mask, then adds 0.
     * Standard SOS/DP-over-subsets iteration order (descending).
     */
    public static List<Integer> enumerateSubsets(int mask) {
        List<Integer> out = new ArrayList<>();
        int s = mask;
        while (true) {
            out.add(s);
            if (s == 0) break;
            s = (s - 1) & mask;
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(popcount(0b10110));      // 3
        System.out.println(isPowerOfTwo(1024));     // true
        System.out.println(lowestSetBit(0b10100));  // 4
        int[] p = {7, 9};
        xorSwap(p);
        System.out.println(Arrays.toString(p));     // [9, 7]
        System.out.println(enumerateSubsets(0b101));
    }
}

Complexity

Time: O(1) per op
Space: O(1)

Common pitfalls

XOR swap breaks when both references alias the same memory location; always guard or just use a temporary.
1 << 31 is negative in a signed int; use 1L << i when i can reach or exceed 31.
x & (x-1) == 0 returns true for x == 0, so you must check x > 0 to correctly test power-of-two.
Subset enumeration via (s - 1) & mask must emit s == 0 as the last submask and then break; forgetting the break creates an infinite loop.

Key design decisions & trade-offs

Manual popcount vs Integer.bitCount — Chosen: Use Integer.bitCount in production. JIT lowers it to hardware POPCNT; manual loops are only useful when sparseness guarantees faster early exit.
XOR swap vs temporary variable — Chosen: Temporary variable. XOR swap is a party trick: it is no faster on modern CPUs and breaks on aliasing, which costs more than it saves.

Practice problems

Interview follow-ups

Use lowestSetBit to walk a Fenwick tree index in O(log n) per update/query.
Implement a Gray-code iteration that flips one bit per step for energy-aware circuit testing or constant-weight enumeration.
Extend to 64-bit operations using long, Long.bitCount, and 1L << i for masks wider than 31 bits.

Why it matters

Bit Tricks is a core part of the Bit Manipulation toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".