NoSyu의 주저리주저리 :: 2008년 1학기 시스템 프로그래밍

bitCount.

사실 이 함수는 제 스스로 힘으로 풀지 못했습니다.

왜냐하면 이 함수를 만드는 방법을 이미 공부하였기 때문입니다.

그래서 아무리 다른 방법을 떠올려봐도 생각이 나지 않아 좌절하였습니다.OTL....

따라서 이 함수에 대해서는 딱히 드릴 말씀이 없습니다.ㅜㅜ

이 함수를 배운 곳

헨리 워렌, 김종규 역, <해커의 즐거움>, 피어슨 에듀케이션 코리아, 2006, pp. 102

/*
* bitCount - returns count of number of 1's in word
*   Examples: bitCount(5) = 2, bitCount(7) = 3
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 40
*   Rating: 4
*/
int bitCount(int x) {
    /* 0x55 = 0101 0101
     * 0x33 = 0011 0011
     * 0x0f = 0000 1111
     *
     * ex)
     * 0001 1011
     * (x & 0x55) + ((x >> 1) & 0x55) => 0001 0001 + 0000 0101 = 0001 0110
     * (x & 0x33) + ((x >> 2) & 0x33) => 0001 0010 + 0000 0001 = 0001 0011
     * (x & 0x0f) + ((x >> 4) & 0x0f) => 0011 + 0001 = 0000 0100
     *
     * x = 00
     * (x & 0x55) + ((x >> 1) & 0x55) => 00
     * x = 01
     * (x & 0x55) + ((x >> 1) & 0x55) => 01
     * x = 10
     * (x & 0x55) + ((x >> 1) & 0x55) => 01
     * x = 11
     * (x & 0x55) + ((x >> 1) & 0x55) => 10
     * I consider each two bits and divide half.
     * If bit is 1 then there is one 1bit.
     * If bit is 0 then there is zero 1bit.
     *
     * x = 0110
     * (x & 0x33) + ((x >> 2) & 0x33) => 0001 + 0010 = 0011
     * I consider each four bits and divide half.
     * And add high two bits and low two bits.
     *
     * (x & 0x0f) + ((x >> 4) & 0x0f)
     * It's same above except deal about four bits and divide half.
     *
     * I read and studied about this procedure on a book a few weeks ago.
     * So I can't find other method.OTL...
     * Therefore professor said to us,
     * "It's wasting time if you read other code or answer before you solve the problem."
     * Of course, That book said use 0x55555555, 0x33333333, 0x0f0f0f0f, 0x00ff00ff, 0x0000ffff.
     * But I can't that constant, So I use shift operator(>>).
     *
     * 20080402 | 20080404
     *
     * I make some variable means to constant over 0xff.
     * Then I reduced operation number less than 40.
     * But I remain old code because of explaination.
     *
     * 20080406
     */
/*
    int copy_variable_x = x; // copy x.
    int sum = 0; // return value. sum

    x = (x & 0x55) + ((x >> 1) & 0x55); // check each two bits and add 1 bit in first byte
    x = (x & 0x33) + ((x >> 2) & 0x33); // check each four bits and add 1 bit in first byte
    sum += (x & 0x0f) + ((x >> 4) & 0x0f); // check each eight bits and add 1 bit in first byte
    x = copy_variable_x >> 8; // move second byte to first byte
    x = (x & 0x55) + ((x >> 1) & 0x55); // check each two bits and add 1 bit in second byte
    x = (x & 0x33) + ((x >> 2) & 0x33); // check each four bits and add 1 bit in second byte
    sum += (x & 0x0f) + ((x >> 4) & 0x0f); // check each eight bits and add 1 bit in second byte
    x = copy_variable_x >> 16; // move third byte to first byte
    x = (x & 0x55) + ((x >> 1) & 0x55); // check each two bits and add 1 bit in third byte
    x = (x & 0x33) + ((x >> 2) & 0x33); // check each four bits and add 1 bit in third byte
    sum += (x & 0x0f) + ((x >> 4) & 0x0f); // check each eight bits and add 1 bit in third byte
    x = copy_variable_x >> 24; // move forth byte to first byte
    x = (x & 0x55) + ((x >> 1) & 0x55); // check each two bits and add 1 bit in forth byte
    x = (x & 0x33) + ((x >> 2) & 0x33); // check each four bits and add 1 bit in forth byte
    sum += (x & 0x0f) + ((x >> 4) & 0x0f); // check each eight bits and add 1 bit in third byte

return sum; // return count number
*/

    int const_0x55555555 = 0x55 + (0x55 << 8); // value = 0x00005555
    int const_0x33333333 = 0x33 + (0x33 << 8); // value = 0x00003333
    int const_0x0f0f0f0f = 0x0f + (0x0f << 8); // value = 0x00000f0f
    int const_0x00ff00ff = 0xff + (0x0f << 16); // value = 0x00ff00ff
    int const_0x0000ffff = 0xff + (0xff << 8); // value = 0000ffff

    const_0x55555555 = const_0x55555555 + (const_0x55555555 << 16); // value = 0x55555555
    const_0x33333333 = const_0x33333333 + (const_0x33333333 << 16); // value = 0x33333333
    const_0x0f0f0f0f = const_0x0f0f0f0f + (const_0x0f0f0f0f << 16); // value = 0x0f0f0f0f

    x = (x & const_0x55555555) + ((x >> 1) & const_0x55555555); // check each two bits and add 1 bit in 4bytes
    x = (x & const_0x33333333) + ((x >> 2) & const_0x33333333); // check each four bits and add 1 bit in 4bytes
    x = (x & const_0x0f0f0f0f) + ((x >> 4) & const_0x0f0f0f0f); // check each eight bits and add 1 bit in 4bytes
    x = (x & const_0x00ff00ff) + ((x >> 8) & const_0x00ff00ff); // check each sixteen bits and add 1 bit in 4bytes
    x = (x & const_0x0000ffff) + (x >> 16); // add high sixteen bits and low sixteen bits.

return x; // return x
}

크리에이티브 커먼즈 라이선스