Bit manipülasyonu: bir sayının 2'nin kuvveti olup olmadığını ve dizide tek kez geçen elemanı (Single Number) nasıl bulursunuz?

İki klasik hile: n & (n - 1) en sağdaki 1 bitini siler; x ^ x = 0 ve x ^ 0 = x olduğundan XOR çift tekrarları yok eder.

2'nin kuvveti mi?

2'nin kuvvetlerinde tam olarak bir bit 1'dir (8 = 1000). n - 1 o biti 0, altındakileri 1 yapar (0111); AND sonucu 0'dır.

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

print(is_power_of_two(16), is_power_of_two(18))  # True False

Single Number

Her eleman iki kez, biri bir kez geçiyorsa hepsini XOR'larız; çiftler birbirini sıfırlar.

from functools import reduce
from operator import xor

def single_number(nums):
    return reduce(xor, nums, 0)

print(single_number([4, 1, 2, 1, 2]))  # 4

O(n) zaman, O(1) bellek; hash set çözümü ise O(n) bellek ister.

1 bitlerini sayma (Hamming weight)

def count_bits(n):
    count = 0
    while n:
        n &= n - 1     # her turda bir 1 bitini sil
        count += 1
    return count

Sık kullanılan işlemler

n = 0b1000
n = n | (1 << 1)   # set   -> 0b1010
n = n & ~(1 << 3)  # clear -> 0b0010

Python'da tam sayılar sınırsız olduğu için negatif sayılarla kaydırma ve 32-bit taşma davranışı C/Java'dan farklıdır; gerekirse & 0xFFFFFFFF ile maskeleyin.