Bir tamsayıdaki 1 olan bitlerin sayısını (set bits / popcount) bulan bir fonksiyon yazın.

En çok beklenen cevap Brian Kernighan yöntemidir: x & (x - 1) işlemi en düşük anlamlı 1 bitini sıfırlar. Döngü sadece 1 olan bit sayısı kadar döner.

#include <stdint.h>

unsigned popcount_naive(uint32_t x)
{
    unsigned count = 0;
    while (x) {
        count += x & 1u;
        x >>= 1;
    }
    return count;            /* her zaman en fazla 32 iterasyon */
}

unsigned popcount_kernighan(uint32_t x)
{
    unsigned count = 0;
    while (x) {
        x &= x - 1u;         /* en sağdaki 1'i sil */
        count++;
    }
    return count;            /* 1 bit sayısı kadar iterasyon */
}

Örnek: x = 0b10110000

• 1. adım: 10110000 & 10101111 = 10100000
• 2. adım: 10100000 & 10011111 = 10000000
• 3. adım: 10000000 & 01111111 = 00000000 sonuç 3.

Dallanmasız (SWAR) yöntem

unsigned popcount_swar(uint32_t x)
{
    x = x - ((x >> 1) & 0x55555555u);
    x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
    x = (x + (x >> 4)) & 0x0F0F0F0Fu;
    return (x * 0x01010101u) >> 24;
}

Derleyici yerleşikleri

GCC/Clang'da __builtin_popcount(); C23'te <stdbit.h> içinde stdc_count_ones() vardır. Cortex-M'de doğrudan popcount talimatı olmadığı için derleyici genelde SWAR koduna benzer bir şey üretir.

İlgili kısa sorular

• 2'nin kuvveti mi? x != 0 && (x & (x - 1)) == 0
• En düşük 1 biti izole etmek: x & -x (unsigned için)
• Parite: popcount'un en düşük biti