Bit Manipülasyonu

Nasıl düşünülür

XOR kendi tersidir: çiftler kaybolur. n & (n-1) en düşük set bit’i düşürür. n & -n onu izole eder. Bitmask’ler küçük evren (n ≤ 20) alt kümelerini DP veya numaralandırma için kodlar.

Şablon şekilleri

Şekil	Temel hamle	Notlar
XOR fold	x ^= a[i]	Tek sayı
En düşük bit	n & -n / n & (n-1)	Say / kaldır
Maske DP	mask in 0..1<<n	Alt kümeler

Karmaşıklık temeli

Sıkça O(n) kelime işlemi veya alt küme DP için O(2^n · n).

Şablondan probleme

1. Problemi bir bitwise kimliğe eşle.
2. Dile özgü int boyutuna dikkat et.
3. Kimlik netse O(n) taramaya bit hilelerini tercih et.
4. Maskeler: gerekirse alt maskeleri dikkat dolaş.

/** Bit template: single number via XOR fold. */
export function singleNumber(nums: number[]): number {
  let x = 0;
  for (const v of nums) x ^= v;
  return x;
}

/** Bit template: single number via XOR fold. */
export function singleNumber(nums: number[]): number {
  let x = 0;
  for (const v of nums) x ^= v;
  return x;
}