[퀴즈-2010/03/18] 워드카운트

이번에는 지난주 문제입니다. 이 문제는 milkelf님이 출제했습니다.

문제의 요는 다음과 같습니다.
word에 들어있는 1비트가 몇개인지 구하라입니다.
만약 9가 입력으로 들어오면 1001이므로 1은 2개가 있는 것입니다.
1000*30개의 입력에 대해서 수행하며 시간이 가장 빠른 사람이 이기는 룰입니다.
언어는 C로 제한됩니다.

기본으로 주어진 함수는 다음과 같습니다.

1. int binw(int v)
2. {
3.  int i;
4.  int x=v;
5.  for(i=0;i<32;i++) {
6.   if (x&1) sum+=1;
7.   x = x >> 1;
8.  }
9.  return x;
10. }

즉, 이 함수를 각자 최대한 성능향상을 꾀하는 문제입니다.

재미있는 것은 정말 답이 다양하게 나오더군요.

*. 비트연산을 테이블로 대체하는 분...
*. 1000개의 입력이 30번 반복되는 문제라, 답을 저장해서 쓰는 분.
*. inline, register, 함수없애기 등의 노력을 하는 분.
*. 그외 다음과 같이 알고리즘을 바꾸는 후보들도 있었습니다.

1. while(x) {
2.  sum+=1;
3.  x = x & (x-1);
4. }

아래와 비슷한 답도 있었으나 여기 설명이 더 자세하고 이해하기 편한듯하여 따로 paste합니다. 이 방법이 가장 빨랐다네요...
http://www.experts-exchange.com/Programming/Algorithms/Q_23629662.html

1. unsigned int v; // count bits set in this (32-bit value)
2. unsigned int c; // store the total here
3. static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
4. static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
5.  
6. c = v - ((v >> 1) & B[0]);
7. c = ((c >> S[1]) & B[1]) + (c & B[1]);
8. c = ((c >> S[2]) + c) & B[2];
9. c = ((c >> S[3]) + c) & B[3];
10. c = ((c >> S[4]) + c) & B[4];

여러분은 뭘로 푸셨을 것 같나요? :)