Software blog에 bit string에 관한 퀴즈(원제:Operation of Bit string)가 올라왔다.
사내 동료들에게 술과 밥을 걸고 낸 문제인 것 같다. 괜시리 도전하고 싶은 욕망에 종이에 긁적이다가 이렇게 블로그에 결과를 올려본다.
내 블로그가 워낙 방문객에 뜸한 블로그라 내 답변을 이렇게 올려도 위 블로그의 동료들에게 노출되지 않을 것 같다.(안습 ㅜㅜ)

프로그래밍을 하다보면 bit 연산을 많이 다루게 된다. 특히 시스템 프로그램이나 네트워크 및 각종 프로토콜에 관련한 프로그래밍에서는 빠질 수 없는 부분이다. 그 중에서 위 블로그에서 몇가지를 설명하면서 문제를 내었다.

(From. Software blog)
  1. Bit string에서 특정 비트의 값이 몇 개나 존재 하는지를 알아내는 데 있어서 O(n)이 아니라 O(m)의 시간 안에 찾아내는 방법을 설명하세요(단 m은 특정한 값을 가진 bit수)
  2. Tailing Zero Counter를 LZC를 사용하여 O(1)에 가깝게 구현하세요.

대부분의 MCU에 LZC (Leading Zero Counter)라는 인스트럭션을 제공한다는 것은 처음 알았다.
사실 어떻게 사용하는지도 알지 못한다. ^^;
수소문해서 사용하는 법을 익혀봐야겠다. 어셈블리 코드를 C코드 내에 삽입해 본적이 없어서 개념도 잡히지 않는다.

나머지는 각설하고 자세한 내용과 문제, 그리고 힌트는 위의 블로그(Software blog)에서 참고하길 바라고, 내가 생각한 답은 아래와 같다. (참고로 2008년 9월 1일 현재 아무에게도 검증받지 못했다.)

전제. LZC라는 인스트럭션을 C에서 함수로 사용 가능하다고 가정하고 작성한 코드이다.
(LZC 함수는 MSB로부터 첫번째 1이 나타나는 bit의 위치를 되돌려 준다. Software blog의 문제 참조.)
int LZC(unsigned int bitString);

당연 함수인자는 구하고자하는 bitString이고 반환 되는 값은 비트 MSB에서 LSB로 가며 처음 1이 나오는 위치입니다. 만약 0001 이라는 비트가 들어간다고 가정하면(실제로는 32Bit지만) 4를 return 하겠지요.

(From. Software blog)

1번 답. Bit string에서 특정 비트의 값이 몇 개 존재하는지 구하는 함수
//-----------------------------------------------------------------
//
// bit string 내에서 1의 개수를 구하는 함수
//
//-----------------------------------------------------------------
int CountOne(unsigned int bits)
{
  int nCount = 0;
  int nPos   = 0;

  while( (nPos = LZC(bits)) > 0 )
  {
    bits <<= nPos;
    nCount++;
  }

  return nCount;
}


//-----------------------------------------------------------------
//
// bit string 내에서 0의 개수를 구하는 함수
//
//-----------------------------------------------------------------
int CountZero(unsigned int bits)
{
  int nCount = 0;
  int nPos   = 0;

  while( (nPos = LZC(bits)) > 0 )
  {
    bits <<= nPos;
    nCount += (nPos - 1);
  }

  return nCount;
}

2번 답. Tailing Zero Counter를 구하는 함수(LSB에서부터 첫번째 1이 나오는 곳의 비트 위치를 구하는 함수)
Idea. Bit string을 뒤집은 후 LZC함수를 이용한다.
//-----------------------------------------------------------------
//
// Bit string을 뒤집는 함수(32 bit에 한하여 동작)
//
//-----------------------------------------------------------------
unsigned int ReverseBitString(unsigned int bits)
{
  bits = ((bits & 0x55555555) << 1 ) | ((bits & 0xAAAAAAAA) >> 1 );
  bits = ((bits & 0x33333333) << 2 ) | ((bits & 0xCCCCCCCC) >> 2 );
  bits = ((bits & 0x0F0F0F0F) << 4 ) | ((bits & 0xF0F0F0F0) >> 4 );
  bits = ((bits & 0x00FF00FF) << 8 ) | ((bits & 0xFF00FF00) >> 8 );
  bits = ((bits & 0x0000FFFF) << 16) | ((bits & 0xFFFF0000) >> 16);

  return bits;
}

//-----------------------------------------------------------------
//
// Tailing Zero Counter를 구하는 함수
//
//-----------------------------------------------------------------
int TZC(unsigned int bits)
{
  return LZC(ReverseBitString(bits));
}

덧1. 언제가 사용할 일이 있을 것 같아서 정리해 보았습니다.
덧2. 위의 방법이 가장 좋은 방법인지는 모르겠습니다. 혹시 더 좋은 아이디어가 있으시면 댓글 남겨 주시기 바랍니다.
덧3. 방금(2008년 9월 1일 오후 1시 37분) 본 글이 정답이 아님을 알았습니다. 1번 문제는 LZC 함수를 사용하지 않고 기본 연산자만 이용해서 풀 수 있다고 합니다. 1번을 풀면 2번도 접근하기가 편하다고 하네요. ^^;