資料結構

1class Bitset {
2  words: bigint[];
3 
4  constructor(size: number) {
5    this.words = new Array(Math.ceil(size / 64)).fill(0n);
6  }
7 
8  add(i: number): void {
9    this.words[i >> 6] |= 1n << BigInt(i & 63);
10  }
11 
12  remove(i: number): void {
13    this.words[i >> 6] &= ~(1n << BigInt(i & 63));
14  }
15 
16  has(i: number): boolean {
17    return ((this.words[i >> 6] >> BigInt(i & 63)) & 1n) === 1n;
18  }
19 
20  combine(other: Bitset, op: "and" | "or" | "xor" | "andNot"): Bitset {
21    const out = new Bitset(this.words.length * 64);
22    for (let w = 0; w < this.words.length; w++) {
23      const a = this.words[w], b = other.words[w];
24      if (op === "and") out.words[w] = a & b;
25      else if (op === "or") out.words[w] = a | b;
26      else if (op === "xor") out.words[w] = a ^ b;
27      else out.words[w] = a & ~b;
28    }
29    return out;
30  }
31 
32  // Kernighan: w & (w - 1) clears the lowest set bit, once per member.
33  count(): number {
34    let total = 0;
35    for (let w of this.words) {
36      while (w !== 0n) { w &= w - 1n; total++; }
37    }
38    return total;
39  }
40}
41 
42const lowestBit = (x: number) => x & -x;
43const clearLowest = (x: number) => x & (x - 1);
44 
45// Every non-empty subset of mask's bits, largest first.
46function submasks(mask: number): number[] {
47  const out: number[] = [];
48  for (let s = mask; s > 0; s = (s - 1) & mask) out.push(s);
49  return out;
50}