Pattern Guide
Bitset & Bit-Parallel Algorithms
"Process 64 elements at once with uint64 bitmasks. DP optimized by 64x."
Bitset operations process 64 elements simultaneously using JavaScript's 32-bit integers (or BigInt for 64-bit). Core use: optimize O(n²/64) DP problems (reachability, subset intersection), store and query boolean arrays faster. Applications: boolean DP optimization, subset matching, string pattern matching, and matrix multiplication over GF(2).
13 min readdp problems →
Problems you can solve with this pattern
3 problems · click any to start solving
Bitset class for subset DP optimization
class Bitset {
constructor(n) {
this.n = n;
this.words = new Int32Array(Math.ceil(n / 32));
}
set(i) { this.words[i >> 5] |= 1 << (i & 31); }
get(i) { return (this.words[i >> 5] >> (i & 31)) & 1; }
orWith(other) { for (let i = 0; i < this.words.length; i++) this.words[i] |= other.words[i]; }
shiftOrWith(other, shift) {
// this |= (other << shift)
const wordShift = shift >> 5, bitShift = shift & 31;
for (let i = this.words.length - 1; i >= wordShift; i--) {
this.words[i] |= (other.words[i - wordShift] << bitShift);
if (bitShift && i > wordShift) this.words[i] |= (other.words[i - wordShift - 1] >>> (32 - bitShift));
}
}
count() { let c = 0; for (const w of this.words) c += popcount32(w); return c; }
test(i) { return this.get(i) === 1; }
}
function popcount32(x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0f0f0f0f;
return (x * 0x01010101) >>> 24;
}
// Subset-sum DP with bitset: "can we make sum exactly k?"
// Standard O(n*k), bitset O(n*k/32)
function subsetSumBitset(nums, target) {
// dp = bitset where bit k is set if sum k is achievable
let dp = new Int32Array(Math.ceil((target + 1) / 32));
dp[0] = 1; // sum 0 is achievable
for (const num of nums) {
// dp |= (dp << num)
const shift = num;
const ws = shift >> 5, bs = shift & 31;
for (let i = dp.length - 1; i >= ws; i--) {
dp[i] |= dp[i - ws] << bs;
if (bs && i > ws) dp[i] |= dp[i - ws - 1] >>> (32 - bs);
}
}
return !!((dp[target >> 5] >> (target & 31)) & 1);
}JavaScript processes 32 bits at a time with bitwise operations. Pack boolean arrays into integer arrays where each int holds 32 flags. AND/OR/XOR on integers processes 32 elements simultaneously. For a DP where dp[i] is a set of reachable values, OR with shifted dp gives "can reach previous value + new element." O(n²/32) instead of O(n²).
Bitset class for subset DP optimization
class Bitset {
constructor(n) {
this.n = n;
this.words = new Int32Array(Math.ceil(n / 32));
}
set(i) { this.words[i >> 5] |= 1 << (i & 31); }
get(i) { return (this.words[i >> 5] >> (i & 31)) & 1; }
orWith(other) { for (let i = 0; i < this.words.length; i++) this.words[i] |= other.words[i]; }
shiftOrWith(other, shift) {
// this |= (other << shift)
const wordShift = shift >> 5, bitShift = shift & 31;
for (let i = this.words.length - 1; i >= wordShift; i--) {
this.words[i] |= (other.words[i - wordShift] << bitShift);
if (bitShift && i > wordShift) this.words[i] |= (other.words[i - wordShift - 1] >>> (32 - bitShift));
}
}
count() { let c = 0; for (const w of this.words) c += popcount32(w); return c; }
test(i) { return this.get(i) === 1; }
}
function popcount32(x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0f0f0f0f;
return (x * 0x01010101) >>> 24;
}
// Subset-sum DP with bitset: "can we make sum exactly k?"
// Standard O(n*k), bitset O(n*k/32)
function subsetSumBitset(nums, target) {
// dp = bitset where bit k is set if sum k is achievable
let dp = new Int32Array(Math.ceil((target + 1) / 32));
dp[0] = 1; // sum 0 is achievable
for (const num of nums) {
// dp |= (dp << num)
const shift = num;
const ws = shift >> 5, bs = shift & 31;
for (let i = dp.length - 1; i >= ws; i--) {
dp[i] |= dp[i - ws] << bs;
if (bs && i > ws) dp[i] |= dp[i - ws - 1] >>> (32 - bs);
}
}
return !!((dp[target >> 5] >> (target & 31)) & 1);
}Bitset DP optimization:
- Classic: subset-sum dp[sum] = boolean, O(n × target)
- Bitset: pack 32 dp states into one int, O(n × target/32)
- BigInt in JS: 64-bit words, but slower than Int32Array
- For competitive programming: use Int32Array for speed
Key operations:
- dp |= (dp << num): "can reach old sum + num"
- dp & other: elements in both sets
- popcount: count set bits (elements in set)
Matrix multiplication over GF(2): C[i][j] = OR of (A[i][k] AND B[k][j]). Represent each row as a bitset. Row-by-column multiplication: C_row |= A_row & B_col for each set bit. O(n³/32) instead of O(n³).
- Classic: subset-sum dp[sum] = boolean, O(n × target)
- Bitset: pack 32 dp states into one int, O(n × target/32)
- BigInt in JS: 64-bit words, but slower than Int32Array
- For competitive programming: use Int32Array for speed
Key operations:
- dp |= (dp << num): "can reach old sum + num"
- dp & other: elements in both sets
- popcount: count set bits (elements in set)
Matrix multiplication over GF(2): C[i][j] = OR of (A[i][k] AND B[k][j]). Represent each row as a bitset. Row-by-column multiplication: C_row |= A_row & B_col for each set bit. O(n³/32) instead of O(n³).