Bit Manipülasyonu

Bilgisayarın belleğindeki her şey sonunda 0 ve 1'lerden oluşur: bir tamsayı, bir harf, bir pikselin rengi, bir dosyanın izinleri. Çoğu zaman bu bitleri görmezsin; int ile toplama yapar, string ile metin işlersin. Ama bazı problemlerde bitlere doğrudan dokunmak hem çok daha hızlı hem de çok daha zarif çözümler verir.

Bit manipülasyonu gerçek hayatta her yerdedir. Unix'teki chmod 755 komutunda her rakam üç bitlik bir izin maskesidir. Ağ yöneticileri 255.255.255.0 gibi alt ağ maskeleriyle bir IP adresinin hangi kısmının ağa ait olduğunu bitsel VE ile bulur. Satranç motorları tahtayı 64 bitlik tamsayılarla temsil eder, Go'nun standart kütüphanesi os.O_CREATE|os.O_WRONLY gibi bayrakları bitlerle birleştirir. Fenwick ağacı ve Bloom filtresi gibi veri yapıları da bit hilelerinin üzerine kuruludur.

Mülakatlarda ve programlama yarışmalarında da bu konu sık karşına çıkar: "Dizide tek kez geçen sayıyı ek bellek kullanmadan bul", "Bir sayının 2'nin kuvveti olup olmadığını tek satırda kontrol et", "20 elemanlı bir kümenin bütün alt kümelerini gez" gibi.

Bu dersin sonunda ikilik ve onaltılık gösterimi rahatça okuyabilecek, negatif sayıların ikiye tümleyen ile nasıl tutulduğunu ve taşmanın neden "sarmaladığını" açıklayabileceksin. Go'nun bit operatörlerini ve kaydırma kurallarını doğru kullanacak, x & (x-1) ve XOR hilelerini, math/bits paketini ve bitmask ile alt küme gezmeyi problem çözerken uygulayabileceksin.

İkili sayı sistemi

Basamak değerleri: onluk, ikilik ve onaltılık

Onluk sistemde her basamak 10'un bir kuvvetidir: 352 = 3·100 + 5·10 + 2·1. İkilik (binary) sistemde taban 2'dir ve her basamak, yani her bit, 2'nin bir kuvvetini temsil eder:

bit konumu:    7    6    5    4    3    2    1    0
değeri:      128   64   32   16    8    4    2    1
             ---------------------------------------
 13 =          0    0    0    0    1    1    0    1   →  8 + 4 + 1 = 13
200 =          1    1    0    0    1    0    0    0   →  128 + 64 + 8 = 200

En sağdaki bite en düşük anlamlı bit (least significant bit, LSB), en soldakine en yüksek anlamlı bit (most significant bit, MSB) denir. Bu derste bitleri hep sağdan ve 0'dan başlayarak numaralandıracağız: "0. bit", "3. bit" gibi.

İkilik sayılar uzadıkça okumak zorlaşır. Burada onaltılık (hexadecimal) sistem imdada yetişir: 16 = 2⁴ olduğu için her onaltılık basamak tam olarak 4 bite karşılık gelir. Bu yüzden bir bayt (8 bit) her zaman iki onaltılık basamakla yazılır.

Bu tabloyu ezberlemen gerekmez ama birkaç satırını tanımak çok işe yarar. F dört bitin hepsinin açık olduğunu, 8 yalnızca en yüksek bitin açık olduğunu söyler. Böylece 0xFF = 1111 1111 = 255 ve 0x80 = 1000 0000 = 128 gibi değerleri anında çözebilirsin.

Go'da ikilik ve onaltılık sayılar

Go'da sayı sabitlerini doğrudan ikilik (0b), sekizlik (0o) ya da onaltılık (0x) yazabilir, uzun sayıları _ ile gruplayabilirsin. Yazdırırken fmt fiilleri devreye girer: %b ikilik, %x ve %X onaltılık, %o sekizlik gösterim üretir. %08b biçimindeki 8 genişliği, 0 bayrağı ise boşlukları sıfırla doldurmayı belirtir. Bitleri hizalı görmek için bu derste sürekli bu biçimi kullanacağız. # bayrağı da 0b veya 0x önekini ekler.

package main

import (
	"fmt"
	"strconv"
)

func main() {
	x := 0b1101      // ikilik sabit
	y := 0x2F        // onaltılık sabit
	z := 0o17        // sekizlik sabit
	big := 1_000_000 // okunabilirlik için alt çizgi

	fmt.Println(x, y, z, big)

	fmt.Printf("%b\n", 13)   // ikilik
	fmt.Printf("%08b\n", 13) // 8 haneye sıfırla tamamla
	fmt.Printf("%#b\n", 13)  // 0b önekiyle
	fmt.Printf("%x %X %#x\n", 255, 255, 255)
	fmt.Printf("%016b\n", 0xBEEF)

	// strconv ile 2..36 arasındaki herhangi bir tabana dönüştür
	fmt.Println(strconv.FormatInt(200, 2), strconv.FormatInt(200, 16))
	n, err := strconv.ParseInt("11001000", 2, 64)
	fmt.Println(n, err)
}

13 47 15 1000000
1101
00001101
0b1101
ff FF 0xff
1011111011101111
11001000 c8
200 <nil>

0xBEEF çıktısına bak: B E E F dört onaltılık basamak, 1011 1110 1110 1111 dört dörtlük bit grubu. Onaltılık gösterimin bu kadar yaygın olmasının sebebi bu birebir eşleşmedir.

İşaretsiz ve işaretli tamsayılar

Go'da tamsayı tipleri iki aileye ayrılır. İşaretsiz (unsigned) tipler (uint8, uint16, uint32, uint64, uint) yalnızca sıfırı ve pozitif sayıları tutar; n bitlik işaretsiz bir tip 0 ile 2ⁿ − 1 arasındaki değerleri temsil eder. İşaretli (signed) tipler (int8 … int64, int) negatif sayıları da tutar ve aynı 2ⁿ desen ikiye bölünür: aralık −2ⁿ⁻¹ ile 2ⁿ⁻¹ − 1 arasıdır.

int ve uint 64 bitlik platformlarda 64, 32 bitlik platformlarda 32 bittir. Bit sayısının önemli olduğu yerlerde (bit kümeleri, hash hesapları, dosya biçimleri) boyutu açıkça belirten uint64 veya uint32 gibi tipleri tercih et. Tiplerin genel tanıtımını Değişkenler, Sabitler ve Tipler dersinde bulabilirsin.

Burada kritik bir fikir var: bitler aynı kalır, yorum değişir. 11111011 bit dizisi uint8 olarak okunduğunda 251, int8 olarak okunduğunda −5 demektir. Peki neden −5? Cevap ikiye tümleyende.

İkiye tümleyen (two's complement)

Negatif sayıları temsil etmenin ilk akla gelen yolu, en yüksek biti işarete ayırmaktır: 1000 0101 = −5. Ne var ki bu yaklaşımda iki ayrı sıfır oluşur (0000 0000 ve 1000 0000) ve toplama devresinin işaretleri ayrıca ele alması gerekir. Günümüz işlemcileri bunun yerine ikiye tümleyen (two's complement) gösterimini kullanır; Go dil spesifikasyonu da tamsayıların ikiye tümleyen ile temsil edildiğini açıkça söyler.

Fikir şu: n bitlik işaretli bir sayıda en yüksek bitin ağırlığı +2ⁿ⁻¹ değil, −2ⁿ⁻¹'dir. 8 bitte en soldaki bit −128 değerindedir, diğer bitler her zamanki gibi pozitiftir:

bit değerleri:  -128   64   32   16    8    4    2    1
                ---------------------------------------
   5 =            0     0    0    0    0    1    0    1   →  4 + 1 = 5
  -5 =            1     1    1    1    1    0    1    1   →  -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5
-128 =            1     0    0    0    0    0    0    0   →  -128
  -1 =            1     1    1    1    1    1    1    1   →  -128 + 127 = -1

Bir sayının negatifini elle bulmanın tarifi kısadır: bütün bitleri ters çevir, sonra 1 ekle.

 5       = 0000 0101
^5       = 1111 1010   bitleri ters çevir (bu -6'dır)
^5 + 1   = 1111 1011   1 ekle (bu -5'tir)

Neden işe yarıyor? Bir sayıyı bitleri ters çevrilmiş haliyle topladığında her konumda tam olarak bir tane 1 bulunur ve hiç elde oluşmaz; sonuç "bütün bitler 1" olur. Bütün bitleri 1 olan işaretli sayı ise −1'dir:

x + ^x = 1111 1111 = -1
    ⇒  ^x     = -1 - x
    ⇒  ^x + 1 = -x

Go'da tekli ^ operatörü bitleri ters çevirir, bu yüzden özdeşliği doğrudan ^x + 1 == -x olarak yazabilirsin. Bu eşitlik ilerideki x & -x hilesinin anahtarı olacak.

İkiye tümleyenin iki güzel sonucu daha var. Birincisi, tek bir sıfır vardır. İkincisi, toplama ve çıkarma işaretli ve işaretsiz sayılar için bit düzeyinde birebir aynıdır: işlemci yalnızca bitleri toplar, sonucu nasıl yorumlayacağına tip karar verir. Aralığın neden asimetrik olduğu da buradan anlaşılır: 8 bitle 256 desen vardır, biri sıfıra, 127'si pozitiflere, 128'i negatiflere gider. Bu yüzden int8'de −128 var ama +128 yok.

package main

import "fmt"

func main() {
	values := []int8{5, -5, 127, -128, -1, 0}
	for _, v := range values {
		// uint8'e dönüşüm bitleri değiştirmez, sadece yorumu değiştirir
		fmt.Printf("%5d  %08b\n", v, uint8(v))
	}

	var x int8 = 5
	fmt.Printf("^x     = %4d  %08b\n", ^x, uint8(^x))
	fmt.Printf("^x + 1 = %4d  %08b\n", ^x+1, uint8(^x+1))
	fmt.Println("^x+1 == -x:", ^x+1 == -x)

	// %b işaretli sayıda eksi işareti yazar, bellekteki bitleri göstermez
	fmt.Printf("%b\n", x-10)
}

    5  00000101
   -5  11111011
  127  01111111
 -128  10000000
   -1  11111111
    0  00000000
^x     =   -6  11111010
^x + 1 =   -5  11111011
^x+1 == -x: true
-101

Taşma ve sarmalama

Sabit genişlikli bir tamsayı sınırını aştığında hata vermez, sarmalar (wraparound). Bunu eski bir kilometre sayacına benzetebilirsin: 999999'dan sonra 000000 gelir. İşaretsiz tiplerde aritmetik 2ⁿ moduna göre yapılır; uint8 için 255 + 1 = 0 ve 0 − 1 = 255 olur. Go spesifikasyonu işaretli tiplerde de sonucu açıkça tanımlar: taşan bitler atılır, kalan bitler ikiye tümleyen olarak yorumlanır ve panik oluşmaz. Bu yüzden int8 için 127 + 1 = −128 olur. C ve C++'ta işaretli taşma tanımsız davranıştır; Go'da tanımlıdır ama pratikte neredeyse her zaman bir hatanın işaretidir.

package main

import (
	"fmt"
	"math"
)

func main() {
	var u uint8 = 255
	u++
	fmt.Println("uint8: 255 + 1 =", u)

	var d uint8 = 0
	d--
	fmt.Println("uint8: 0 - 1 =", d)

	var s int8 = 127
	s++
	fmt.Println("int8: 127 + 1 =", s)

	var m int8 = math.MinInt8
	fmt.Println("int8: -(-128) =", -m) // +128 int8'e sığmaz

	var big int64 = math.MaxInt64
	fmt.Println("MaxInt64 + 1 == MinInt64:", big+1 == math.MinInt64)
}

uint8: 255 + 1 = 0
uint8: 0 - 1 = 255
int8: 127 + 1 = -128
int8: -(-128) = -128
MaxInt64 + 1 == MinInt64: true

-(-128) sonucunun yine −128 çıkmasına dikkat et. Aynı durum math.MinInt64 için de geçerlidir: mutlak değer fonksiyonu yazarken en küçük negatif sayı sessizce negatif kalır.

Sarmalama yalnızca çalışma zamanında sessizdir. Sabitler derleme zamanında kontrol edildiğinden sığmayan bir sabit derleme hatası verir:

var x int8 = 128
var mask int32 = 1 << 31

cannot use 128 (untyped int constant) as int8 value in variable declaration (overflows)
cannot use 1 << 31 (untyped int constant 2147483648) as int32 value in variable declaration (overflows)

Go'nun bit operatörleri

Go altı bit operatörü sunar. Hepsi yalnızca tamsayılarla çalışır ve her bit konumunu diğerlerinden bağımsız olarak işler (kaydırmalar hariç).

Aynı kuralları tek bitlik doğruluk tablosu olarak da görebilirsin:

&^ Go'ya özgü bir operatördür: a &^ b, a & ^b ile aynı sonucu verir ama "b'nin işaretlediği bitleri temizle" niyetini tek adımda ve okunaklı biçimde anlatır. Mantıksal &&, || ve ! ise yalnızca bool içindir; Go int ile bool arasında örtük dönüşüm yapmadığından & ile &&'yi karıştırmak genellikle derleme hatasıyla yakalanır.

package main

import "fmt"

func main() {
	var a uint8 = 0b1100_1010
	var b uint8 = 0b1010_0110

	fmt.Printf("a      = %08b\n", a)
	fmt.Printf("b      = %08b\n", b)
	fmt.Printf("a & b  = %08b\n", a&b)
	fmt.Printf("a | b  = %08b\n", a|b)
	fmt.Printf("a ^ b  = %08b\n", a^b)
	fmt.Printf("a &^ b = %08b\n", a&^b)
	fmt.Printf("^a     = %08b\n", ^a)
	fmt.Printf("a << 2 = %08b\n", a<<2)
	fmt.Printf("a >> 3 = %08b\n", a>>3)
}

a      = 11001010
b      = 10100110
a & b  = 10000010
a | b  = 11101110
a ^ b  = 01101100
a &^ b = 01001000
^a     = 00110101
a << 2 = 00101000
a >> 3 = 00011001

a << 2 satırında soldan taşan iki bit (11) kayboldu: uint8 yalnızca 8 bit tutar. Kaydırma, genişliğin dışına çıkan bitleri sessizce atar.

Operatör önceliği

Go'nun öncelik tablosu C'den farklıdır ve bit işlemleri için daha sezgiseldir. <<, >>, & ve &^ çarpma (*) ile aynı düzeydedir; | ve ^ toplama (+) ile aynı düzeydedir; == ve < gibi karşılaştırmalar bunların hepsinden sonra gelir.

gofmt bu önceliği boşluklarla gösterir: 1<<n - 1 yazımında sıkı bağlanan kısım bitişik yazılır. Yine de C kodunu Go'ya taşıyorsan ya da okuyucunun duraksayacağını düşünüyorsan parantez kullanmaktan çekinme.

Sağa kaydırma: aritmetik ve mantıksal

x << n, taşma olmadığı sürece x · 2ⁿ ile aynıdır. x >> n ise x / 2ⁿ sonucunu aşağı yuvarlar. Sağa kaydırırken boşalan yüksek bitlere ne yazılacağı operandın tipine bağlıdır:

• İşaretsiz tiplerde soldan 0 girer. Buna mantıksal kaydırma (logical shift) denir.
• İşaretli tiplerde soldan işaret biti kopyalanır. Buna aritmetik kaydırma (arithmetic shift) denir; negatif bir sayı böylece negatif kalır.

int8(-8)   = 1111 1000
      >> 1 = 1111 1100  = -4    soldan işaret biti (1) girdi

uint8(248) = 1111 1000
      >> 1 = 0111 1100  = 124   soldan 0 girdi

package main

import "fmt"

func main() {
	var s int8 = -8
	u := uint8(s) // aynı bitler: 11111000

	fmt.Printf("s      = %4d  %08b\n", s, uint8(s))
	fmt.Printf("s >> 1 = %4d  %08b  (aritmetik)\n", s>>1, uint8(s>>1))
	fmt.Printf("u      = %4d  %08b\n", u, u)
	fmt.Printf("u >> 1 = %4d  %08b  (mantıksal)\n", u>>1, u>>1)

	// kaydırma aşağı yuvarlar, bölme sıfıra doğru yuvarlar
	fmt.Println(-7>>1, -7/2)

	// kaydırma miktarı bit genişliğini aşabilir
	n := 70
	var x uint64 = 12345
	var neg int64 = -12345
	var pos int64 = 12345
	fmt.Println(x<<n, x>>n, neg>>n, pos>>n)
}

s      =   -8  11111000
s >> 1 =   -4  11111100  (aritmetik)
u      =  248  11111000
u >> 1 =  124  01111100  (mantıksal)
-4 -3
0 0 -1 0

-7 >> 1 sonucunun −4, -7 / 2 sonucunun −3 olduğuna dikkat et. Go'da tamsayı bölmesi sıfıra doğru, aritmetik kaydırma eksi sonsuza doğru yuvarlar. "2'ye bölmek yerine kaydırayım" optimizasyonu negatif sayılarda bu yüzden sessizce farklı sonuç verir. Derleyiciler sabit bir 2'nin kuvvetine bölmeyi zaten verimli koda çevirir; niyetin bölmekse / yaz.

Kaydırma miktarının kuralları

C'de bir sayıyı bit genişliği kadar ya da daha fazla kaydırmak tanımsız davranıştır. Go'da kurallar nettir:

1. Kaydırma miktarının üst sınırı yoktur. Spesifikasyona göre x << n, x'i n kez birer birer kaydırmak gibi davranır. Genişliği aşan bir kaydırmada sola kaydırılan her sayı ve sağa kaydırılan her işaretsiz sayı 0 olur. İşaretli bir sayıyı sağa kaydırırsan sonuç, sayı negatifse −1 (bütün bitler işaret biti), değilse 0 olur. Yukarıdaki çıktının son satırı tam olarak bunu gösteriyor.
2. Kaydırma miktarı negatif olamaz. Go 1.13'ten beri kaydırma miktarı işaretli bir tamsayı olabilir, ama çalışma zamanında negatifse program panikler. Sabit bir negatif miktar ise doğrudan derleme hatasıdır.
3. Sabit bir miktarla yapılan anlamsız kaydırmayı go vet yakalar. u bir uint64 iken u << 64 yazarsan vet u (64 bits) too small for shift of 64 uyarısı verir.

package main

import "fmt"

func main() {
	k := 0
	mask := 1 << (k - 1) // k-1 = -1
	fmt.Println(mask)
}

panic: runtime error: negative shift amount

Bu hata en çok 1 << (k-1) gibi ifadelerde, k sıfır olduğunda ortaya çıkar. Kaydırma miktarını bir hesaplamadan alıyorsan önce sınırlarını kontrol et.

Tek bir biti okuma, açma, kapatma ve değiştirme

Bit manipülasyonunun temel taşı maske (mask) kavramıdır: yalnızca ilgilendiğin konumlarda 1 olan bir sayı. i. bit için maske 1 << i olur. Bu maskeyi dört operatörle birleştirerek tek bir bit üzerinde istediğin her işlemi yapabilirsin.

Aynı maskenin her operatörle ne yaptığını yan yana görelim (x = 0010 1001, i = 4):

x          = 0010 1001
m = 1 << 4 = 0001 0000
------------------------
x & m      = 0000 0000   sonuç 0: bit 4 kapalı
x | m      = 0011 1001   bit 4 açıldı
x &^ m     = 0010 1001   bit 4 zaten kapalıydı, hiçbir şey değişmedi
x ^ m      = 0011 1001   bit 4 ters çevrildi

package main

import "fmt"

// Has, i. bitin açık olup olmadığını söyler.
func Has(x uint8, i uint) bool { return x&(1<<i) != 0 }

// Set, i. biti 1 yapar.
func Set(x uint8, i uint) uint8 { return x | 1<<i }

// Clear, i. biti 0 yapar.
func Clear(x uint8, i uint) uint8 { return x &^ (1 << i) }

// Toggle, i. biti ters çevirir.
func Toggle(x uint8, i uint) uint8 { return x ^ 1<<i }

func main() {
	var x uint8 = 0b0010_1001
	fmt.Printf("başlangıç  %08b\n", x)
	fmt.Println("bit 3 açık mı?", Has(x, 3))
	fmt.Println("bit 4 açık mı?", Has(x, 4))

	x = Set(x, 4)
	fmt.Printf("Set(4)     %08b\n", x)
	x = Clear(x, 0)
	fmt.Printf("Clear(0)   %08b\n", x)
	x = Toggle(x, 7)
	fmt.Printf("Toggle(7)  %08b\n", x)
	x = Toggle(x, 7)
	fmt.Printf("Toggle(7)  %08b\n", x)

	low := uint8(1)<<4 - 1 // en düşük 4 bitin maskesi
	fmt.Printf("maske      %08b\n", low)
	fmt.Printf("x & maske  %08b\n", x&low)
}

başlangıç  00101001
bit 3 açık mı? true
bit 4 açık mı? false
Set(4)     00111001
Clear(0)   00111000
Toggle(7)  10111000
Toggle(7)  00111000
maske      00001111
x & maske  00001000

Aynı biti iki kez ters çevirmenin başlangıç değerine döndürdüğünü görüyorsun; bu, XOR'un kendi kendisinin tersi olmasından gelir. Son iki satırdaki "düşük k biti maskele" kalıbı ise x % 16 işleminin işaretsiz sayılar için bit karşılığıdır: 2ⁿ ile mod almak, en düşük n biti tutmak demektir.

x & (x-1): en düşük 1 bitini silmek

Bir sayıdan 1 çıkardığında bitlere ne olur? İkilikte çıkarma, en sağdaki 1 bitine ulaşana kadar "ödünç alır": o 1 biti 0 olur, sağındaki bütün 0'lar 1'e döner, solundaki bitler ise hiç değişmez.

x         = 1011 0100
x - 1     = 1011 0011     en sağdaki 1 → 0, sağındaki 0'lar → 1
x & (x-1) = 1011 0000     değişen kısım sıfırlandı: en düşük 1 biti silindi

İki sayıyı VE'lediğinde değişen kısım tamamen sıfırlanır, değişmeyen kısım olduğu gibi kalır. Sonuç, x'in en düşük 1 biti silinmiş halidir. Bu tek satırlık hile iki klasik problemi çözer.

1 bitlerini saymak: Kernighan yöntemi

Her adımda tam bir 1 biti sildiğine göre, sayı sıfır olana kadar kaç adım attığını saymak açık bitlerin sayısını (popcount) verir. Döngü 64 bitin hepsine bakmaz, yalnızca açık bit sayısı kadar döner.

2'nin kuvveti kontrolü

2'nin kuvvetlerinin ikilik gösteriminde tam bir tane 1 biti vardır: 1 = 0001, 2 = 0010, 16 = 1 0000. O tek biti silersen geriye 0 kalır; diğer pozitif sayılarda en az iki açık bit olduğu için silme sonrasında bir şey kalır. Dolayısıyla x&(x-1) == 0 testi neredeyse doğrudur, ama iki tuzağı var:

• x = 0 için 0 & (0-1) = 0 & -1 = 0 çıkar; test sıfırı yanlışlıkla 2'nin kuvveti sayar.
• İşaretli tiplerde en küçük değer (math.MinInt64 = 1000…0) de tek bir açık bite sahiptir; x-1 sarmalayıp 0111…1 olur ve test bu negatif sayıyı da kabul eder.

Bu yüzden doğru ifade x > 0 && x&(x-1) == 0 şeklindedir.

x & -x: en düşük 1 bitini yalıtmak

İkiye tümleyenden hatırla: -x = ^x + 1. Bitleri ters çevirince x'in en düşük 1 biti 0 olur, sağındaki 0'lar 1 olur. 1 eklediğinde bu 1'ler elde ile tekrar 0'a döner ve elde tam da o konumda durur. Sonuçta -x ile x yalnızca o konumda ortak bir 1 bitine sahiptir:

x         = 1011 0100
^x        = 0100 1011
-x = ^x+1 = 0100 1100
x & -x    = 0000 0100     yalnızca en düşük 1 biti kaldı

Bu değer, Fenwick ağacında bir sonraki düğüme atlamak için kullanılan meşhur "en düşük bit" hilesidir. Go'da tekli eksi işaretsiz tiplerde de geçerlidir ve 2ⁿ moduna göre 0 - x hesaplar; bu yüzden x & -x hem int hem uint ile çalışır.

package main

import (
	"fmt"
	"math"
)

// popCount, Kernighan yöntemiyle açık bitleri sayar.
func popCount(x uint64) int {
	count := 0
	for x != 0 {
		x &= x - 1 // en düşük 1 bitini sil
		count++
	}
	return count
}

func isPowerOfTwo(x int) bool {
	return x > 0 && x&(x-1) == 0
}

func main() {
	var x uint8 = 0b1011_0100
	fmt.Printf("x        = %08b\n", x)
	fmt.Printf("x-1      = %08b\n", x-1)
	fmt.Printf("x&(x-1)  = %08b\n", x&(x-1))
	fmt.Printf("-x       = %08b\n", -x)
	fmt.Printf("x&-x     = %08b\n", x&-x)

	fmt.Println("popCount(180) =", popCount(180))

	for _, v := range []int{0, 1, 6, 16, 1024, -8} {
		fmt.Printf("%5d: 2'nin kuvveti mi? %v\n", v, isPowerOfTwo(v))
	}

	naive := func(x int) bool { return x&(x-1) == 0 }
	fmt.Println("naive(0) =", naive(0), "naive(MinInt) =", naive(math.MinInt))
}

x        = 10110100
x-1      = 10110011
x&(x-1)  = 10110000
-x       = 01001100
x&-x     = 00000100
popCount(180) = 4
    0: 2'nin kuvveti mi? false
    1: 2'nin kuvveti mi? true
    6: 2'nin kuvveti mi? false
   16: 2'nin kuvveti mi? true
 1024: 2'nin kuvveti mi? true
   -8: 2'nin kuvveti mi? false
naive(0) = true naive(MinInt) = true

Son satır, x > 0 koşulunu atlayan "saf" sürümün iki kenar durumda da yanlış cevap verdiğini kanıtlıyor.

Aynı aileden birkaç kalıp daha, hepsi x = 0101 1000 için:

XOR hileleri

XOR'un dört basit özelliği pek çok zekice çözümün temelidir:

Birlikte düşündüğünde şunu söylerler: bir XOR zincirinde sıranın önemi yoktur ve çift sayıda geçen her değer kendi kendini yok eder. XOR'u "elde taşımayan toplama" olarak da düşünebilirsin: her bit konumunda 2'ye göre mod alınmış toplam.

Tek kalan sayı

Problem: Bir dizide her sayı tam iki kez geçiyor, yalnızca biri bir kez geçiyor. O sayıyı O(n) zamanda ve O(1) ek bellekle bul.

Hash tablosuyla saymak O(n) ek bellek harcar, sıralamak O(n log n) zaman alır. XOR ise bütün sayıları tek bir değişkende birleştirir: çiftler birbirini yok eder, geriye yalnız olan kalır. [4, 1, 2, 1, 2] için adım adım:

Ara değerler anlamsız görünebilir, ama sonuçta her iki 1 ve her iki 2 birbirini götürür.

Eksik sayı

Problem: 0'dan n'e kadar olan sayılardan biri eksik olacak şekilde n elemanlı bir dizi veriliyor. Eksik sayıyı bul.

0 ^ 1 ^ … ^ n değerini dizideki bütün elemanlarla XOR'larsan, dizide bulunan her sayı iki kez (bir kez indeks ya da n olarak, bir kez değer olarak) geçer ve yok olur; geriye yalnızca eksik sayı kalır. n(n+1)/2 - toplam formülü de işe yarar, ama XOR'da taşma diye bir derdin olmaz.

package main

import "fmt"

// singleNumber: her sayı iki kez, biri tek kez geçiyor.
func singleNumber(nums []int) int {
	result := 0
	for _, n := range nums {
		result ^= n
	}
	return result
}

// missingNumber: 0..n aralığından tam bir sayı eksik.
func missingNumber(nums []int) int {
	result := len(nums) // n'yi baştan zincire kat
	for i, n := range nums {
		result ^= i ^ n
	}
	return result
}

func main() {
	fmt.Println(singleNumber([]int{4, 1, 2, 1, 2}))
	fmt.Println(missingNumber([]int{3, 0, 1}))
	fmt.Println(missingNumber([]int{9, 6, 4, 2, 3, 5, 7, 0, 1}))
}

4
2
8

Geçici değişken olmadan takas ve neden kullanmamalısın

XOR'un kendi tersi olması, iki değişkeni üçüncü bir değişken olmadan takas etmeye izin verir:

başlangıç:  a = 0110 (6)   b = 1001 (9)
a ^= b  →   a = 1111       b = 1001
b ^= a  →   a = 1111       b = 0110 (6)    b ^ (a ^ b) = a
a ^= b  →   a = 1001 (9)   b = 0110 (6)    (a ^ b) ^ a = b

Bu hile mülakatlarda sorulabilir, ama gerçek kodda bir tuzağı var: iki işaretçi aynı bellek konumunu gösterirse ilk adım a ^= a olur, değer sıfırlanır ve geri dönüşü yoktur.

package main

import "fmt"

func xorSwap(a, b *int) {
	*a ^= *b
	*b ^= *a
	*a ^= *b
}

func main() {
	x, y := 6, 9
	xorSwap(&x, &y)
	fmt.Println(x, y)

	nums := []int{10, 20, 30}
	i, j := 1, 1 // aynı indeks
	xorSwap(&nums[i], &nums[j])
	fmt.Println(nums) // 20 kayboldu

	nums = []int{10, 20, 30}
	nums[i], nums[j] = nums[j], nums[i] // Go'nun deyimsel takası
	fmt.Println(nums)
}

9 6
[10 0 30]
[10 20 30]

Sıralama algoritmalarında i == j durumu çok kolay oluşur. Go'da a, b = b, a çoklu ataması hem okunaklıdır hem de bu tuzağa düşmez. Modern derleyiciler geçici değişkenli takası zaten verimli koda çevirdiğinden XOR takası pratikte bir hız kazancı da sağlamaz; bu hileyi bil, ama kullanma.

math/bits paketi

Açık bitleri saymak ya da baştaki sıfırları bulmak için döngü yazmak öğreticidir; gerçek kodda ise math/bits paketini kullan. Paket belgelerine göre bu fonksiyonların bir kısmı derleyici tarafından doğrudan uygulanır ve hangilerinin böyle ele alındığı mimariye ve Go sürümüne bağlıdır. Destekleyen işlemcilerde bu çağrılar birkaç makine komutuna, hatta tek bir komuta dönüşebilir.

Her fonksiyonun 8, 16, 32 ve 64 ekli sürümleri ile uint alan eksiz sürümü (bits.OnesCount, bits.Len …) vardır. Hepsi işaretsiz tip ister; int ile çalışıyorsan uint(x) dönüşümü yap. Len ile LeadingZeros birbirini tamamlar: bits.Len64(x) == 64 - bits.LeadingZeros64(x). Len sıfır için 0 döndürür, pozitif x için ise bits.Len(x) - 1 değeri ⌊log₂ x⌋'e eşittir. Pakette ayrıca taşmayı elde olarak döndüren bits.Add64 ve 128 bitlik çarpım sonucunu iki parça halinde veren bits.Mul64 gibi aritmetik yardımcılar da bulunur.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	var x uint8 = 0b0010_1100

	fmt.Printf("x               = %08b\n", x)
	fmt.Println("OnesCount8      =", bits.OnesCount8(x))
	fmt.Println("LeadingZeros8   =", bits.LeadingZeros8(x))
	fmt.Println("TrailingZeros8  =", bits.TrailingZeros8(x))
	fmt.Println("Len8            =", bits.Len8(x))
	fmt.Printf("RotateLeft8(3)  = %08b\n", bits.RotateLeft8(x, 3))
	fmt.Printf("RotateLeft8(-3) = %08b\n", bits.RotateLeft8(x, -3))
	fmt.Printf("Reverse8        = %08b\n", bits.Reverse8(x))

	// int ile çalışırken uint'e dönüştür
	n := 1_000_000
	fmt.Println("OnesCount(n)    =", bits.OnesCount(uint(n)))
	fmt.Println("Len(n)          =", bits.Len(uint(n)))

	// n'den büyük veya eşit en küçük 2'nin kuvveti (n > 1 için)
	fmt.Println("sonraki kuvvet  =", 1<<bits.Len(uint(n-1)))
	fmt.Println("UintSize        =", bits.UintSize)
}

x               = 00101100
OnesCount8      = 3
LeadingZeros8   = 2
TrailingZeros8  = 2
Len8            = 6
RotateLeft8(3)  = 01100001
RotateLeft8(-3) = 10000101
Reverse8        = 00110100
OnesCount(n)    = 7
Len(n)          = 20
sonraki kuvvet  = 1048576
UintSize        = 64

1 << bits.Len(uint(n-1)) kalıbı sık işine yarar: n'den büyük veya n'e eşit en küçük 2'nin kuvvetini verir. Kapasitesini 2'nin kuvvetleri halinde tutan veri yapıları bu hesabı kullanır. bits.UintSize ise programın derlendiği platformda uint ve int'in kaç bit olduğunu söyleyen bir sabittir.

Bit bayrakları: iota ile izinler

Birbirinden bağımsız birkaç açık/kapalı seçeneği tek bir tamsayıda tutmak istediğinde her seçeneğe bir bit ayırırsın. Go'da bunun deyimsel yolu 1 << iota ile sabit tanımlamaktır (iota ile numaralandırma). Standart kütüphane de böyle yapar: os.OpenFile(name, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0o644) çağrısındaki bayraklar ve log.SetFlags(log.Ldate | log.Ltime) birer bit maskesidir. Aynı çağrıdaki 0o644 ise Unix izin bitleridir: sekizlik her rakam üç biti (okuma, yazma, çalıştırma) temsil eder.

package main

import "fmt"

// Permission, Unix'teki gibi üç izni tek bir sayıda tutar.
type Permission uint8

const (
	Execute Permission = 1 << iota // 001 = 1
	Write                          // 010 = 2
	Read                           // 100 = 4
)

// Has, istenen bayrakların hepsinin açık olup olmadığını söyler.
func (p Permission) Has(flags Permission) bool { return p&flags == flags }

func (p Permission) String() string {
	b := []byte("---")
	if p.Has(Read) {
		b[0] = 'r'
	}
	if p.Has(Write) {
		b[1] = 'w'
	}
	if p.Has(Execute) {
		b[2] = 'x'
	}
	return string(b)
}

func main() {
	p := Read | Write
	fmt.Printf("%s = %d (%03b)\n", p, p, p)

	p |= Execute // izin ver
	fmt.Printf("%s = %d (%03b)\n", p, p, p)

	p &^= Write // izni geri al
	fmt.Printf("%s = %d (%03b)\n", p, p, p)

	fmt.Println("yazabilir mi?", p.Has(Write))
	fmt.Println("okuyup çalıştırabilir mi?", p.Has(Read|Execute))

	// chmod 754: sahip rwx, grup r-x, diğerleri r--
	mode := 0o754
	fmt.Println(Permission(mode>>6&7), Permission(mode>>3&7), Permission(mode&7))
}

rw- = 6 (110)
rwx = 7 (111)
r-x = 5 (101)
yazabilir mi? false
okuyup çalıştırabilir mi? true
rwx r-x r--

Has metodunda p&flags == flags yazdığımıza dikkat et. p&flags != 0 yazsaydık, birden fazla bayrak sorduğumuzda "hepsi var mı?" yerine "en az biri var mı?" sorusunu cevaplamış olurduk; p.Has(Read|Write) çağrısı r-x için yanlışlıkla true dönerdi. Tek bir tamsayıda sekiz, on altı veya altmış dört bayrak tutmak; bayrak kümelerini == ile karşılaştırmak, map anahtarı yapmak ve tek bir | ile birleştirmek, ayrı bool alanlara göre hem daha az bellek harcar hem de daha pratiktir.

Bitmask ile alt kümeleri gezme

n elemanlı bir kümenin 2ⁿ alt kümesi vardır. Her alt kümeyi n bitlik bir sayıyla eşleyebilirsin: i. bit 1 ise i. eleman alt kümededir, 0 ise değildir. 0'dan 2ⁿ − 1'e kadar saymak, böylece bütün alt kümeleri tam birer kez gezmek demektir.

indeks:      2       1       0
eleman:    kiraz   armut   elma

mask = 5 = 1       0       1    →  {elma, kiraz}
mask = 6 = 1       1       0    →  {armut, kiraz}

Go 1.22 ile gelen tamsayı üzerinde range sayesinde döngü çok kısadır: for mask := range 1 << n.

package main

import "fmt"

func main() {
	items := []string{"elma", "armut", "kiraz"}
	n := len(items)

	for mask := range 1 << n {
		var subset []string
		for i := range n {
			if mask&(1<<i) != 0 {
				subset = append(subset, items[i])
			}
		}
		fmt.Printf("%d  %03b  %v\n", mask, mask, subset)
	}
}

0  000  []
1  001  [elma]
2  010  [armut]
3  011  [elma armut]
4  100  [kiraz]
5  101  [elma kiraz]
6  110  [armut kiraz]
7  111  [elma armut kiraz]

Bu yöntem, Geri İzleme dersindeki özyinelemeli alt küme üretiminin döngüyle yazılmış karşılığıdır. Avantajı, her alt kümenin tek bir sayı olmasıdır; bu sayıyı dizi indeksi ya da map anahtarı olarak kullanabilirsin. Sınırı ise n'dir: n = 20 için yaklaşık bir milyon, n = 30 için yaklaşık bir milyar alt küme vardır. Pratikte bitmask ile gezme n ≤ 20 civarında kullanılır; int 64 bit olsa bile n ≥ 63 için 1 << n işaret bitine taşar ve döngü hiç çalışmaz.

Bir maskenin alt maskelerini gezmek

Bazen bütün alt kümeleri değil, belirli bir mask'in alt kümelerini (alt maskelerini) gezmek istersin. Klasik deyim sub = (sub - 1) & mask şeklindedir. 1 çıkarmak en düşük 1 bitini 0 yapar ve altındaki bütün bitleri 1'e çevirir; & mask ise bu 1'lerden yalnızca maskede bulunan konumları bırakır. Etkisi, maskenin açık bitleri üzerinde geriye sayan bir sayaç gibidir: alt maskeleri büyükten küçüğe, her birini tam bir kez gezer.

mask = 1011

sub  = 1011
1011 - 1 = 1010  →  & 1011 = 1010
1010 - 1 = 1001  →  & 1011 = 1001
1001 - 1 = 1000  →  & 1011 = 1000
1000 - 1 = 0111  →  & 1011 = 0011   bit 2 maskede yok, atlandı
0011 - 1 = 0010  →  & 1011 = 0010
0010 - 1 = 0001  →  & 1011 = 0001
0001 - 1 = 0000  →  & 1011 = 0000   boş küme: işle ve dur

Boş küme de bir alt küme olduğundan döngüyü "sub > 0 iken" diye yazarsan onu kaçırırsın. Aşağıdaki program boş kümeyi de işleyip sonra çıkıyor. İkinci kısımda ise m &= m - 1 ile en düşük biti silerken bits.TrailingZeros ile silinen bitin indeksini okuyoruz; yalnızca açık bitleri gezmenin en hızlı yolu budur.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	mask := 0b1011

	fmt.Println("alt maskeler:")
	for sub := mask; ; sub = (sub - 1) & mask {
		fmt.Printf("  %04b\n", sub)
		if sub == 0 {
			break
		}
	}

	fmt.Print("açık bitlerin indeksleri:")
	for m := uint(mask); m != 0; m &= m - 1 {
		fmt.Print(" ", bits.TrailingZeros(m))
	}
	fmt.Println()
}

alt maskeler:
  1011
  1010
  1001
  1000
  0011
  0010
  0001
  0000
açık bitlerin indeksleri: 0 1 3

k açık biti olan bir maskenin 2ᵏ alt maskesi vardır. Bütün n bitlik maskelerin bütün alt maskelerini gezersen toplam iş O(2ⁿ · 2ⁿ) değil O(3ⁿ) olur. Sebebi şu: her eleman için üç durum vardır (maskede yok; maskede var ama alt maskede yok; ikisinde de var) ve her (mask, sub) çifti bu durumların bir seçimine karşılık gelir. n = 15 için 3¹⁵ ≈ 14,3 milyon, gayet makul bir sayı.

Bitmask DP'ye kısa bir bakış

Bitmask'in en güçlü kullanım alanı, durumu "şu ana kadar hangi elemanları kullandım?" sorusuyla tanımlanan dinamik programlama problemleridir. Klasik örnek gezgin satıcı problemidir (Traveling Salesman Problem, TSP): n şehrin her birini tam bir kez ziyaret edip başlangıca dönen en kısa turu bul.

Kaba kuvvet bütün sıralamaları dener: 0. şehri sabitlersen (n − 1)! tur kalır, n = 16 için bu 15! ≈ 1,3 trilyon demektir. Oysa turun geri kalanının en iyi maliyeti yalnızca iki bilgiye bağlıdır: hangi şehirleri gezdin ve şu an hangi şehirdesin. Gezdiğin şehirlerin hangi sırayla gezildiği gelecekteki kararları etkilemez. Bu yüzden durumu şöyle tanımlarız:

dp[mask][i] = 0. şehirden başlayıp mask'teki şehirleri tam birer kez gezerek
              i. şehirde biten yolların en düşük maliyeti

başlangıç:    dp[0001][0] = 0

geçiş:        j mask'te değilse
              dp[mask | 1<<j][j] = min(dp[mask | 1<<j][j], dp[mask][i] + dist[i][j])

cevap:        i üzerinden min( dp[1111][i] + dist[i][0] )

2ⁿ · n durum ve her durumdan en fazla n geçiş vardır, toplam O(2ⁿ · n²). n = 16 için bu 2¹⁶ · 256 ≈ 16,8 milyon işlem eder; trilyonlarla kıyaslanamayacak kadar az. Aşağıdaki program dört şehir için fikri gösteriyor:

package main

import (
	"fmt"
	"math"
)

func main() {
	// dist[i][j]: i şehrinden j şehrine gitmenin maliyeti
	dist := [][]int{
		{0, 10, 15, 20},
		{10, 0, 35, 25},
		{15, 35, 0, 30},
		{20, 25, 30, 0},
	}
	n := len(dist)
	const inf = math.MaxInt / 2 // toplarken taşmasın

	dp := make([][]int, 1<<n)
	for mask := range dp {
		dp[mask] = make([]int, n)
		for i := range n {
			dp[mask][i] = inf
		}
	}
	dp[1][0] = 0 // yalnızca 0. şehir gezildi ve oradayız

	for mask := range 1 << n {
		for i := range n {
			if mask&(1<<i) == 0 || dp[mask][i] == inf {
				continue
			}
			for j := range n {
				if mask&(1<<j) != 0 {
					continue
				}
				next := mask | 1<<j
				dp[next][j] = min(dp[next][j], dp[mask][i]+dist[i][j])
			}
		}
	}

	full := 1<<n - 1
	best := inf
	for i := 1; i < n; i++ {
		best = min(best, dp[full][i]+dist[i][0])
	}
	fmt.Println("en kısa tur maliyeti:", best)
}

en kısa tur maliyeti: 80

Burada ayrıntıya girmiyoruz; durum ve geçiş tanımlamayı Dinamik Programlama I, klasik problemleri Dinamik Programlama II dersinde bulacaksın. Akılda tutman gereken sinyal şu: n yaklaşık 20'yi aşmıyor ve problem "her elemanı bir kez kullan" türünde bir kısıt içeriyorsa bitmask DP'yi düşün.

Gray kodu

Normal ikilik sayma sırasında bazen birden fazla bit aynı anda değişir: 3'ten 4'e geçerken (011 → 100) üç bit birden. Mekanik bir konum sensöründe bu bitler tam olarak aynı anda değişmezse, sensör geçiş anında 111 (7) veya 000 (0) gibi bambaşka bir değer okuyabilir. Gray kodu (yansıtılmış ikilik kod) bu sorunu çözer: ardışık her iki değer yalnızca tek bir bitte farklıdır. Döner kodlayıcılar (rotary encoder) bu yüzden Gray kodu kullanır.

Dönüşüm tek satırdır: g = b ^ (b >> 1). Gray kodunun her biti, ikilik sayıdaki komşu iki bitin farklı olup olmadığını söyler. Geri dönüşüm için Gray kodunun sağa kaydırılmış bütün hallerini XOR'larsın, çünkü her ikilik bit kendisinden yukarıdaki Gray bitlerinin XOR'udur.

package main

import (
	"fmt"
	"math/bits"
)

func toGray(b uint) uint { return b ^ b>>1 }

func fromGray(g uint) uint {
	b := g
	for g >>= 1; g != 0; g >>= 1 {
		b ^= g
	}
	return b
}

func main() {
	fmt.Println("i  ikilik  gray  değişen  geri")
	for i := range uint(8) {
		g := toGray(i)
		changed := "-"
		if i > 0 {
			changed = fmt.Sprint(bits.OnesCount(g ^ toGray(i-1)))
		}
		fmt.Printf("%d  %03b     %03b   %s        %d\n", i, i, g, changed, fromGray(g))
	}
}

i  ikilik  gray  değişen  geri
0  000     000   -        0
1  001     001   1        1
2  010     011   1        2
3  011     010   1        3
4  100     110   1        4
5  101     111   1        5
6  110     101   1        6
7  111     100   1        7

"değişen" sütunu, bir önceki satırla arasında kaç bitin farklı olduğunu bits.OnesCount(g1 ^ g2) ile hesaplıyor: her satırda tam 1. İki sayı arasındaki farklı bit sayısına Hamming mesafesi denir ve bu XOR + popcount ikilisi ile tek satırda hesaplanır. Gray kodu algoritmalarda da işe yarar: alt kümeleri Gray sırasıyla gezersen her adımda kümeye tam bir eleman eklenir ya da çıkarılır, böylece toplam gibi bir değeri her seferinde baştan hesaplamak yerine O(1)'de güncelleyebilirsin.

Sık yapılan hatalar

• Negatif bir sayının bitlerini %b ile görmeye çalışmak. fmt eksi işareti ve mutlak değer yazar. Bitleri görmek için uint8(x) veya uint64(x) gibi aynı genişlikteki işaretsiz tipe dönüştür.
• Bit tersi için ~x yazmak. Go'da bit DEĞİL tekli ^x'tir; ~ yalnızca jenerik kısıtlarında kullanılır.
• 2'nin kuvveti kontrolünde x > 0 koşulunu unutmak. x&(x-1) == 0 tek başına 0'ı ve işaretli tiplerin en küçük değerini de kabul eder.
• İşaretli sayıda mantıksal kaydırma beklemek. Negatif bir int'i sağa kaydırmak soldan 1 doldurur. Bitleri sıfır dolgusuyla kaydırmak istiyorsan önce uint'e dönüştür.
• x >> 1 ile x / 2'yi her zaman eşit sanmak. Negatif tek sayılarda sonuçlar farklıdır (−7 için −4 ve −3).
• Kaydırma miktarının negatif olabileceğini gözden kaçırmak. 1 << (k-1) ifadesi k = 0 iken çalışma zamanında panik üretir.
• Operatör önceliğini C'ye göre düşünmek. 1<<n - 1 Go'da (1<<n) - 1 demektir. C'den kod taşırken parantezleri koru.
• Sabitlerin sığmadığını unutmak. var mask int32 = 1 << 31 derlenmez; 32 bitin hepsini kullanacaksan uint32 seç.
• int'in her yerde 64 bit olduğunu varsaymak. 32 bitlik platformlarda int 32 bittir. 64 elemanlık bir bit kümesi için uint64 kullan.
• XOR takasını aynı konum üzerinde çalıştırmak. i == j olduğunda eleman sıfırlanır; a, b = b, a kullan.
• Çoklu bayrak kontrolünde p&flags != 0 yazmak. Bu "en az biri açık mı?" sorusudur; "hepsi açık mı?" için p&flags == flags gerekir.
• Bitmask'i büyük n için denemek. 2ⁿ çok hızlı büyür; n = 30'da bir milyarı geçer. n ≤ 20 civarı güvenli bölgedir.

Alıştırmalar

package main

import (
	"fmt"
	"math/bits"
)

func countBits(n int) []int {
	ans := make([]int, n+1)
	for i := 1; i <= n; i++ {
		ans[i] = ans[i>>1] + i&1
	}
	return ans
}

func main() {
	fmt.Println(countBits(8))

	// math/bits ile doğrula
	for i, c := range countBits(1000) {
		if c != bits.OnesCount(uint(i)) {
			fmt.Println("hata:", i)
		}
	}
	fmt.Println("0..1000 doğrulandı")
}

[0 1 1 2 1 2 2 3 1]
0..1000 doğrulandı

package main

import "fmt"

func twoSingles(nums []int) (int, int) {
	xor := 0
	for _, n := range nums {
		xor ^= n // sonuç: a ^ b
	}
	low := xor & -xor // a ile b'nin farklı olduğu en düşük bit
	a, b := 0, 0
	for _, n := range nums {
		if n&low != 0 {
			a ^= n
		} else {
			b ^= n
		}
	}
	return min(a, b), max(a, b)
}

func main() {
	fmt.Println(twoSingles([]int{1, 2, 1, 3, 2, 5}))
	fmt.Println(twoSingles([]int{-1, 0}))
	fmt.Println(twoSingles([]int{4, 7, 4, 9, 7, 11}))
}

3 5
-1 0
9 11

package main

import "fmt"

func maxProduct(words []string) int {
	masks := make([]uint32, len(words))
	for i, w := range words {
		for _, ch := range w {
			masks[i] |= 1 << (ch - 'a')
		}
	}

	best := 0
	for i := range words {
		for j := i + 1; j < len(words); j++ {
			if masks[i]&masks[j] == 0 {
				best = max(best, len(words[i])*len(words[j]))
			}
		}
	}
	return best
}

func main() {
	fmt.Println(maxProduct([]string{"abcw", "baz", "foo", "bar", "xtfn", "abcdef"}))
	fmt.Println(maxProduct([]string{"a", "ab", "abc", "d", "cd", "bcd", "abcd"}))
	fmt.Println(maxProduct([]string{"a", "aa", "aaa", "aaaa"}))
}

16
4
0

        görev0  görev1  görev2  görev3
işçi0     9       2       7       8
işçi1     6       4       3       7
işçi2     5       8       1       8
işçi3     7       6       9       4

package main

import (
	"fmt"
	"math"
	"math/bits"
)

func minAssignment(cost [][]int) int {
	n := len(cost)
	dp := make([]int, 1<<n)
	for i := range dp {
		dp[i] = math.MaxInt
	}
	dp[0] = 0

	for mask := range 1 << n {
		if dp[mask] == math.MaxInt {
			continue
		}
		worker := bits.OnesCount(uint(mask)) // sıradaki işçi
		if worker == n {
			continue
		}
		for job := range n {
			if mask&(1<<job) == 0 {
				next := mask | 1<<job
				dp[next] = min(dp[next], dp[mask]+cost[worker][job])
			}
		}
	}
	return dp[1<<n-1]
}

func main() {
	cost := [][]int{
		{9, 2, 7, 8},
		{6, 4, 3, 7},
		{5, 8, 1, 8},
		{7, 6, 9, 4},
	}
	fmt.Println(minAssignment(cost))

	fmt.Println(minAssignment([][]int{
		{4, 1, 3},
		{2, 0, 5},
		{3, 2, 2},
	}))
}

13
5

Kısa sınav

Özet

• İkilik sistemde her bit 2'nin bir kuvvetidir; onaltılık her basamak tam 4 bite karşılık gelir. %08b, %x ve 0b/0x sabitleri bitleri görmeni kolaylaştırır.
• Go tamsayıları ikiye tümleyen ile tutar: en yüksek bitin ağırlığı negatiftir ve ^x + 1 == -x. Taşma panik üretmez, sarmalar; sabitlerin taşması ise derleme hatasıdır.
• Operatörler: &, |, ^ (ikili XOR, tekli NOT), &^ (bit temizleme), <<, >>. Go'da ~ yoktur. Sağa kaydırma işaretli tiplerde aritmetik, işaretsizlerde mantıksaldır; genişliği aşan kaydırma tanımlıdır, negatif miktar paniktir.
• Tek bit deyimleri: kontrol x&(1<<i) != 0, açma x |= 1<<i, kapatma x &^= 1<<i, ters çevirme x ^= 1<<i.
• x & (x-1) en düşük 1 bitini siler (popcount, x > 0 koşuluyla 2'nin kuvveti kontrolü); x & -x en düşük 1 bitini yalıtır.
• XOR'da çiftler birbirini yok eder: tek kalan sayı ve eksik sayı O(1) bellekle çözülür. XOR takası bilinmeli ama kullanılmamalıdır.
• Gerçek kodda math/bits kullan: OnesCount, LeadingZeros, TrailingZeros, Len, RotateLeft, Reverse. Bayrakları 1 << iota ile tanımla.
• for mask := range 1 << n bütün alt kümeleri O(2ⁿ · n)'de, (sub - 1) & mask alt maskeleri gezer; n ≤ 20 civarındaki "her elemanı bir kez kullan" problemlerinde bitmask DP ve Gray kodu gibi teknikler güçlü araçlardır.