Maskeler ve bit bit düşünmek

Maske, yalnızca ilgilendiğin bitleri 1 olan bir sayıdır. 1 << k, yalnızca k'inci biti açık olan maskedir; n & (1 << k) sıfır değilse n'in k'inci biti 1'dir. Maskeyle bir sayının tek bir bitine bakar, onu açar (|) ya da ters çevirirsin (^).

1def is_power_of_two(n):
2    return n > 0 and (n & (n - 1)) == 0
3 
4lowest = n & -n

İki klasik: n & (n - 1) en sağdaki 1 bitini siler; ikinin kuvvetlerinde tek bir 1 biti olduğu için sonuç 0 çıkar. n & -n ise yalnızca en sağdaki 1 bitini bırakır. n > 0 kontrolü şarttır: 0 için de n & (n - 1) sıfırdır ama 0 ikinin kuvveti değildir.

Bazı problemler sayılara değil bit konumlarına göre düşününce kolaylaşır. Bütün çiftlerin kaç bitte ayrıştığını (Hamming mesafesi) saymak için her çifti denemene gerek yok: tek bir bit konumunda, o biti 1 olan c sayı ve 0 olan n - c sayı varsa, o konumda ayrışan çiftlerin sayısı c × (n - c)'dir. Bunu her konum için topla. Maske, sayıları iki gruba ayırmaya da yarar: tek kalan iki farklı sayının XOR'unda açık olan herhangi bir bit (örneğin x & -x), o ikisini ayıran bittir; sayıları o bite göre ikiye böl ve her grubu kendi içinde XOR'la.

Görevler