Boş zamanlarımda C öğrenmeye çalışıyorum ve diğer diller (C#, Java, vb.) aynı konsepte (ve genellikle aynı operatörlere) sahip ...
Merak ettiğim şey, temel düzeyde, bit kaydırma (<<
, >>
, >>>
) ne işe yarar, hangi sorunları çözmeye yardımcı olabilir ve virajın etrafında hangi sorunlar gizlenir? Başka bir deyişle, tüm güzellikleriyle bit kaydırma için mutlak bir başlangıç rehberi.
Bit kaydırma operatörleri tam olarak adlarının ima ettiği şeyi yapar. Bitleri kaydırırlar. İşte farklı kaydırma operatörlerine kısa (ya da çok kısa olmayan) bir giriş.
>>
aritmetik (veya işaretli) sağa kaydırma operatörüdür.>>>
mantıksal (veya işaretsiz) sağa kaydırma operatörüdür.<<
sola kaydırma operatörüdür ve hem mantıksal hem de aritmetik kaydırma ihtiyaçlarını karşılar.Bu operatörlerin tümü tamsayı değerlerine uygulanabilir (int
, long
, muhtemelen short
ve byte
veya char
). Bazı dillerde, int
ten küçük herhangi bir veri tipine shift operatörlerini uygulamak, işleneni otomatik olarak bir int
olarak yeniden boyutlandırır.
<<<`nin bir işleç olmadığına dikkat edin, çünkü gereksiz olacaktır.
Ayrıca C ve C++'ın sağa kaydırma operatörleri arasında ayrım yapmadığını unutmayın. Sadece >>
operatörünü sağlarlar ve sağa kaydırma davranışı işaretli tipler için tanımlanmıştır. Yanıtın geri kalanı C# / Java operatörlerini kullanır.
(gcc ve clang/LLVM dahil tüm ana akım C ve C++ uygulamalarında, işaretli tiplerde >>
aritmetiktir. Bazı kodlar bunu varsayar, ancak bu standardın garanti ettiği bir şey değildir. Yine de tanımlanmamış değildir; standart, uygulamaların bunu bir şekilde tanımlamasını gerektirir. Ancak, negatif işaretli sayıların sola kaydırılması *tanımlanmamış bir davranıştır (işaretli tamsayı taşması). Bu nedenle, aritmetik sağa kaydırmaya ihtiyaç duymadığınız sürece, bit kaydırma işleminizi işaretsiz tiplerle yapmak genellikle iyi bir fikirdir).
Tamsayılar bellekte bir dizi bit olarak saklanır. Örneğin, 32 bit int
olarak saklanan 6 sayısı şöyle olacaktır:
00000000 00000000 00000000 00000110
Bu bit örüntüsü bir konum sola kaydırıldığında (6 << 1
) 12 sayısı elde edilir:
00000000 00000000 00000000 00001100
Gördüğünüz gibi, rakamlar bir pozisyon sola kaymış ve sağdaki son rakam sıfır ile doldurulmuştur. Sola kaydırmanın 2'nin kuvvetleriyle çarpmaya eşdeğer olduğunu da not edebilirsiniz. Yani 6 << 1
, 6 * 2
ye ve 6 << 3
, 6 * 8
e eşdeğerdir. İyi bir optimizasyon derleyicisi, mümkün olduğunda çarpma işlemlerini kaydırma işlemleriyle değiştirecektir.
Lütfen bunların döngüsel vardiyalar olmadığını unutmayın. Bu değerin bir konum sola kaydırılması (3,758,096,384 << 1
):
11100000 00000000 00000000 00000000
3,221,225,472 ile sonuçlanır:
11000000 00000000 00000000 00000000
Sondan kaydırılan "rakam" kaybolur. Etrafına sarılmaz.
Mantıksal sağa kaydırma, sola kaydırmanın tersidir. Bitleri sola taşımak yerine, basitçe sağa taşırlar. Örneğin, 12 sayısının kaydırılması:
00000000 00000000 00000000 00001100
bir konum sağa kaydırırsak (12 >>> 1
) orijinal 6`yı geri alırız:
00000000 00000000 00000000 00000110
Böylece sağa kaydırmanın 2'nin kuvvetleriyle bölmeye eşdeğer olduğunu görüyoruz.
Ancak, bir kaydırma "kayıp" bitleri geri alamaz. Örneğin, bu kalıbı kaydırırsak:
00111000 00000000 00000000 00000110
sola doğru 4 konum (939,524,102 << 4
), 2,147,483,744 elde ederiz:
10000000 00000000 00000000 01100000
ve sonra geri kaydırarak ((939,524,102 << 4) >>> 4
) 134,217,734 elde ederiz:
00001000 00000000 00000000 00000110
Parçalarımızı kaybettikten sonra orijinal değerimizi geri alamayız.
Aritmetik sağa kaydırma aynen mantıksal sağa kaydırma gibidir, ancak sıfırla doldurmak yerine en anlamlı bitle doldurur. Bunun nedeni, en anlamlı bitin işaret biti veya pozitif ve negatif sayıları birbirinden ayıran bit olmasıdır. En anlamlı bitle doldurarak, aritmetik sağa kaydırma işareti korur.
Örneğin, bu bit desenini negatif bir sayı olarak yorumlarsak:
10000000 00000000 00000000 01100000
Elimizde -2,147,483,552 sayısı var. Bunu aritmetik kaydırma ile 4 konum sağa kaydırdığımızda (-2,147,483,552 >> 4) bize verecektir:
11111000 00000000 00000000 00000110
ya da -134,217,722 sayısı.
Böylece, mantıksal sağa kaydırma yerine aritmetik sağa kaydırmayı kullanarak negatif sayılarımızın işaretini koruduğumuzu görüyoruz. Ve bir kez daha, 2'nin kuvvetleriyle bölme işlemi yaptığımızı görüyoruz.
Diyelim ki elimizde tek bir bayt var:
0110110
Tek bir sol bit kaydırma uygulamak bize ulaşır:
1101100
En soldaki sıfır baytın dışına kaydırılmış ve baytın sağ ucuna yeni bir sıfır eklenmiştir.
Bitler devredilmez; atılırlar. Bu, 1101100'ü sola kaydırıp sonra sağa kaydırırsanız, aynı sonucu geri alamayacağınız anlamına gelir.
N ile sola kaydırmak 2N ile çarpmaya eşdeğerdir.
N ile sağa kaydırmak (eğer ones' complement kullanıyorsanız) 2N ile bölmeye ve sıfıra yuvarlamaya eşdeğerdir.
Bit kaydırma, 2'nin kuvveti ile çalışmanız koşuluyla, delicesine hızlı çarpma ve bölme için kullanılabilir. Neredeyse tüm düşük seviyeli grafik rutinleri bit kaydırma kullanır.
Örneğin, eskiden oyunlar için 13h modunu (320x200 256 renk) kullanırdık. Mod 13h'de video belleği piksel başına sıralı olarak yerleştirilirdi. Bu, bir pikselin konumunu hesaplamak için aşağıdaki matematiği kullanacağınız anlamına geliyordu:
memoryOffset = (row * 320) + column
O zamanlar hız çok önemliydi, bu yüzden bu işlemi yapmak için bit kaydırma kullanırdık.
Ancak, 320 ikinin kuvveti değildir, bu nedenle bunu aşmak için birlikte 320 yapan ikinin kuvvetinin ne olduğunu bulmamız gerekir:
(row * 320) = (row * 256) + (row * 64)
Şimdi bunu sola kaydırmaya dönüştürebiliriz:
(row * 320) = (row << 8) + (row << 6)
Nihai sonuç için:
memoryOffset = ((row << 8) + (row << 6)) + column
Şimdi, pahalı bir çarpma işlemi yerine iki bit kaydırmayı kullanmamız dışında, daha önce olduğu gibi aynı ofseti elde ederiz... x86'da şöyle bir şey olurdu (not, assembly yapmayalı uzun zaman oldu (editörün notu: birkaç hatayı düzelttim ve 32 bitlik bir örnek ekledim)):
mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]
; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov
Toplam: Bu zamanlamalara sahip eski CPU'da 28 döngü.
Vrs
mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6; 2
shl di, 8; 2
add di, ax; 2 (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]
Aynı eski CPU'da 12 döngü.
Evet, 16 CPU döngüsünden tasarruf etmek için bu kadar çok çalışırdık.
32 veya 64 bit modunda, her iki sürüm de çok daha kısa ve hızlı hale gelir. Intel Skylake (bkz. http://agner.org/optimize/) gibi modern sıra dışı yürütme CPU'ları çok hızlı donanım çarpımına (düşük gecikme ve yüksek verim) sahiptir, bu nedenle kazanç çok daha azdır. AMD Bulldozer ailesi, özellikle 64 bit çarpma için biraz daha yavaştır. Intel CPU'larda ve AMD Ryzen'de, iki kaydırma biraz daha düşük gecikme süresine sahiptir, ancak çarpmadan daha fazla talimat vardır (bu da daha düşük verime yol açabilir):
imul edi, [row], 320 ; 3 cycle latency from [row] being ready
add edi, [column] ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column], in 4 cycles from [row] being ready.
vs.
mov edi, [row]
shl edi, 6 ; row*64. 1 cycle latency
lea edi, [edi + edi*4] ; row*(64 + 64*4). 1 cycle latency
add edi, [column] ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column], in 3 cycles from [row] being ready.
Derleyiciler bunu sizin için yapacaktır: gcc, clang ve MSVC'nin return 320*row + col;
]2 optimizasyonunu yaparken shift+lea'yı nasıl kullandığına bakın.
Burada dikkat edilmesi gereken en ilginç şey, x86'nın küçük sol kaydırmalar yapabilen ve aynı zamanda add
komutu gibi performansla toplayabilen bir kaydırma ve ekleme komutuna (LEA
) sahip olmasıdır. ARM daha da güçlüdür: herhangi bir komutun bir operandı ücretsiz olarak sola veya sağa kaydırılabilir. Bu nedenle, 2'nin kuvveti olduğu bilinen bir derleme zamanı sabiti ile ölçeklendirme, bir çarpmadan bile daha verimli olabilir.
Tamam, modern günlere geri dönersek... şimdi daha kullanışlı bir şey, iki 8 bitlik değeri 16 bitlik bir tamsayıda saklamak için bit kaydırma kullanmak olacaktır. Örneğin, C#'da:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
C++'da, iki 8-bit üyeli bir struct
kullandıysanız derleyiciler bunu sizin için yapmalıdır, ancak pratikte her zaman yapmazlar.
Bir sorun, aşağıdakilerin uygulamaya bağlı olmasıdır (ANSI standardına göre):
char x = -1;
x >> 1;
x şimdi 127 (01111111) veya hala -1 (11111111) olabilir.
Pratikte, genellikle ikincisi olur.