C++ Dersleri | Bit İşlemleri - Set Bitleri sayma

 C++ bit işlemlerinde bir bit dizesi içerisindeki SET (1) olmuş bitlerin sayısını elde etmek için bir kaç yol izleyebiliriz, basitçe programlama kafasıyla for kullanarak yapılabilir :

int main()
{
	unsigned int a = 1234;     // 0100 1101 0010
	int bitCount = 0;
	for (bitCount = 0; a; a >>= 1)
		bitCount += a & 1LL;
	
	cout << "result=" << bitCount << endl;
}

 result=5 

ne yapmış olduk açıklamaya çalışamadan önce for ne yapıyor onu anlatalım : for 'un ilk ifadesi bir kez çalıştırılır, ikinci ifadesi kontrol edilecek durumu belirler; burada yalnızca a var, bu ne anlama geliyor, bu ifade boolean bir ifade olmalıdır, 0 olmamışsa durumun sağlandığını kabul eder yani 3 5 7 vs diğer tüm sayılar true kabul edilir, yani for 'un bitme şartı a nın sıfır olması durumudur, en son ifadesi de her dönüşte yürütülecek kod ifadesidir, for'u yazmadan for'u da anlatmış olduk kısaca, yazarız ilerde detaylı bir şekilde.

• bitCount = 0    a = 1234 : 0100 1101 0010b    a & 1LL -> 0100 1101 0010 & 1 den +0 oldu
• a >>= 1 -> 0010 0110 1001   a & 1LL den bu sefer 1 geldi bitCount +1 oldu,

yaani her defasında a bir bit sağa kaydırılarak değeri düştü en sondaki biti 1 ise bitCount 1 arttı sıfırsa değişmedi, adımlar tamamlandığında a sıfır oldu ve for çalışmayı durdurdu, bu arada bitCount 5 değerine ulaşmış oldu, dileyenler for 'un içerisinde bitCount 'a değer verdiğimiz satıra bir breakpoint atarak adım adım değerleri izleyebilirler.

Daha basitçe yine for kullanarak; en sağda set edilmiş biti kaldır formuna dayanan şu algoritma da kullanılabilir :

int main()
{
	unsigned int a = 1234;     // 0100 1101 0010
	int bitCount = 0;
	for (; a; ++bitCount)
		a &= (a - 1);
	
	cout << "result=" << bitCount << endl;
}

 result=5 

Burada for için başlangıç koşulu verilmemiş, yine a sıfır değilse devam ediyor, preincrement kullanılmış, bu da önce değer ver sonra aksiyona geç demekti, for içerisinde de en sağdaki biti resetle demiş olduk, bu sayede kaç resetlenecek bit varsa o kadar bitCount++ olmuş olacak.

Son olarak Hamming weight (üzerine tıklayarak detaylarına ulaşabilirsiniz) algoritmasıyla geliştirilen bir fonksiyonla şu şekilde de yapılabiliyor, armut piş durumu :)

unsigned popcount(std::uint64_t x)
{
	const std::uint64_t m1 = 0x5555555555555555; // binary: 0101...
	const std::uint64_t m2 = 0x3333333333333333; // binary: 00110011..
	const std::uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // binary: 0000111100001111
	const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...
	x -= (x >> 1) & m1; // put count of each 2 bits into those 2 bits
	x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits
	x = (x + (x >> 4)) & m4; // put count of each 8 bits into those 8 bits
	return (x * h01) >> 56; // left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}
 
int main()
{
	unsigned int a = 1235;     // 0100 1101 0010
	int bitCount = popcount(a);
	
	cout << "result=" << bitCount << endl;
}

Herkese kolay gelsin!

Önceki konu : Bit Kontrol

Sonraki konu  : Bir Tamsayının 2'nin Kuvveti Olup Olmadığının Kontrol Edilmesi