Bit İşlemleri

Aşağıda bitlerle çalışırken aldığım notlar var. Aslında tüm işlemler temel olarak şöyle yapılıyor.

#define BitSet(arg,posn) ((arg) | (1L << (posn)))
#define BitClr(arg,posn) ((arg) & ~(1L << (posn)))
#define BitTst(arg,posn) BOOL((arg) & (1L << (posn)))
#define BitFlp(arg,posn) ((arg) ^ (1L << (posn)))

1. Okuma İşlemleri
Okuma işlemi verilen sayının belli bir bit aralığını almak içindir. Temel iki yöntem vardır. İlk yöntem shift işlemini kullanır. İkinci yöntem ise mask işlemini kullanır.

LSB okumak için Mask'lamak Shift İşleminden Daha Hızlıdır
Bazen bir sayının ilk N tane LSB bitini okumak isteriz. Sayıyı toplam bit sayısı - N defa sola kaydırarak gereksiz bitlerden kurtulamak ve daha sonra toplam bit sayısı - N defa sağa kaydırarak istediğimiz bitlere erişmek mümkün. Örneğin 64 bitlik bir sayıda LSB 32 bit şöyle okunur.
lower = (64bitvar << 32) >> 32;
Ancak bu işlem yavaştır. Mask'lamak her zaman daha hızlıdır.

Ortadan Bitleri Okumak
Mask tablosu kullanmak en iyi yöntem.

Ortadan Tek Bir Biti Okumak İçin Sola Kaydırmak - Kullanmayın
Mask tablosunu kullanmayı tercih etmek gerekir. Ancak istenirse shift işlemi ile mask dinamik olarak yaratılabilir.

Örnek:

bit (i) = byte & (1U << i)

Ortadan Tek Bir Biti Okumak İçin Sağa Kaydırmak - Kullanmayın
Mask tablosunu kullanmayı tercih etmek gerekir. Ancak istenirse tek bir biti okumak için aşağıdaki gibi yapılabilir.
bit(i) = byte >> i & 0x1

Sağa kaydırırken, signed tipleri kullanmamak gerekir, çünkü C dili sağa kaydırmanın MSB'de bulunan eksi sayı bitini muhafaza edip etmeyeceğini belirtmez. Örneğin 10000000 kaydırılınca 11000000 olmak zorunda değildir. 01000000 de olabilir. Bu yüzden statik analiz araçları şuna benzer bir hata verirler.
"Left hand operand of right-shift operator is a variable of signed int type".

2. Diğer Notlar

Shift İşlemi Sonucu int veya unsigned int'tir - Integer Promotion
C/C++ kullanırken yapılan en büyük yanlışlardan birisi shift işleminin sonucunun shift edilen tip ile aynı olduğunu varsaymak. C Integer Promotion başlıklı yazıya bakınız.

Negate Operatorünün Sonucu int veya unsigned int'tir - Integer Promotion
C/C++ kullanırken yapılan en büyük yanlışlardan birisi shift işleminin sonucunun shift edilen tip ile aynı olduğunu varsaymak. C Integer Promotion başlıklı yazıya bakınız. Açıklama

The result of the ~ operator is the bitwise complement of its (promoted) operand (that is, each bit in the result is set if and only if the corresponding bit in the converted operand is not set). The integer promotions are performed on the operand, and the result has the promoted type. If the promoted type is an " 'unsigned type', the expression ~E is equivalent to the maximum value representable in that type minus E".

BitMask için Unsigned Int Kullanmak
Bitmask değerini tutmak için int kullanmak sakıncalı diye bir not gördüm.

int mask = 10101010101010101010101010101010

Bitmask değerlerini tutmak için unsigned int kullanılmalıymış.

Negatif Sayılar
Bit İşlemleri yazısına taşıdım.

Sağa Kaydırmada Verinin Bit Uzunluğunu Aşmamak
Sağa kaydırılan veri 32 bit uzunluğunda ise, en fazla 31 bit sağa kaydırılabilir. 32 veya üstü bir sayı kadar kaydırma denenirse, sonuç tanımsızdır (undefined). Hatta Intel işlemciler, sağa kaydırma işlemini bile yapmazlar.

Tüm bitleri 1 yapmak
Örnek:

int64_t x = -1 veya uint64_t x = ~0;   

Belli Sayıda bitleri 1 yapmak
Örnek

int32_t x ~( ~0u << n )

Eğer belli bir pozisyondan başlayarak n tane biti 1 yapmak istersek

int32_t x = ~( ~0u << n ) << m

Verilen Biti Temizlemek
Negate operatörünü kullanmak gerekir. Aşağıdaki örnekte sadece 0x40 alanı temizleniyor, diğer alanlarda değişiklik yapılmıyor. Aynı kullanım şeklini BitStream sınıfının Write() metodunda da görebilirsiniz. Örnek:

data &= ~0x40;

data |= 0 << 15 şeklinde bit temizlenemez!.

Verilen Bitleri Tersine Çevirmek
Hiç kullanmam gerekmedi ancak 32 bitlik bir alanın ilk 16 bitini tersine çevirmek için aşağıdaki gibi yapılabilir. XOR kullanılarak 1 olan alan 0, 0 olan alan ise 1 yapılır.

crc = crc ^ ~0U;

FitsBits
Şöyle yaparız.

int fitsBits(int x, int n) {
  int res = -1;
  if(x >= 0){
    res = (x >> (n - 1));
  }
  else if (x < 0){
    res = (~x >> (n - 1));
  }
  return !res;
}

Reverse
Rotate ile karıştırmamalı. 110 gibi bir biti 011 olacak şekilde başını sonuna getirir.

Power of two
unsigned bir değerin ikinin katı olup olmadığını aşağıdaki gibi anlayabiliriz.

(n & (n - 1)) == 0

Is Even or Odd Power of two
n sayısının aşağıdaki sabit ile and'lenmesi sonucu üssü'nün çift olup olmadığını buluruz. Sonuç 0 ise üssü tektir.
n & 0x55555555

Modulus Operatorü Yerine Bitmask
Aşağıdaki örnekte modulus yerine bit işlemi yapılmış.
x++
x = x & 1023 işlemi aslında

x = (x + 1) % 1024 anlamına geliyor.

Java
Bit İşlemleri yazısına taşıdım.

C
C dilinde bir struct içinde bitfield'lar tanımlanabilir. Bitfield signed veya unsigned olabilir.

A bit-field may have type int , unsigned int , or signed int . Whether the high-order bit position of a plain int bit-field is treated as a sign bit is implementation-defined

Signed alan kullanılması aslında anlamlı değil.Aşağıdaki örnekte çıktı olarak 1 yerine -1 alırız.

#include<stdio.h>
int main(){
struct A{
    int a:1;
};
struct A bb;
bb.a=1;
printf("%d",bb.a);//-1 verir
return 0;
}

Bitfield derleyici tarafından integral bir tipin katı olacak şekilde pad'lenir. Örnek:

struct S {
  unsigned char b1:3;  // 3 bits - b1
  unsigned char   :2;  // 2 bits - unused
  unsigned char b2:6;  // 6 bits - b2
  unsigned char b3:2;  // 2 bits - b3
                       // Total: 13 bits
};                     // 3 bits - unused (implicit padding)

BitStream Sınıfı
Endianness byte'tan büyük herhangi bir tipe byte byte erişmeye başlayınca yani pointer arithmetic kullanınca işin içine girer.  Bu yüzden BitStream sınıfında pointer arithmetic yerine bit kaydırma yapılır.
Bit kaydırma işlemi endianness'tan bağımsızdır.

Java
Bit İşlemleri yazısına taşıdım.

Alternatif olarak  String kullanan basit bir BitStream sınıfı ise aşağıda.

String bitStream = Long.toBinaryString (value);
int numBytes = bitStream.length () / 8;
for (int index = 0; index < numBytes; index++){
    int byteIndex = index * 8;
    String singleByte = bitStream.substring (byteIndex , 8);
    StringBuffer buf = new StringBuffer (singleByte);
    singleByte = buf.reverse().toString();
    int byteValue = Integer.valueOf (singleByte,2);
}

C#
Burada hazır bir sınıf var. Ayrıca BitArray sınıfı da işe yarar.

BitArray bits = new BitArray(1000); // lots of bits
bits[1] = true;

C++
Gömülü Proje - BitStream yazısına taşıdım.