templates · Bits, range queries & string matching

Bit tricks

  • "Count the 1 bits", "is it a power of two", "reverse the bits"
  • Every value appears twice except one: XOR cancels the pairs
  • A small set (n ≤ 20) stored as one int, with bit i meaning "element i is in"

Bit tricks (shift, mask, lowest set bit)XOR cancellationBitmask as a set

the one rule

The invariant

A Java int is 32 bits in two's complement: -x == ~x + 1, and bit 31 is the sign bit.

write it from memory

The template

read, set, clear, flip bit i

javajava.util.*
/** Bit i of x (0 = lowest). Works for negative x too. */static boolean isBitSet(int x, int i) {    return ((x >> i) & 1) == 1;} static int setBit(int x, int i) {    return x | (1 << i);                              // turn bit i on} static int clearBit(int x, int i) {    return x & ~(1 << i);                             // turn bit i off} static int toggleBit(int x, int i) {    return x ^ (1 << i);                              // flip bit i}

1 << i is a number with only bit i set. OR turns it on, AND with ~ turns it off, XOR flips it.

fill in the blanks — only these lines change per problem

  1. line 3Which bit you look at, and whether you shift x right or 1 left.

the lowest set bit

javajava.util.*
/** Only the lowest set bit of x: 12 (1100) → 4 (0100). */static int lowestSetBit(int x) {    return x & -x;                                    // -x = ~x + 1 keeps only that bit} /** How many bits are 1. Each step removes the lowest one. */static int popCount(int x) {    int count = 0;    while (x != 0) {                                  // not x > 0: negatives have bit 31 set        x &= x - 1;                                   // drop the lowest set bit        count++;    }    return count;} /** A power of two has exactly one bit set. */static boolean isPowerOfTwo(int x) {    return x > 0 && (x & (x - 1)) == 0;               // x > 0 rules out 0 and Integer.MIN_VALUE}

x & (x - 1) drops the lowest 1 bit; x & -x keeps only it. Most bit problems use one of these two.

fill in the blanks — only these lines change per problem

  1. line 10What you do per set bit: count it, or record its position.
  2. line 18The power-of-two test. Keep the x > 0 part.

XOR cancellation

javajava.util.*
/** Every value appears twice except one: pairs cancel, a ^ a = 0 and a ^ 0 = a. */static int singleNumber(int[] nums) {    int x = 0;    for (int v : nums) x ^= v;    return x;}

fill in the blanks — only these lines change per problem

  1. line 4What you XOR together: the values, or values and indexes (missing number).

every subset of a mask

javajava.util.*
/** Every subset of the set `mask` (bit i = element i), biggest first, ending with the empty set. */static List<Integer> submasks(int mask) {    List<Integer> out = new ArrayList<>();    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) out.add(sub); // next smaller subset    out.add(0);                                       // the empty set is a subset too    return out;}

(sub - 1) & mask jumps straight to the next smaller subset, skipping numbers that have bits outside the mask.

fill in the blanks — only these lines change per problem

  1. line 4What you do with each subset: often a DP step like dp[mask] = Math.min(dp[mask], dp[sub] + cost).

complexity

What it costs

time O(1) per trick · O(set bits) for popcount · O(2ᵏ) for submasks
Each trick is one or two CPU operations. Popcount loops once per 1 bit. A mask with k bits has 2ᵏ subsets.
space O(1)
Only a few int variables, apart from the list of submasks.

watch out

Common bugs

  • Writing x & 1 == 1. In Java == binds tighter than &, so it does not even compile. Add brackets: (x & 1) == 1.
  • Looping while (x > 0) on a negative number. It never runs; use x != 0, and >>> when you shift right.
  • Writing 1 << i when you need 64 bits. Use 1L << i, or the bit wraps around.

use it

Practise it on

learn it properly