Binary Digit DP

May 2026 · 28 min read

Digit DP usually means decimal digits, but the same tight-flag idea works over bits. Binary digit DP is natural when constraints involve popcount, XOR, AND, OR, or bitwise comparisons under an upper bound.

Count Numbers by Popcount

Count values x <= N with exactly K set bits by scanning bits from high to low.

long long dp[64][64][2];

long long solve(int pos, int ones, bool tight, vector<int>& bits) {
    if (ones < 0) return 0;
    if (pos == (int)bits.size()) return ones == 0;
    long long& memo = dp[pos][ones][tight];
    if (memo != -1) return memo;
    memo = 0;
    int limit = tight ? bits[pos] : 1;
    for (int bit = 0; bit <= limit; ++bit) {
        memo += solve(pos + 1, ones - bit, tight && bit == limit, bits);
    }
    return memo;
}

Pair DP with XOR Constraints

For pairs (a, b), each bit has four possibilities: 00, 01, 10, 11. Track tight flags for both numbers and any relation you care about.

// Count pairs a <= A, b <= B, and (a ^ b) <= X.
state = (pos, tightA, tightB, tightX);
try abit in {0,1};
try bbit in {0,1};
xbit = abit ^ bbit;

AND/OR Constraints

AND and OR constraints are also per-bit:

• (a & b) bit is 1 only for pair 11.
• (a | b) bit is 0 only for pair 00.
• (a ^ b) bit is 1 for 01 or 10.

Range to Prefix

As with normal digit DP, convert range queries to prefix queries:

answer(L, R) = count(0..R) - count(0..L-1)

Combining with Mask State

If the property depends on seen categories, residues, or automaton states, add them to the DP state. Keep the mask small; binary digit DP already has many tight flags.

Practice Problems

• LeetCode 338 - Counting Bits warmup understand popcount recurrence.
• LeetCode - Nth Smallest Integer With K One Bits kth walk combinatorics over binary digits.
• Codeforces 431D - Random Task popcount prefix count by number of ones.
• LeetCode - Bitwise constraints bit feasibility pair binary reasoning with DP.