XOR

• XOR, iki bit birbirinden farklı olduğunda 1 olan bir işlemdir; dışlayıcı OR, eşit olmama, koşullu ters çevirme ve mod 2 toplama/çıkarma kavramlarını tek bir davranışta birleştirerek anlaşılabilir
• Tamsayılar üzerindeki bit düzeyinde XOR, her biti bağımsız işler ve bit bazlı farkı ortaya çıkarır; elde taşımayan ikili toplama gibi davranırken değişme özelliği, birleşme özelliği, 0 birim elemanı ve kendisinin tersi olma özelliklerini korur
• Kriptografide düz metin ile keystream birleştirmek için kullanılır; geçmişte piksel grafiklerinde ise aynı şekli yeniden çizerek silme yöntemiyle bellek ve CPU yükünü azaltmıştır
• Yarım toplayıcı özdeşliği, bit değiştirme, üç XOR ile swap ve Nim oyunundaki kazanma koşulu gibi fark üretip sonra bunu tekrar yok eden hesaplamalarda XOR’un özelliklerinden doğrudan yararlanılır
• Kümelerin simetrik farkından üs 2’li gruplara, nim-sum’a ve GF(2) üzerindeki lineer cebir ile polinomlara kadar uzanır; ayrıca Hamming kodu, CRC, AES, GCM ve Classic McEliece gibi hata tespit/düzeltme ve kriptografi teknikleriyle de bağlantılıdır

---

XOR’un temel anlamı

• XOR, iki giriş biti ve bir çıkış biti olan bir Boole işlemidir; doğruluk tablosu 00→0, 01→1, 10→1, 11→0 şeklindedir
• “exclusive OR” olarak bakıldığında, iki girişten yalnızca biri doğruysa 1 üretir; ikisi de doğruysa 0 olur
• “not equals” olarak bakıldığında a XOR b, a ≠ b ile aynıdır; yani iki Boole değeri farklı olduğunda 1 üretir
• Koşullu ters çevirme olarak bakıldığında, a=0 ise b aynen kalır, a=1 ise b terslenir
  • Aynı nedenle b kontrol girişi kabul edilip a’yı tersleyen yorum da yapılabilir
• Parite açısından bakıldığında, girişlerdeki 1 sayısının tek mi çift mi olduğunu söyler
  • İki bit için a+b mod 2 ile aynıdır
  • a-b mod 2 ile de aynıdır
  • Birden çok değer XOR’landığında, tüm girişlerdeki 1 sayısının tek mi çift mi olduğu anlaşılır

XOR’un cebirsel özellikleri

• XOR, değişme özelliği ve birleşme özelliği taşır
  • a XOR b = b XOR a
  • (a XOR b) XOR c = a XOR (b XOR c)
  • Uzun XOR listelerinde sıra ve gruplayış sonucu etkilemez
• 0, XOR’un birim elemanıdır
  • a XOR 0 = 0 XOR a = a
  • Uzun XOR listelerinde 0 kaldırılabilir
• Her değer, kendisine göre kendi tersidir
  • a XOR a = 0
  • Aynı değişken iki kez geçiyorsa bu iki terim birlikte sadeleşir
  • (a XOR b) XOR b = a örneğinde olduğu gibi, zaten karışmış bir değerden bilinen terimi bir kez daha XOR’layarak çıkarabilirsiniz

Tamsayılarda bit düzeyinde XOR

• Tamsayıların bit düzeyinde XOR’u, iki tamsayıyı ikili biçimde ele alır ve her bit konumunu bağımsız olarak XOR’lar
• Tek bitlik XOR’un özellikleri tamsayılarda da aynen geçerlidir
  • a XOR b = b XOR a
  • (a XOR b) XOR c = a XOR (b XOR c)
  • a XOR 0 = a
  • a XOR a = 0
• Bit düzeyinde XOR, iki tamsayı arasındaki bit bazlı farkı gösterir
  • a=b ise a XOR b = 0
  • a≠b ise en az bir bit farklıdır, dolayısıyla a XOR b ≠ 0
  • Sonuçtaki 1 bitleri, iki girişin farklı olduğu konumları gösterir
• Bit düzeyinde XOR, bir koşullu bit tersleyici olarak da görülebilir
  • Kontrol değerindeki 1 bit konumlarında veri bitlerini tersler
  • ASCII ve onu izleyen bazı kodlamalarda Latin büyük ve küçük harfler yalnızca tek bir bitte farklıdır; bu yüzden karakter değerine 32 ile XOR uygulamak büyük/küçük harfi değiştirebilir
  • Bu kural tüm Unicode karakterleri için geçerli değildir; büyük/küçük harf kavramı olmayan ya da bu kurala uymayan çok sayıda karakter vardır
• Bit düzeyinde XOR, elde taşımayan ikili toplama ile aynıdır
  • Her basamakta yalnızca mod 2 toplama yapılır ve bir sonraki basamağa elde aktarılmaz

Kriptografide XOR

• Kriptografide, düz metinle aynı uzunlukta bir keystream üretilir ve düz metin baytları ya da word’leri bu keystream ile birleştirilerek şifreli metin oluşturulur
• Bu birleştirme adımında genellikle XOR kullanılır
  • Alıcı, aynı keystream’i yeniden XOR’layarak özgün düz metni geri elde edebilir
  • Gönderici ve alıcının aynı işlemi kullanması da küçük bir pratiklik sağlar
• Keystream’in kendisini üretme yöntemi daha karmaşık olabilir
  • one-time pad, tüm mesaj boyutu kadar gerçek rastgele veri kullanır ve kırılamaz; ancak çoğu amaç için son derece kullanışsızdır
  • Genellikle stream cipher ya da counter mode kullanan blok şifreler, küçük bir anahtardan ihtiyaç duyulan uzunlukta keystream üretir
• Bu yöntem, iyi bir keystream olduğunda gizlilik sağlayabilir; ancak mesaj üzerinde oynama yapıldığını tespit eden bütünlük koruması sağlamaz
  • Bütünlük koruması ayrı bir problemdir
  • Acemi kriptosistem tasarımlarında bütünlüğü dışarıda bırakmak yaygın bir hatadır ve daha karmaşık şifreleme şemalarında da yanlış sonuçlara yol açar
• Donanımda XOR, toplamadan daha basittir
  • Toplama, bitler arasında elde yayılımı gerektirir; bu da daha fazla çip alanı ve zaman demektir
  • XOR’da elde olmadığı için özel devrelerde daha ucuza mal olur

XOR çizimi ve piksel grafikleri

• 1980’lerin ev bilgisayarlarında ekran pikseli başına bit sayısı ve RAM sınırlıydı; bu yüzden tüm ekranı iki kopya hâlinde saklamak zordu
• Hareketli nesneler XOR ile çizildiğinde, aynı nesneyi yeniden çizmek orijinal ekranı geri yüklemek için yeterli olur
  • Piksel değeri S ile hareketli nesnenin pikseli M XOR’lanarak C elde edilir; daha sonra aynı M tekrar XOR’lanarak S geri kazanılır
• Birden çok pikselin tek bir bayta packed edildiği ya da bit plane yapısının kullanıldığı ekranlarda, toplama tabanlı birleştirme zahmetlidir
  • Normal toplamada, bir pikselden çıkan elde bir sonraki piksele taşabilir
  • XOR’da hiç elde olmadığı için bu sorun ortaya çıkmaz
• XOR ile çizilen çizgilerde, iki çizginin kesiştiği piksel iki kez terslenir ve arka plan rengine dönebilir; bu da küçük bir kusur gibi görünebilir
  • Bu kusur, bir çizgi silinirken diğer çizgilerin bozulmamasının bedeli olarak kabul edilirdi
• XOR çizimi basit animasyonlar için de elverişliydi
  • Yeni bir çizgi çizip eski bir çizgiyi yeniden çizerek silmek, bir sonraki kareyi oluşturur
  • Ekrandaki tüm pikselleri ya da tüm çizgileri baştan çizmek gerekmediği için bellek ve CPU kullanımı düşüktür
  • 1981 tarihli Qix oyunundaki hareketli çizgi ve ilk GUI’lerde pencere taşıma taslakları bu yöntemle yapılmıştır

Yarım toplayıcı özdeşliği

• Tek bitlik toplamada a+b işleminin düşük biti a XOR b, yüksek biti ise a AND b olur
• Aynı ilişki tamsayıların bit düzeyindeki işlemlerinde de geçerlidir
  • a + b = (a XOR b) + 2 × (a AND b)
  • a XOR b, eldesiz toplanmış değeri; a AND b ise her basamakta oluşması gereken elde bitlerini içerir
• Bu ilişki, yarım toplayıcı özdeşliği olarak görülebilir
  • Donanımsal yarım toplayıcı, iki bitlik toplamanın elde ve düşük bitini AND ve XOR kapılarıyla üretir
  • Bu, tüm tamsayı toplamayı yalnızca basit işlemlerle kurmak anlamına gelmez; sağ taraftaki +, elde yayılımını tamamlar
• Taşma olmadan iki tamsayının ortalamasını almak için bu özdeşlik kullanılabilir
  • Doğrudan a+b yapıp sağa kaydırmak, 33 bitlik toplamın en üst bitini kaybettirebilir
  • carry flag ya da RRX/RCR gibi komutları olmayan veya kullanımı zor CPU’larda (a XOR b) >> 1 + (a AND b) biçimi bir alternatif olabilir
  • Örnek olarak MIPS, RISC-V ve DEC Alpha’da carry flag yoktur; ilk Arm Thumb sürümlerinde de RRX bulunmuyordu
• XOR komutu olmayan CPU’larda bu özdeşlik ters çevrilerek XOR üretilebilir
  • a XOR b = (a + b) − 2 × (a AND b)
  • 1970’lerin Data General CPU’larında AND vardı, ancak bitwise XOR yoktu

Bitlerin ve değerlerin swap edilmesi

• İki biti değiştirme problemi, bitler aynıysa hiçbir şey yapmama; farklıysa iki biti de tersleme problemine indirgenir
• XOR ve shift kullanılarak iki bitin farklı olup olmadığı bulunabilir ve gerekirse her iki konum da terslenebilir
  • diff_all = input XOR (input >> distance) ile belirli bir uzaklıktaki bit çiftlerinin farkı hesaplanır
  • AND ile yalnızca ilgilenilen konumlar seçilir
  • Seçilen farklar diğer konuma kopyalanır ve girişe XOR uygulanarak yalnızca gerektiğinde iki bit birden terslenir
• Aynı uzaklıkta bulunan birden çok bit çiftini aynı anda değiştirmek için de aynı yöntem kullanılabilir
  • Tek bit maskesi yerine birden çok biti içeren maske kullanılır
  • Beneš network, birden fazla aşamada aynı uzaklıktaki çok sayıda çifti yer değiştirerek keyfi permütasyonları ifade edebilir
• Tüm iki değeri değiştiren üç XOR’lu swap da mümkündür
  • a = a XOR b
  • b = b XOR a
  • a = a XOR b
  • Geçici değişken olmadan iki değer yer değiştirir
• Üç XOR’lu swap’ta aliasing problemi vardır
  • Farklı değişkenlerde çalışır
  • Ancak bir dizinin aynı elemanını kendisiyle swap etmeye çalışmak gibi, iki isim aynı depolama konumunu gösteriyorsa değer 0 olabilir

Nim oyunu ve XOR

• Nim, birkaç yığından sırayla bir yığın seçip içinden istenen sayıda, ama en az 1 taş kaldırılan; artık hamle kalmadığında kaybedilen bir oyundur
• Basit Nim sürümünde kaybeden konum, tüm yığın boyutlarının bit düzeyinde XOR’unun 0 olduğu durumdur
• XOR’un 0 olduğu bir konumda, bir yığın boyutunu a değerinden b değerine değiştirmek toplam XOR’u a XOR b kadar değiştirir; a≠b olduğu için sonuç artık 0 olmaz
• XOR’un 0 olmadığı konumda, toplam XOR değeri x içindeki en yüksek 1 bite bakılır; o biti 1 yapan bir yığın seçilip boyutu pile XOR x değerine indirilirse toplam XOR 0 yapılabilir
• Örneğin 12, 10 ve 3 boyutlu yığınlar ikili olarak 1100, 1010, 0011’dir ve XOR sonuçları 0101 olur
  • En büyük yığın olan 12’ye 0101 XOR uygulandığında değer 9’a düşer
  • Kazandıran hamle, 12’den 3 taş kaldırıp 9’a indirmektir

XOR’a benzeyen matematiksel yapılar

• Küme kuramındaki simetrik fark X∆Y, bir elemanı yalnızca iki kümeden tam olarak birinde bulunuyorsa içeren işlemdir
  • Bir elemanın kümede bulunup bulunmamasını Boole değeri olarak görürseniz, simetrik fark XOR ile aynıdır
  • Bu yüzden değişme ve birleşme özellikleri gibi XOR özelliklerini paylaşır
• Grup kuramında üs 2’li grup, her elemanı kendi tersi olan gruptur
  • Böyle grupların işlemi birleşme özelliğini sağlar ve standart bir alıştırma olarak değişme özelliğini de sağladığı gösterilir
  • Aynı elemandan iki tane yan yana geldiğinde birbirini götürmesi XOR’a benzer
  • Tüm üs 2’li gruplar, {0,1} değerli bazı fonksiyonların bit düzeyinde XOR’u gibi anlaşılabilir
• Sprague-Grundy analizinde birçok impartial game konumuna bir Grundy number atanır
  • Birden çok alt oyunun birleşimi olan composite konumun Grundy number’ı, bileşen oyunların Grundy number’larının bitwise XOR’u ile hesaplanır
  • Oyun kuramında negatif olmayan tamsayıların bitwise XOR’una bazen nim-sum denir
• GF(2) cismi, yalnızca 0 ve 1 elemanlarına sahip sonlu bir cisimdir
  • Toplama ve çıkarma XOR gibi çalışır
  • Çarpma AND gibi çalışır
  • Bu yüzden a AND (b XOR c) = (a AND b) XOR (a AND c) eşitliği geçerlidir

GF(2) üzerinde lineer cebir ve hata düzeltme

• GF(2) üzerindeki vektör ve matrisler, bileşenleri 0 veya 1 olan yapılardır; vektör ya da matris toplamı bileşen bazında XOR’dur
• Bir vektör v ile matris M çarpımı, v içindeki 1 bileşenlerinin seçtiği M sütunlarını XOR ile toplamakla aynıdır
• Hata düzeltme kodları, m bitlik mesajları daha uzun n bitlik codeword’lere genişleterek bazı bit hatalarını tespit etmeyi ya da düzeltmeyi sağlar
  • Geçerli codeword’ler arasında çok sayıda bit farkı varsa, az sayıdaki bit hatası başka bir geçerli codeword’e dönüşmez
  • İki geçerli codeword en az k bitte farklıysa, k’den az hata tespit edilebilir; k/2’den az hata ise en yakın codeword bulunarak düzeltilebilir
• Lineer kodlar, GF(2) üzerinde generator matrix ve check matrix kullanır
  • sender, generator matrix ile m bitlik mesajı n bitlik codeword’e genişletir
  • receiver, check matrix ile alınan codeword’ün geçerli olup olmadığını denetler ve hata varsa syndrome elde eder
  • Aynı hata deseni, mesajdan bağımsız olarak aynı syndrome’u üretir
• Hamming code, code uzunluğu n değeri 2^d−1 olduğunda görülen bir örnektir
  • n=15 ise 15 bit konumu 0001’den 1111’e kadar 4 bitlik sıfır olmayan sayılarla numaralandırılır
  • receiver, değeri 1 olan bitlerin indekslerini XOR’lar; sonuç 0 ise geçerli bir codeword vardır
  • Tek bir bit terslenirse XOR sonucu doğrudan terslenen bitin indeksini verir; böylece lookup table olmadan 1 bitlik hata düzeltilebilir
  • 15 bitlik Hamming code, 11 bit veri taşır ve 4 biti hata düzeltmeye ayırır

GF(2) polinomları, CRC ve daha büyük sonlu cisimler

• GF(2) üzerindeki polinomlar, katsayıları 0 veya 1 olan biçimsel polinomlardır; toplama, aynı derecedeki katsayıları XOR’lamakla aynıdır
• Polinom çarpımı, normal polinomlardaki gibi kısmi çarpımlar oluşturup katsayıları mod 2’ye indirerek yapılır
  • Bu gösterimi bit dizisi olarak düşünürseniz, tamsayı çarpımına benzer; ancak kısmi çarpımlar birleştirilirken normal toplama yerine eldesiz XOR kullanılır
  • x86, CLMUL dâhil carryless multiplication komutları sunar; Arm ise polynomial multiplication ailesi komutları sağlar
• CRC, GF(2) polinom bölmesinin kalanını checksum olarak kullanır
  • Gönderilen mesaj bit dizisi büyük bir M polinomu olarak görülür ve uzlaşılan P polinomuna bölümden kalan M mod P saklanır
  • Ethernet ve benzeri ağ paketlerinin doğrulanmasında kullanılır
  • CRC hata düzeltmez, yalnızca tespit eder; çoğu iletimin normal olduğu ve nadiren bit dönmesi ya da gürültü oluşan durumlar için uygundur
• Daha büyük sonlu cisimler, GF(p) üzerindeki polinomların bir irreducible polynomial Q ile bölümünden kalan yapılar olarak kurulabilir
  • Q polinomunun derecesi d ise yeni sonlu cisim p^d elemana sahip olur
  • p=2 durumunda irreducible polynomial değerleri bit desenleri olarak tamsayı biçiminde yazılabilir ve ilgili diziler OEIS A014580 içinde kayıtlıdır
• 2’nin kuvveti büyüklüğündeki sonlu cisimler birçok kriptografi tekniğinde karşımıza çıkar
  • 2^8 büyüklüğündeki sonlu cisim, AES ve Twofish’in temel yapı taşlarından biridir
  • 2^128 büyüklüğündeki sonlu cisim, toplu şifreleme ile bütünlük korumasını birleştiren GCM’de kullanılır
  • 2’nin kuvveti büyüklüğündeki sonlu cisimler, bazı elliptic-curve cryptography türlerinde ve post-quantum yöntem olan Classic McEliece’in decoding algoritmalarında da yer alır

[GN⁺]

Hacker News yorumları

• Benim sevdiğim lanetli XOR tekniği XOR çift bağlı liste: https://en.m.wikipedia.org/wiki/XOR_linked_list
  Her düğüm, sonraki/önceki işaretçileri ayrı ayrı saklamak yerine ikisinin XOR'lanmış tek bir değerini saklar. Elbette geçerli bir işaretçi değildir; ama gezinirken önceki düğüm işaretçisiyle birleşik işaretçiyi XOR'layınca sonraki düğüm işaretçisi çıkar ve iki yönlü gezinme de mümkün olur. Yasadışı gibi hissettiriyor.

  • Normal bir çift bağlı listeye kıyasla, yalnızca öğenin adresi elinizde olduğunda ya da ekleme/silme işlemlerinde bile kararlı kalan bir yineleyiciniz olduğunda o öğeyi kaldırabilme yeteneğini kaybedersiniz. Oysa bu, çoğu zaman çift bağlı liste kullanmanın temel nedenidir.
    Daha az temel bir kusur olarak, standarda sıkı sıkıya uyan C'de XOR bağlı liste yazmak epey zahmetlidir. Standart, aynı işaretçiyi tamsayıya dönüştürdüğünüzde aynı tamsayının elde edileceğini garanti etmez; bu yüzden pratikte normalleştirilmiş tamsayıya dönüştürülmüş bir sürümü korumak için her şeyi uintptr_t yapmak gerekir.
  • 64 bit işlemcilerde bile çoğu uygulama için 4 GB'tan az RAM yeterli sayılırsa, yalnızca 32 bit adres alanı kullanarak depolama alanını daha da azaltabilirsiniz.
    Hatta 16 bit yakın/göreli işaretçiler bile mümkün olabilir. Veri odaklı tasarımla iyi uyum sağlayabilir; 64K öğelik bloklar tutup içerideki öğeleri uint16 indeksleriyle göstermek gibi.
  • Bunu yaparsanız çöp toplayıcı bundan hoşlanmayacaktır. Ya da en azından bu veri yapısını çöp sanacaktır.
  • Bu tekniği neden kullanmak isteyeceğinizi merak ediyorum.
  • Bu, işaretçiden ziyade iki işaretçi arasındaki farkı saklamaktan pek farklı değil. Farkı saklasanız da elbette iki yönlü gezinme mümkün olur.

• Atlanan bir şey var. XOR aynı zamanda 3-wise bağımsız doğrusal hash fonksiyonudur; bu yüzden Boole fonksiyonu çözümlerinin olasılıksal yaklaşık tekdüze örneklemesi ve sayımı için kullanılabilir. Gerçekten faydalıdır ve olasılıksal olsa da kanıtlanmış sayılar veren sayaçlar oluşturmakta kullanılır. Daha anlaşılır bir açıklamayı burada yazmıştım: https://www.msoos.org/2018/12/how-approximate-model-counting...
  Temelde her seferinde çözüm uzayını neredeyse tam olarak yarıya indirir. Bu yüzden, örneğin 10 çözüm kalana kadar XOR koşulları eklemeye devam edersiniz; eklenen XOR sayısı k ise 10'u 2^k ile çarparsınız. Her seferinde yarıya indiği için 10 civarına kadar çok hızlı ulaşır ve iyi ölçeklenir.
  İlgili makaleler https://arxiv.org/abs/1306.5726 ve https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf adreslerinde; araçlar da https://github.com/meelgroup/approxmc ve https://github.com/meelgroup/unigen adreslerinde. Son model sayma yarışmasında, kesin bir sayaçla birleştirildiğinde diğer rakipleri açık ara geride bıraktı; slaytlar https://mccompetition.org/assets/files/2024/MC2024_awards.pd... adresinde.

• En sevdiğim XOR anekdotlarından biri, Oxide, Joyent ve Sun'dan Bryan Cantrill'in şu sunumda https://speakerdeck.com/bcantrill/oral-tradition-in-software... ve şu videoda https://www.youtube.com/watch?v=4PaWFYm0kEw anlattığı hikâye.
  Linklere tıklamanıza gerek kalmasın diye özetleyeyim: Sun'dayken meslektaşı Roger Faulkner ile C'de mantıksal XOR olmamasının nedenini konuşmuşlar; Faulkner bunun kısa devre değerlendirme yapılamamasından kaynaklandığını söylemiş, Brian ise bunu tuhaf bulmuş. Bunun üzerine Roger, Dennis Ritchie'ye e-posta ile sormuş ve Ritchie, Faulkner'ın haklı olduğunu doğrulamış. Cantrill'in anlatımı komik ama asıl şaşırtıcı olan, doğrudan ilgili kişiye sorabilmiş olmaları.

  • DMR şaşırtıcı derecede nazik, yardımsever ve ulaşılabilir biriydi. 80'lerin ortasında lisans öğrencisiyken, Unix v6'nın PDP-11 olmayan Interdata 8/32'ye yapılan “ilk” portunu okudum ve mimariyle ilgili daha fazla bilgi var mı diye [e-mail] adresine rastgele bir e-posta attım.
    O zamanlar Google yoktu, üniversite kütüphanesinde de kaynak yoktu; birkaç gün sonra fiziksel adresimi sordu ve birkaç hafta sonra komut kümesi özet kılavuzunun bir kopyası posta kutuma geldi. IBM 360 ailesini andırıyordu ve hâlâ duruyor.
  • C'de mantıksal XOR var; o da != operatörü. Diğer mantıksal operatörlerden farklı olarak argümanları tekil bir doğru değerine normalize etmek gerekir ve C'nin Boole dönüşümü deyimi olan !! ile iyi uyum sağlar.
  • “Kısa devre değerlendirme yapılamaması”nın bir operatör eklemeye neden engel olduğunu anlamıyorum. Biri açıklasa iyi olur.
  • İlgili konu 37:18'de başlıyor.
  • C'de 40 yılı aşkın süredir bitsel XOR operatörü ^ vardı: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

• Otomobil emojisini 0x20 ile XOR’layınca, yani “küçük harfe çevirince” yaya giremez emojisi olduğunu bugün öğrendim. Tesadüf olamayacak kadar cuk oturuyor gibi; bunun bilinçli olup olmadığını bilen var mı merak ediyorum
  Bunu fazla zorlayınca otomobil emojisinin küçük harfinin “yaya giremez” tabelası olduğu gibi tuhaf bir fikir de mümkün oluyor

  • HN’nin emoji kaldıran yorum işleyicisinden kaçınmak için şöyle doğrulanabilir:
    >>> from unicodedata import lookup, name
>>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
'NO PEDESTRIANS'
  • Otomobilin küçük harfi go-kart olurdu gibi
  • :tada: → :tophat:, :rocket: → :mountain_cableway: de mümkün

• XOR’u anlatırken kullanılabilecek iyi bir gerçek dünya benzetmesi, evin merdivenindeki ışık anahtarı. Aşağıda bir anahtar, yukarıda bir anahtar vardır ve ikisi de aynı ışığı kontrol eder
  Başta ikisi de kapalı konumdadır; alttaki anahtarı açınca ışık yanar. Merdivenden çıkıp üstteki anahtarı açınca iki anahtar da “açık” konumda olmasına rağmen ışık söner. Yalnızca bir anahtar “açık”, diğeri “kapalı” olduğunda ışık yanar; diğer durumlarda söner

  • Bizim ofisteki elektrikçi kablolamayı yanlış yapmış olabilir. Odada iki anahtar var ama düşününce XOR’dan çok AND kapısı gibi çalışıyor. Salondaki iki anahtar kesinlikle XOR gibi çalışıyor

• Bu mantık fonksiyonu için yaygın olarak XOR, yani “dışlayıcı OR” adının kullanılmasından gerçekten hoşlanmıyorum. Çünkü neredeyse her zaman asıl anlamı “2’ye göre kalanlı toplam”, yani parite; dışlayıcı OR değil
  “2’ye göre kalanlı toplam”/parite ile “dışlayıcı OR” farklı mantık fonksiyonlarıdır ve yalnızca giriş operandı 2 olduğunda tesadüfen çakışırlar. Çünkü 2 veya daha küçük tek sayı yalnızca birdir
  Giriş 3 veya daha fazla olduğunda çoğu kişinin XOR dediği şey aslında tek sayıda giriş 1 olduğunda 1 olan paritedir. Buna karşılık dışlayıcı OR, giriş 3 veya daha fazla olduğunda yalnızca tam olarak bir giriş 1 ve kalanların tümü 0 ise 1 olan fonksiyondur
  Bilgisayar donanımında parite, dışlayıcı OR’dan çok daha önemlidir. Başlıca nedeni, 2’ye göre kalanlı toplamanın daha büyük sayıların toplanmasını gerçekleştirmek için bir yapı taşı olarak kullanılmasıdır. Buna karşılık matematikte dışlayıcı OR, pariteden çok daha önemlidir
  Örneğin bir yüklemin bir kümenin bazı elemanları, tüm elemanları veya tek bir elemanı için doğru olduğunu ifade eden niceleyiciler sırasıyla OR, AND ve dışlayıcı OR’a dayanır. Doğal dildeki “or” her zaman kapsayıcı OR ya da dışlayıcı OR anlamına gelir; birçok programcının XOR dediği parite anlamına gelmez
  Programlamada dışlayıcı OR mantık fonksiyonunu hesaplamak nadirdir, ama program davranışını açıklarken sıkça kullanılır. Örneğin select/case/switch bileşik deyiminde birinci deyim ya da ikinci deyim ya da üçüncü deyimden birinin çalışması veya union/toplam tip değişkeninin mevcut değerinin alabileceği tipleri açıklamak gibi

  • Elektrik teknolojisi sembol standardı IEC 60617 bu kısmı doğru ele alır. XOR kapısı =1, parite kapısı 2k + 1 olarak gösterilir. Ama PCB veya FPGA için devre tasarım yazılımı kullanırken beklediğinizden farklı bir şey alıp yine de yakalanabilirsiniz
  • Matematikte sözünü ettiğin şeye tekil varlık niceleyicisi denir ve kendi sembolü ∃! vardır
  • Giriş 3 veya daha fazla olduğunda “dışlayıcı OR”un tam olarak yalnızca bir tane 1 olduğunda doğru olduğu açıklamasının dayanağa ihtiyacı var
  • Bu yorum, ana makalede de ele alınıyor

• Kademlia dağıtık karma tablosu da var: kademlia distributed hash table. Büyük fikir, her düğümün [0, 2^m) aralığında rastgele bitler alması ve mesafenin XOR ile tanımlanması. Tüm ağı bilmeden X’ten Y’ye bilgiyi hızlıca gönderecek dağıtık bir algoritma bulmak isteniyor
  Yalnızca matematiğe bakarak çalıştığı kanıtlanabilir, ama benim sevdiğim görsel sezgi şöyle. Başlangıç düğümü X’in k düğümünü bulmak istediğini varsayalım. “X-mesafe ağacı”nı, yaprak indeksleri 0, 1, 2... olan ikili bir ağaç olarak tanımlayalım; her yaprağa da X’e olan mesafeyi göstermek için X^leaf_index etiketi verelim. Örneğin dist(x, x) = x^x = 0 olduğundan özgün düğüm X etiketi en soldaki 0 yaprağında yer alır
  [2^i, 2^(i+1)) aralığı X-mesafe ağacındaki bir alt ağaçtır. k’nin mesafesinin bu aralığa düştüğü biliniyorsa, onun içindeki herhangi bir Y düğümünü yaklaşık komşu olarak sorgularız
  Hangi Y seçilirse seçilsin, Y-mesafe ağacında sonuç öneki her zaman X-mesafe ağacında seçilen [2^i, 2^(i+1)) alt ağacının bir permütasyonu olur. Daha kesin olarak labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)) şeklinde görülebilir. İndeksler mesafeye göredir, ama etiketler değişebilir
  Chord gibi diğer dağıtık karma tablolarıyla karşılaştırma için matematiksel ve deneysel olarak çok daha sıkı kaynaklar var. Ama bu görsel sezgi, Kademlia’nın “simetrisi”nin ne olduğunu; herkesin kendi yerel komşularına ve kendi alt ağaçlarına sahip olduğu hissini verir
  Buna karşılık Chord, iki yönlü uygulansa bile 2 kat bellek ister ve uygulaması da daha riskli görünür; bu düzeyde bir “yalıtılmışlık” elde etmek zordur. S boyutlu komşu kayan penceresi sürekli hareket eder ve her bit için 2^m farklı komşu vardır. Komşuların çoğu benzer görünse bile temiz değildir
  Kademlia’da 1 + 2 + 4 ... + 2^m-1 komşu vardır ve bütünü düzenlidir

• Merak edenler için ekleyeyim, bu kişi Simon Tatham's Portable Puzzle Collection’daki Simon Tatham. Bilmiyorsanız çevrimdışıyken sıkılınca denemeye değer
  Lisede bunlarla çok zaman harcadım: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

  • Ayrıca PuTTY’yi yapan Simon Tatham da odur: https://www.chiark.greenend.org.uk/~sgtatham/putty/
  • En iyi yanı, Mayın Tarlası algoritmasının tahmin gerektirmeyen oyunlar üretmesi

• Günümüzde birçok özel amaçlı optimizasyon çözücüsü, örneğin Ising Machine, XOR problemini benchmark olarak kullanıyor. Aslında birden çok XOR maddesini çözmek Gauss eliminasyonuyla polinom zamanda mümkün olduğu için pratik değeri biraz düşük; ancak çözücülerin hepsi üstel ölçeklenme gösterdiğinden performansı ölçmek için iyi bir yöntem oluyor.
  İkinci ilginç uygulama McEliece kriptosistemi ile ilgili. 70'lerin bir açık anahtarlı şifreleme sistemi; bugünlerde kuantuma dayanıklılık nedeniyle yeniden ilgi görüyor. Şifre çözme saldırısı, bir XOR denklem kümesinin çözümünü bulma problemi; bu da polinom zamanda çözülebiliyor, ancak Hamming uzaklığının açık anahtarda yer alan belirli bir sayıya eşit olması koşulu ekleniyor.

• TI-83 programlamak için Z80 assembly öğrenirken makine kodundaki her 1 bayt önemliydi. Çünkü hesap makinesinin toplam depolama alanı yalnızca 24KB idi.
  Ana akümülatör yazmacı ayı 0'a ilklendirmek için LD a, 0 yerine XOR a kullanırdık. Matematik komutlarında a otomatik operand olduğu için XOR a, ayı kendisiyle XOR'lar ve tüm komut yalnızca 1 bayttır. Buna karşılık 0'ı açıkça aya yüklemek için literal 0'ın opcode'a girmesi gerektiğinden LD a, 0 2 baytlık bir komuttur.