Bitwise İşlemler: AND, OR, XOR, Shift ve Bit Mask ile Flag Yönetimi

Sürüm notu: Bu yazıdaki kodlar .NET 10 (C# 14), TypeScript 7.0 ve Node.js 24 ile derlenip denenmiştir; C# örneklerinin testleri xUnit v3 4.0.3 ile yazılmıştır.

Önce Tahmin Et

Bookstore'da kitap ID'leri büyüdü, artık 2^40 civarında. Frontend'deki bir yardımcı fonksiyon ID'nin son byte'ını alıp cache'te hangi bölmeye düşeceğini hesaplıyor: bookId & 0xff. bookId = 2 ** 40 + 3 için sonuç 3 olmalı. Peki bookId | 0 ne verir? Sayının kendisi mi, sıfır mı, başka bir şey mi?

C# tarafında da bir soru: int one = 1; int shift = 32; iken one << shift ne olur? 32 bitlik bir int'te 1'i 32 kez sola kaydırınca bit dışarı düşer ve sonuç 0 olmalı, değil mi?

İki sorunun da cevabı "hayır". Serinin ilk yazısında, "Binary ve Hexadecimal" yazısında bitleri okumayı öğrendik. Bu yazıda onları tek tek değiştireceğiz ve bu iki sürprizin nedenini bit düzeyinde göreceğiz.

Altı Operatör: AND, OR, XOR, NOT ve Shift

Bitwise operatörler iki sayının aynı konumdaki bitlerini birbirinden bağımsız olarak işler. Toplamadaki gibi elde (carry) yoktur; her bit kendi sütununda hesaplanır.

static string Bits(uint value, int width = 8) => Convert.ToString(value, 2).PadLeft(width, '0');

uint a = 0b1100_1010;
uint b = 0b1010_0110;
Console.WriteLine($"a      {Bits(a)}");
Console.WriteLine($"b      {Bits(b)}");
Console.WriteLine($"a & b  {Bits(a & b)}");
Console.WriteLine($"a | b  {Bits(a | b)}");
Console.WriteLine($"a ^ b  {Bits(a ^ b)}");
Console.WriteLine($"~a     {Bits(~a & 0xFF)}");
Console.WriteLine($"~a     {Bits(~a, 32)}");

a      11001010
b      10100110
a & b  10000010
a | b  11101110
a ^ b  01101100
~a     00110101
~a     11111111111111111111111100110101

AND (&) yalnızca iki bit de 1 ise 1 verir; bir şeyi "filtrelemek" için kullanılır. OR (|) bitlerden biri 1 ise 1 verir; bir şeyi "eklemek" için. XOR (^, exclusive OR) bitler farklıysa 1 verir; bir şeyi "çevirmek" için. NOT (~) her biti tersine çevirir. Son iki satıra dikkat: a 8 bitlik bir değer gibi görünse de tipi uint, yani 32 bit. ~a üstteki 24 sıfırı da 1 yapar. Sadece alt byte'ı istiyorsan & 0xFF ile maskelemen gerekir. Bu "mask" fikri yazının geri kalanının temeli.

Shift: Kaydırmak, Çarpmak ve Bölmek

x << n bitleri n konum sola kaydırır, sağdan sıfır girer. Her kaydırma 2 ile çarpmak demektir: 5 << 3 = 5 × 8 = 40. Sağa kaydırmak 2'ye bölmektir: 40 >> 3 = 5. Sağa kaydırmada soldan ne gireceği ise sayının tipine bağlı:

int negative = -16;
Console.WriteLine(negative >> 2);    // -4
Console.WriteLine(negative >>> 2);   // 1073741820
Console.WriteLine(-7 / 2);            // -3
Console.WriteLine(-7 >> 1);           // -4

-16        11111111111111111111111111110000
-16 >> 2   11111111111111111111111111111100
-16 >>> 2  00111111111111111111111111111100

Signed bir tipte >> arithmetic shift yapar: en soldaki biti, yani işaret bitini kopyalar, böylece negatif sayı negatif kalır. C# 11 ile gelen >>> ise logical shift (unsigned right shift) yapar: soldan her zaman sıfır girer, tip ne olursa olsun. Daha önce aynı sonuç için (int)((uint)x >> 2) gibi cast'ler yazmak gerekiyordu. Unsigned tiplerde (uint, ulong) iki operatör aynı davranır. Negatif sayının bit düzeninin neden böyle olduğunu, yani two's complement'i serinin sonraki yazısında ayrıntılı göreceğiz.

Son iki satır ince bir farkı gösteriyor: -7 / 2 sıfıra doğru yuvarlar ve -3 verir, -7 >> 1 ise eksi sonsuza doğru yuvarlar ve -4 verir. "Sağa kaydırmak 2'ye bölmektir" kuralı negatif sayılarda birebir geçerli değil. JIT (Just-In-Time; kodu çalışma anında makine koduna çeviren derleyici), sabit bir ikinin kuvvetine bölmeyi zaten shift kullanan bir koda çeviriyor ve negatif sayılar için araya bir düzeltme adımı ekliyor. Performans için / 2 yerine >> 1 yazmana gerek yok; yazarsan negatif sayılarda sonuç değişir.

Bit Mask ile Flag Yönetimi: Set, Clear, Toggle, Test

Bookstore'da her kullanıcının bir izin kümesi var. Bunları ayrı ayrı bool kolonlarda tutmak yerine tek bir sayının bitlerinde tutuyoruz. [Flags] attribute'unun ve enum'ların genel kullanımı C# Temelleri serisinin "C# Enum: Underlying Type, [Flags], Parse ve switch" yazısında anlatıldı; burada bit düzeyine iniyoruz:

namespace Bookstore.Security;

[Flags]
public enum Permission : uint
{
    None = 0,
    ViewCatalog = 1u << 0,
    PlaceOrder = 1u << 1,
    WriteReview = 1u << 2,
    ManageInventory = 1u << 3,
    IssueRefund = 1u << 4,
    ManageUsers = 1u << 5,
    Customer = ViewCatalog | PlaceOrder | WriteReview,
    Staff = Customer | ManageInventory | IssueRefund,
}

public static class PermissionBits
{
    public static Permission Grant(Permission current, Permission add) => current | add;

    public static Permission Revoke(Permission current, Permission remove) => current & ~remove;

    public static Permission Toggle(Permission current, Permission flip) => current ^ flip;

    // İstenen bitlerin hepsi açık olmalı
    public static bool HasAll(Permission current, Permission required) =>
        required != Permission.None && (current & required) == required;

    // İstenen bitlerden en az biri açık olmalı
    public static bool HasAny(Permission current, Permission wanted) => (current & wanted) != 0;
}

Değerleri 1u << n diye yazmak her izne tek bir bit ayrıldığını açıkça gösterir; 1, 2, 4, 8, 16 yazmaktan daha az hata çıkarır. Dört işlem dört idiom'dur. Set: current | add. Clear: current & ~remove, yani "silmek istediğin bitler hariç her şeyi tut". Toggle: current ^ flip. Test: (current & required) == required. Alice'in izinleri üzerinde:

Permission alice = Permission.Customer;                              // Customer = 00000111
alice = PermissionBits.Grant(alice, Permission.IssueRefund);         // Customer, IssueRefund = 00010111
alice = PermissionBits.Revoke(alice, Permission.WriteReview);        // ViewCatalog, PlaceOrder, IssueRefund = 00010011
alice = PermissionBits.Toggle(alice, Permission.WriteReview);        // Customer, IssueRefund = 00010111
PermissionBits.HasAll(alice, Permission.PlaceOrder | Permission.IssueRefund);  // True
PermissionBits.HasAll(alice, Permission.PlaceOrder | Permission.ManageUsers);  // False
PermissionBits.HasAny(alice, Permission.PlaceOrder | Permission.ManageUsers);  // True

HasAll'daki None kontrolü süs değil. Framework'ün HasFlag method'u alice.HasFlag(Permission.None) için True döndürür, çünkü x & 0 == 0 her zaman doğrudur. Configuration'dan okunan bir "gerekli izin" değeri boş gelirse HasFlag herkese izin verir.

BitOperations: Saymak, Bulmak, Yuvarlamak

System.Numerics.BitOperations, CPU destekliyorsa bu işler için ayrılmış özel instruction'ları kullanan method'lar içeriyor. Elle döngüyle yazmana gerek yok:

uint staff = (uint)Permission.Staff;
Console.WriteLine(BitOperations.PopCount(staff));                                // 5
Console.WriteLine(BitOperations.TrailingZeroCount((uint)Permission.IssueRefund)); // 4
Console.WriteLine(BitOperations.LeadingZeroCount((uint)Permission.IssueRefund));  // 27
Console.WriteLine(BitOperations.Log2((uint)Permission.IssueRefund));              // 4
Console.WriteLine(BitOperations.IsPow2((uint)Permission.IssueRefund));            // True
Console.WriteLine(BitOperations.IsPow2((uint)Permission.Customer));               // False
Console.WriteLine(BitOperations.RoundUpToPowerOf2(1000u));                        // 1024
Console.WriteLine(BitOperations.RoundUpToPowerOf2(1024u));                        // 1024

PopCount (population count) açık bit sayısını verir: Staff rolünde 5 izin var. TrailingZeroCount en sağdaki 1'in konumunu, LeadingZeroCount soldaki sıfırların sayısını verir; 32 − 27 − 1 = 4, yani IssueRefund 4 numaralı bit. IsPow2 bir değerde tam olarak tek bit açık mı diye bakar; bir API'ye "tek bir izin" bekleyen yerde birleşik bir değer gelirse bunu yakalar. RoundUpToPowerOf2 ise buffer veya hash tablosu boyutunu bir sonraki ikinin kuvvetine yuvarlamak için kullanılır. .NET 7'den beri aynı method'lar generic math ile tiplerin üzerinde de var: uint.PopCount(staff).

Bir flag değerindeki izinleri tek tek dolaşmak için klasik bir idiom var:

uint remaining = (uint)Permission.Staff;
while (remaining != 0)
{
    int index = BitOperations.TrailingZeroCount(remaining);
    Console.Write($"{(Permission)(1u << index)} ");
    remaining &= remaining - 1;   // en sağdaki 1'i sil
}
// ViewCatalog PlaceOrder WriteReview ManageInventory IssueRefund

x - 1 en sağdaki 1'i sıfır yapar ve onun sağındaki sıfırları 1'e çevirir; x & (x - 1) böylece yalnızca en sağdaki 1'i siler. Döngü açık bit sayısı kadar döner, 32 kez değil.

XOR: Kullanışlı Ama Okunması Zor

XOR'un üç özelliği var: x ^ x = 0, x ^ 0 = x ve sıranın önemi yok. Bunlardan birkaç bilinen hile çıkar:

int p = 12, q = 7;
p ^= q; q ^= p; p ^= q;
Console.WriteLine($"{p} {q}");                    // 7 12

int[] arr = [3, 9, 3, 4, 9];
int lonely = 0;
foreach (int n in arr) lonely ^= n;
Console.WriteLine(lonely);                         // 4

Console.WriteLine(BitOperations.PopCount(0b1011u) & 1);  // 1 (tek sayıda bit açık)

Geçici değişkensiz swap, çiftler birbirini sıfırladığı için dizide tek kalan elemanı bulma, parity yani açık bit sayısının tek mi çift mi olduğu. Parity ve XOR gerçek sistemlerde hata tespitinde, RAID'de (Redundant Array of Independent Disks; birden fazla diski tek bir birim gibi kullanıp veri yedekliliği sağlayan yapı) ve hash fonksiyonlarında iş görür. Ama uygulama kodunda XOR swap yazma. Modern C#'ta (p, q) = (q, p) yazmak hem okunur hem de şu tuzağa düşmez: iki değişken aynı bellek konumunu gösteriyorsa (örneğin ref ile aynı array element'i) XOR swap değeri sıfırlar. Kod incelemesinde birinin durup "bu ne yapıyor" diye düşünmesi gerekiyorsa o kod pahalıdır.

TypeScript: Her Bitwise İşlem 32 Bit

JavaScript'te number 64 bitlik bir floating point değer. Ama bitwise operatörler operand'larını önce 32 bitlik signed integer'a çevirir (spesifikasyondaki adıyla ToInt32), işlemi yapar ve sonucu yine 32 bitlik integer olarak döndürür. Bu çevirme üstteki bitleri hiçbir uyarı vermeden atar:

console.log(2 ** 31 | 0);               // -2147483648
console.log((2 ** 32 + 5) | 0);         // 5
console.log(0x80000000 | 1);            // -2147483647
console.log((0x80000000 | 1) >>> 0);    // 2147483649
console.log(~~3.7, ~~-3.7, Math.trunc(-3.7));  // 3 -3 -3
console.log(1 << 32, 1 << 31);          // 1 -2147483648

const bookId = 2 ** 40 + 3;
console.log(bookId, bookId & 0xff, bookId | 0);  // 1099511627779 3 3

Önce Tahmin Et'teki sorunun cevabı: bookId | 0 3 verir. ID'nin 40. bitten yukarısı kayboldu. & 0xff şans eseri doğru çıktı çünkü zaten yalnızca alt 8 biti istiyorduk. Aynı fonksiyon "ID'yi tam sayıya yuvarla" diye | 0 kullansaydı, 2^31'i geçen her ID bozulurdu ve test verisindeki küçük ID'lerle bunu hiç görmezdin.

>>> 0 hilesi sonucu unsigned 32 bit olarak yorumlatır; ilk yazıda (-1 >>> 0).toString(2) ile 32 tane 1 görmemizin nedeni buydu. ~~x da aynı ToInt32 çevirmesine dayanan eski bir "ondalığı at" hilesi; 2^31'den büyük sayılarda yanlış sonuç verdiği için Math.trunc kullan.

32 bitten büyük değerlerde bitwise işlem gerekiyorsa BigInt kullan. BigInt keyfi genişlikte çalışır ve bitwise operatörleri doğru uygular, ama number ile karıştırılamaz:

const big = 2n ** 40n + 3n;
console.log(big & 0xffn, big | 1n << 50n);    // 3n 1126999418470403n
console.log(BigInt.asUintN(64, -1n));          // 18446744073709551615n
console.log(BigInt.asIntN(8, 255n));           // -1n

BigInt.asUintN ve asIntN değeri belirli bir bit genişliğine sığdırır; C#'taki unchecked cast'lerin karşılığı gibi düşünebilirsin. Büyük ID'lerin JSON üzerinden frontend'e taşınırken nasıl bozulduğunu serinin sonraki yazısında ayrıntılı göreceğiz.

Üretimde Dikkat

Flag enum'unu veritabanında tek bir integer kolonda saklamak pratik ama birkaç kural ister. Bir bit numarası bir kez kullanıldıktan sonra anlamı değişmez. ManageUsers'ı kaldırıp onun bitini yeni bir izne vermek, veritabanındaki eski satırlarda o biti açık olan herkese yeni izni verir. Yeni izinler her zaman kullanılmamış bir bite eklenir; kaldırılan iznin biti boş bırakılır.

Underlying type'a dikkat et. SQL Server'da unsigned integer tipi yok. uint enum'un 31 numaralı bitini kullandığında değer 2147483648 olur; bunu int kolonuna zorla yazarsan -2147483648 olarak saklanır. 31 bitten fazla izin öngörüyorsan baştan long ve bigint seç.

Sorgulama maliyetini düşün. WHERE (Permissions & 16) = 16 kolonun kendisine değil bir ifadeye bakar, bu yüzden index'ten yararlanamaz ve tabloyu tarar. "IssueRefund yetkisi olan herkesi bul" sorgusu sık çalışıyorsa izinleri ayrı bir tabloda satır olarak tutmak daha uygun olabilir. Bit mask kullanıcının kendi izinlerini kontrol ederken iyi çalışır, raporlamada zorlaşır.

API'de sayı yerine isim gönder. System.Text.Json enum'u varsayılan olarak sayı yazar: {"Name":"alice","Permissions":23}. JsonStringEnumConverter eklenince flag değeri okunur hâle gelir: {"Name":"alice","Permissions":"Customer, IssueRefund"}, ve aynı biçim geri okunabilir. Sayı gönderirsen frontend bitwise işlem yapmak zorunda kalır ve yukarıdaki 32 bit sınırına takılır.

Sık Düşülen Tuzaklar

Operatör önceliği. == operatörü &'tan önce işlenir; flags & 4 == 4 aslında flags & (4 == 4) demek. C# bunu derlemez:

int flags = 0b0110;
if (flags & 4 == 4)
{
    Console.WriteLine("can write reviews");
}
// error CS0019: Operator '&' cannot be applied to operands of type 'int' and 'bool'

TypeScript de yakalar: error TS2363: The right-hand side of an arithmetic operation must be of type 'any', 'number', 'bigint' or an enum type. Ama düz JavaScript'te 4 == 4 önce true'ya, sonra 1'e çevrilir ve kod sessizce çalışır. flags = 0b0011 (ViewCatalog ve PlaceOrder açık, WriteReview kapalı) iken flags & 4 == 4 koşulu 3 & 1 = 1 olur ve ekrana "can write reviews" yazar. Bitwise ifadeleri her zaman parantez içine al: (flags & 4) === 4.

Shift miktarının maskelenmesi. Önce Tahmin Et'teki ikinci sorunun cevabı 1:

int one = 1;
int shift = 32;
Console.WriteLine(one << shift);   // 1
Console.WriteLine(one << 33);      // 2
long oneL = 1;
Console.WriteLine(oneL << 64);     // 1
Console.WriteLine(oneL << 63);     // -9223372036854775808

C# spesifikasyonuna göre int ve uint'te shift miktarının yalnızca alt 5 biti, long ve ulong'da alt 6 biti kullanılır. 32 & 31 = 0 olduğu için 1 << 32 hiç kaydırmaz. x86 ve x64 işlemcilerin shift instruction'ları da sayıyı aynı şekilde maskeler; C# bu davranışı dilin kuralı olarak tanımlamış. JavaScript'te de aynı kural var: 1 << 32 1 verir. Shift miktarı bir değişkenden geliyorsa (örneğin bit numarası veritabanından okunuyorsa) önce aralığını kontrol et.

[Flags] enum'da ikinin kuvveti olmayan değerler. ManageUsers = 3 gibi yanlışlıkla verilmiş bir değer, ViewCatalog ve PlaceOrder'ın birleşimi gibi davranır ve ToString çıktısı da kafa karıştırır. Tek izinleri 1u << n ile, birleşimleri | ile tanımla ve bir testte her tek iznin BitOperations.IsPow2 ile tek bit olduğunu doğrula.

Signed tipte sağa kaydırma beklentisi. Bir hash'in üst bitlerini alıp bucket numarası hesaplarken int ile >> kullanırsan negatif hash'lerde negatif index elde edersin. Ya uint'e çevir ya da >>> kullan.

Küçük Bir Deneme

★☆☆ PermissionBits'e Count(Permission p) ekle ve BitOperations.PopCount kullanmadan, yalnızca x &= x - 1 döngüsüyle yaz. Sonucu PopCount ile karşılaştıran bir test yaz.

★★☆ Bir byte değerinin bitlerini tersine çeviren (0b0000_0001 → 0b1000_0000) bir fonksiyonu yalnızca shift, AND ve OR ile yaz. 256 değerin hepsi için iki kez tersine çevirmenin değeri geri verdiğini test et.

★★★ TypeScript'te 64 bitlik izin değerleri için BigInt tabanlı bir grant, revoke, has üçlüsü yaz. Aynı işlemleri number ile yapan bir versiyonla 40 numaralı bit üzerinde karşılaştır ve hangi satırda bozulduğunu göster.

Bu yazıda bitleri değiştirdik ama bir soruyu açık bıraktık: -16'nın bit düzeni neden 11111111111111111111111111110000? Serinin sonraki yazısı "Integer Temsili: Two's Complement, Overflow, Endianness ve JSON'da Kaybolan long ID" bu soruyla başlıyor; Math.Abs(int.MinValue)'in neden exception fırlattığını, byte sırasının dosya formatlarında ve ağda neden önemli olduğunu ve büyük bir long ID'nin JSON üzerinden frontend'e giderken nasıl sessizce değiştiğini göreceğiz.