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ş.

Yardımcı kimlikler

Python int’leri sınırsızdır. ~n -n - 1’dir, sabit genişlikte bit çevirme değildir. >> aritmetik kaydırmadır: 2**k ile alta böler, negatifler dahil. n >> 31 ile kurulan maske 32-bit int varsayar. Bit i sıfır tabanlıdır (i = 0 en düşük anlamlı bittir).

def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

def lowest_set_bit(n: int) -> int:
    return n & -n

def clear_lowest_set_bit(n: int) -> int:
    return n & (n - 1)

def get_bit(n: int, i: int) -> int:
    return (n >> i) & 1

def set_bit(n: int, i: int) -> int:
    return n | (1 << i)

def clear_bit(n: int, i: int) -> int:
    return n & ~(1 << i)

def toggle_bit(n: int, i: int) -> int:
    return n ^ (1 << i)

def popcount(n: int) -> int:
    """Brian Kernighan. n >= 0 only.

    A negative Python int has an infinite string of sign bits, so the
    loop never finishes. For Python 3.10+, n.bit_count() counts the bits
    of abs(n) and accepts negatives.
    """
    if n < 0:
        raise ValueError("popcount loop requires n >= 0")
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

def single_number(nums: list[int]) -> int:
    """Every value appears twice, except one."""
    acc = 0
    for value in nums:
        acc ^= value
    return acc

def opposite_signs(x: int, y: int) -> bool:
    """True when one value is negative and the other is not.

    Zero counts as non-negative, so zero and a negative are opposite.
    """
    return (x ^ y) < 0

def sign(n: int) -> int:
    return (n > 0) - (n < 0)

def submasks(mask: int):
    """Every bitmask contained in mask, mask itself included."""
    sub = mask
    while True:
        yield sub
        if sub == 0:
            break
        sub = (sub - 1) & mask

a ^ a == 0
a ^ 0 == a
a ^ b == b ^ a
(a ^ b) ^ c == a ^ (b ^ c)
~n == -n - 1

Takas: a, b = b, a. XOR-takas (a ^= b; b ^= a; a ^= b) iki ayrı nesne ister. Aynı değişkene iki kez uygulanırsa sıfırlar.

INT32_MAX = 2**31 - 1, INT32_MIN = -2**31. Bunlar Java ve sabit int dillerde mülakatların varsaydığı 32-bit sınırlardır. Python’da limit değildir. 0xAAAAAAAA ve 0x55555555 32-bit almaşık maskelerdir; Python’da o genişlikte pozitif değerlerdir.

k sola kaydırma 2**k ile çarpar. Sağa kaydırma 2**k ile alta böler. Python’da (-3 >> 1) == -2.

Sabit genişlik: TypeScript ve C#

TypeScript bitwise operatörleri önce number’ı int32’ye çevirir. C# int zaten int32’dir. İkisinde de 1 << 31 işaret bitidir, değer -2147483648. Pozitif kalması gereken kaydırma bigint (1n << 31n) veya C# long (1L << 31) kullanır.

>> aritmetik kaydırmadır. >>> mantıksal kaydırmadır, sıfır doldurur. C# 11’den beri >>> vardır. Bu reponun test ettiği .NET 10’da da vardır.

İki’nin kuvveti testi n > 0 && (n & (n - 1)) == 0 C# int için geçerlidir; TypeScript number için yalnızca n 1 .. 2**31 - 1 aralığında bir tamsayıyken. Ötesinde bitwise operatörler düşük 32 bite bakar. 2**32 + 1 iki’nin kuvveti değildir, int32 testi öyle der.

long üzerinde 1L << 31 pozitiftir ve aynı test kabul eder. int.MinValue tek set bittir ve n > 0’ı geçemez, bu yüzden int testi reddeder.

Bu sitedeki dil kartları (/tr/python, /tr/typescript, /tr/csharp) geri kalan mülakat deyimlerini tutar.

/** 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;
}