Webmaster Destek Forumu

Yarınların için bir şey yapmazsan, ölene dek Alarm kurmaya mahkumsun !
İletişim
  • Duyuru; Sizde hemen Üye Olup Sorunuzu Sorabilirsiniz, katılım ve kullanım tamamen Ücretsizdir!

Bit Manipülasyonları ile Satranç Karesinin Rengini Bulma

Panther

Forum Üyesi
Katılım
18 Eki 2022
Mesajlar
50
Puanları
0
Yaş
33
Konum
istanbul
Leetcode'da gezinirken basit, tatlı bir probleme denk geldim. İzninizle problemi ve Bit Manipülasyonlarını kullanarak yaptığım çözümü paylaşmak istiyorum:

Problem: Size "coordinates" adında, satranç karesinin yerini gösteren bir string veriyoruz. Alttaki satranç tahtasını referans alabilirsiniz:

screenshot-2021-02-20-at-22159-pm.png


Eğer verilen kare beyaz ise "true", değilse "false" değerini döndürmeni istiyoruz.

Örnek 1:
Input: coordinates = "a1"
Output: false
Açıklama: Üstteki satranç tahtasından da görebileceğiniz üzere, "a1" karesi siyah. Bu yüzden false döndürülüyor.

Örnek 2:
Input: coordinates = "h3"
Output: true
Açıklama: Üstteki satranç tahtasından da görebileceğiniz üzere, "h3" karesi beyaz. Bu yüzden true döndürülüyor.


Şimdi her şeyden önce, izlenilecek yolu şu şekilde bulabiliyoruz:

"a" ve "h" arasındaki tüm karakterleri bu ikisi dahil olmak üzere 1'den 8'e kadar numaralandırırsak ve kareleri bu şekilde bulmaya çalışırsak elimize güzel bir sonuç geçiyor;
Eğer elde ettiğimiz sonuç çift ise siyah kareyi, tek ise beyaz kareyi buluyoruz yani. Örneğin:

a1 karesini bulmak istiyoruz diyelim, "a" karakterine 1 rakamını verdik, sonraki karakter olan 1 ile a karakterinin değerini topladığımızda sonuç 2 oluyor. Çift olduğu için karenin siyah olduğunu söyleyebiliyoruz.

Yaptığım çözüm (C#):

Kod: Tümünü Seç Tümünü Kopyala
Kod:
public class Solution {
    public bool SquareIsWhite(string coordinates) {
        return (coordinates[0] & 1) != (coordinates[1] & 1);
    }
}

Bit manipülasyonunu nasıl kullandığımı söylemeden önce bit manipülasyonlarının nasıl işlediğine bir göz atalım. Birkaç operatörümüz var bu işlemler için;

Kod: Tümünü Seç Tümünü Kopyala
Kod:
& = Bitwise AND
| = Bitwise OR
^ = Bitwise XOR
~ = Bitwise NOT
<< = Bitwise Sola Kaydırma
>> = Bitwise Sağa Kaydırma

Programlamadaki genel kullanımın aksine, bu operatörlerle değişkenleri ikilik tabanında değiştirebiliyoruz. Bu da bize çok daha esnek bir kullanım, çok daha hızlı derleme gibi artılarla yansıyor. Tek problemi, okuması ve yazması biraz zor. Ancak elde ettiğiniz hız karşısında kesinlikle değiyor.

Konunun içinde tüm operatörlerin nasıl işlediğine girmeyeceğim. Matematikte mantık konusuna hakimseniz zaten and, or, xor operatörlerine kolayca alışırsınız. Şu anlık sadece AND operatörünün nasıl işlediğini anlatmam yeterli, çünkü yazdığım kodda bir tek onu kullandım.

And işlemi, iki değişkeni ikilik tabanda alt alta koyuyor, sıralı dizilerden ikisi de 1 olan bir bit varsa, onu 1 döndürüyor. Haricinde tamamen 0 döndürüyor.
Örneğin 10110001 ile 00101001 bitlerini AND işlemine tabii tutalım;

Kod: Tümünü Seç Tümünü Kopyala
Kod:
10110001
00101001
&
-----------
00100001


Şimdi "coordinates[0] & 1" ifadesinin ne işe yaradığına bakalım.

String'in ilk karakterini alıyor, bitwise olarak 1 ile AND işlemine tabi tutuyor. Yani şu şekilde; "a1" inputunu girseydik, şöyle bir işlem yapacaktı.

"a" karakterinin ikilik tabanda gösterimi 01100001. AND işlemine tabi tuttuğum bir diğer ifade ise "1". Bilgisayar şöyle bir işlem yapıyor:

Kod: Tümünü Seç Tümünü Kopyala
Kod:
01100001
00000001
&
-----------
00000001

Yani bu şu işe yarıyor: Eğer karakterin son biti 1 ise sonucu 1 döndürüyor, değilse 0 döndürüyor.

Aynı işlemi "1" ifadesi için de yapıyor. 1 sayısının gösterimi de 00110001.

Kod: Tümünü Seç Tümünü Kopyala
Kod:
00110001
00000001
&
-----------
00000001

Eğer bu AND'lerden topladığımız iki ifade eşitse, sonucumuz çift demektir. Yani karemiz siyah demektir.
Biz siyah kareyi değil de, beyaz kareyi aradığımız için eşitliği değil; eşitsizliği arıyoruz. bu yüzden kodumuz şuna dönüşüyor:

Kod: Tümünü Seç Tümünü Kopyala
return (coordinates[0] & 1) != (coordinates[1] & 1);

Eğer çözümü denemek ya da kendi çözümünüzü üretmek istiyorsanız diye problemin linkini aşağıya bırakıyorum:

 
Üst