Bit Count

อันนี้เป็นแบบ version ทำมือ

เห็นฟังก์ชั่นนี้มันเจ๋งดี ใช้นับจำนวน bit 1 ในเลขฐาน 2 ใช้ constant time อันนี้มันมีบอกหลักการกับพิสูจน์ในเว็บอ่ะ ถ้าสนใจก็ลองดูต่อในเว็บละกัน

int BitCount(unsigned int u)
{
        unsigned int uCount;
        uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
        return  ((uCount + (uCount >> 3)) & 030707070707) % 63;
}

มีอีกอันนึง

int BitCount (unsigned int u)
{
         unsigned int uCount=0 ;
         for(; u; u&=(u-1))
            uCount++;
         return uCount ;
}

Credit : http://tekpool.wordpress.com/category/bit-count/

เพิ่งเจอ...มันมีฟังก์ชั่น สำเร็จรูป

Function __builtin_clz

ฟังก์ชันสำหรับนับจำนวนบิต 0 ที่อยู่ทางซ้ายก่อนจะเจอบิต 1

int __builtin_clz (unsigned int x)

เช่น

__builtin_clz(16);

ซึ่ง 16 ใน unsigned int จะเป็น

00000000 00000000 00000000 00010000

__builtin_clz(16); จึงมีค่า (return ออกมา) เป็น 27

Function __builtin_ctz

ฟังก์ชันสำหรับนับจำนวนบิต 0 ที่อยู่ทางขวาก่อนจะเจอบิต 1

__builtin_ctz(16);

ซึ่ง 16 ใน unsigned int จะเป็น

00000000 00000000 00000000 00010000

__builtin_ctz(16); จึงมีค่า (return ออกมา) เป็น 4

Function __builtin_popcount

ฟังก์ชันสำหรับนับจำนวนบิต 1 ทั้งหมด

__builtin_popcount(16);

ซึ่ง 16 ใน unsigned int จะเป็น

00000000 00000000 00000000 00010000

__builtin_popcount; จึงมีค่า (return ออกมา) เป็น 1

Credit: http://www.go4expert.com/articles/builtin-gcc-functions-builtinclz-t29238/