Sorting 문제에 대해서 CS전공자라면 분명 학부 시절에 배울 것이고, 비 전공자라고 해도 컴퓨터를 만지는 사람이라면 한번즈음은 다루어 보는 문제 일 것입니다. 일반적으로 Sorting 알고리즘의 복잡도는 얼마라고 배웠나요? 

글은 9월 중순에 써놨는데 공개는 딱 9월 말에 하게 되네요. (그 사이에 한 후배가 문제를 풀어서 다행이라고 생각합니다.) Ln(N)문제는 다음 주 주말 즈음 해서 결과를 올리도록 하겠습니다. 답변에 실제 매번 루프를 도는 잘못된 비트 분석 방법과 아래 알고리즘에 대한 실제 속도 차이를 평가한 도표도 같이 추가 하려했지만, 그 도표는 개인적인 사정으로 인해 아무래도  Ln(N) 퀴즈를 풀이 하면서 올려야겠습니다.

1bit counter of O(m)

정답 부터 바로 공개 해볼까요?

이 걸로 문제는 해결 됩니다.
이 정답 코드에 앞서서 문제를 해결 하기 위해서는 어떻게 접근 해야 하는지 알아보도록 하겠습니다. 이 문제에서 1이라는 값을 가지는 bit만 센다는 것을 다른 방식으로 해석하여 문제를 전개 해야 합니다. 1 값을 가지는 bit를 센다는 것은 한번에 한번씩 1값을 가지는 bit를 제거하고 총 제거된 횟수를 세는 문제와 동일합니다. 문제가 수렴하기 위한 Base condition은 하나씩 제거된 bit string이 어떤 bit도 1의 값을 가지지않을때 이겠군요.

그러면 문제의 솔루션은 찾았습니다. 그런데 이것을 어떻게 구현 할지에 대한 고민이 생기겠지요. 우리는 한번에 하나씩 1의 값을 가지는 bit를 제거하는데 두 가지의 접근이 가능합니다.

1. 처음 Borrow가 발생하는 bit 이후에는 모두 negation 되는 특징.
2. 2의 보수(Complement) 특징

 

All bits negate after borrow

첫번째 해결 법으로 만들어진 해답이 처음 공개된 코드입니다. 아래 그림을 보면 좀 더 그 특징을 알 수 있습니다.
 

 
이 특징을 가지고 1의 값을 가지는 bit 하나만 어떻게 제거 할 수 있을까요. 코드를 보셨으니 아시겠습니다만 &연산을 통해서 Borrow가 생기는 bit 이하를 모두 제거 할 수 있습니다.

  
  이렇게 -1 후  &연산을 하는 동작이 한번의 알고리즘 복잡도에서 이야기하는 기본 유닛(Basic Unit)이 됩니다. 기본 유닛 동작후의 결과가 0이 될때 까지 반복하면 정확히 1의 값을 가진 bit 만큼만 루프를 돌면서 알고리즘을 정상 종료 할 수 있습니다. 1의 값을 가지는 bit 수를 우리는 m이라고 정의 했으니 알고리즘의 복잡도는 O(m)이 되겠군요.

 

Usage of 2's complements

2의 보수를 이용하는 방법은 2의 보수 정의를 알면  Borrow를 통해 풀이하는 방법 보다 좀 더 직관적입니다. 2의 보수 특징을 사용해서 문제를 푼 후배는 딱 2명이 있습니다.  우선 2의 보수라는 것은 어떤 특징을 가지는지 봐야 겠군요. 2의 보수는 원래의 값과 보수의 값을 더 했을때 0이 되는 것이 그 정의입니다. 일반적으로 우리는 이 정의를 만족 하기 위해서 원래 bit값의 negation(1의 보수) 에다가 1을 더해 줍니다.

다시 말해 2의 보수는 LSB중에 가장 가까운 Bit만 1이고 그 이상의 MSB들은 모두 역수인 특징을 가지게 됩니다. 이것을 이용하면 특정한 Bit string이 주어졌을때 우리는 LSB에서 가장 가까운 Bit만 값이 1인 String을 얻을 수 있습니다.

이렇게 2의 보수를 통해서 LSB부터 1인 비트들을 클리어 해가면 정확히 1이 존재 하는 횟수만큼만 그 Bit String을 조작 할 수 있습니다. 이렇게 2의 보수를 이용하여 정답을 구 할 수 있는데 이를 구현 하는것은 사실 몇가지 방법이 있을 수 있습니다. Clear를  취하는 방법이 다를 수 있으니까요.

 

Tailing Counter Zero

테일링 카운터 제로는 1번 문제를 풀었다고 하면 쉽게 이해가 됩니다. 일단 앞서 말씀 드린 2의 보수의 성격을 이용해서 Rightmost 에서 Leftmost로 가는 비트중 제일 먼저 나오는 1만이 남고 나머지는 모두 0가 됩니다. 그러면 이를 LCZ를 이용하여 나오면 1의 값을 가지는 비트가 존재 하는 것 까지의 비트수를 세어 주고 그것을 총 사이즈(integer가 32로 가정했음) 32에서 빼주면 값을 구할 수 있습니다.

후배님들이 두 가지의 해답을 제시 했는데 하나는 31 - LZC( n & (~n + 1) ) 이고 다른 하나는 32 - LZC( n & (~n + 1) )였습니다. 하나 차이지만 이것은 매우 중요한 문제입니다. 왜냐하면 부연 설명에 제시된 LZC는 실제 LZC 인스트럭션과 달리 1을 포함한 비트 까지의 비트수를 반환 합니다. 다시 말해서 0001이라고 하면 실제 LZC는 3을 반환하고 퀴즈의 LZC는 4를 반환하도록 제시 되어 있습니다. 즉, 31에서 값을 빼는 해답은 좀 더 엄격히 말하면 틀린 것이지요. 아마  문제의 해답을 원래 알고서 썼다기 보다는  LZC를 원래 알고 있어서 원래 리턴하는 값으로 문제를 풀었다고 믿고 있습니다.


문제의 원본
2008/08/30 - [For craft/Quiz] - Operation of Bit string

이전 퀴즈에서 우리는 1bit를 count  하는데 1이 존재하는 만큼의 알고리즘 복잡도를 가지는 O(M)의 1bit counter에 대한 문제를 만나봤습니다. 약속을 9월 말까지 공개 하기로 했으니 좀 더 지켜보지요. 문제를 5분만에 푸나 한달만에 푸나 푸는 것에 의미가 있으니깐요. 한달만에라도 풀었다면 몇번의 반복을 통해서 문제 풀이시간 5분에 근접 할 수 있습니다. 꼭 풀어 보시기 바랍니다.

관련글
 2008/08/30 - [For craft/Quiz] - Operation of Bit string


1bit counter of O(M) 의 문제 풀이 방식의 Wosrt case

 오늘은 같은 문제에 대해서 조금 다른 방향으로 접근 해보려 합니다.
1bit counter of O(M) 의 문제 풀이 방식(참조 : "Operation of bit string")은 분명 한 bit를 쉬프트 해가며 bit string을 구성하고 있는 bit수 N 만큼의 루프를 돌면서 정보를 취하는 단순한 알고리즘 보다 효율적인면에서 충분히 유리합니다. 그런데 이 알고리즘의 worst case는 없을까요? 이 알고리즘의 worst case는 bit수 M이 전체 bit string의 size인 N과 같아 질때입니다. unsigned int 타입을 쓰고 이 타입이 32bit라고 가정할 때 1bit counter of O(M) 의 문제 풀이 방식이 1의 값을 가진 bit수 만큼만 효율적인 단위 동작을 한다고 하여도 worst case에서는 결국 32번 돌아야 합니다.

 이 worst case 시나리오는 충분히 실현될 가능성이 높습니다.
 예전의 퀴즈에서 들었던 예처럼 bit string이 캐시 모듈에서 사용된다고 가정해보죠. 각 bit가 특정 위치의 데이터의 유효성을 가르키기 때문에 처음에 모든 bit string들은 0으로 채워 져 있을 것이고 1bit counter of O(M) 의 문제 풀이 방식은 충분히 빠르게 동작 할 것입니다. 하지만 이 bit string은 시간이 지날 수록 모든 bit의 값이 1인 bit string으로 바뀌어 갈 것입니다. 왜냐면 계속 유효한 데이터를 저장 함으로써 스냅샷인 bit string도 1로 계속 채워 질테니깐요.
 이후에 이 캐시 모듈을 참조 하는 경우 1bit counter of O(M) 의 문제 풀이 방식의 코드는 매번 32번의 루프를 돌게 됩니다.
 우리는 이 알고리즘의 worst case recovery를 아래와 같이 precondition check를 넣어서 개선 할 수 있습니다.

bitmap table

우리는 흔히 bitmap table과 같이 특정한 범위의 값을 bit string으로 표현합니다. 너무나 흔히 쓰이는 것이기 때문에 좀 지루하시긴 하겠지만 일단 퀴즈가 나가기 전에 이 퀴즈의 쓰임새부터 설명 하는 것이 맞을 것이라 생각하여 간단하게 bitmap table 또는 bit string의 표현예를 아래 그림과 같이 들었습니다.
이러한 bit string들은 많은 곳에서 유용하게 쓰입니다. 가장 흔한 방법은 0과 1로써 유효성을 표현하여 큰 사이즈의 데이터를 작게 표현하는 방법입니다. 예를 들어서 캐시나 스토리지등에서 현재 DRAM또는 레지스터에 있는 정보가 유효한지를 나타내기 쓰입니다. 4Byte짜리 값은 총 32개의 Entry 정보 유효성을 표시 할 수 있습니다.

 

위의 그림에서는 유효한 Entry가 앞에서 6번째부터 3개입니다. 이러한 예제 말고도 우리는 이러한 bit string을 프로토콜을 표현할 때도 사용합니다. 스토리지등에서 한개의 기본 연산 Entry가 512 byte이므로 4byte짜리 unsigned int타입의 변수 하나는 16 KByte 크기의 스냅샷을 생성 할 수 있습니다. 우리가 일반적으로 128GByte의 하드를 쓰고 있지요? 그러면 이 하드에 대한 스냅샷은 8Mbyte 사이즈를 가지는 배열, 즉 unsigned int타입의 2만개면 충분한 것이지요.
 8Mbyte 사이즈의 배열 하나로 128GByte를 관리 하지만 실제 특정 섹터에 값이 존재 하는지 아닌지를 파악하기 위해서는 bit 하나 하나를 다 뒤져야 합니다. 당연히 알고리즘에 따라 상당한 속도 차이를 가지게 되겠지요.

Bit string을 쓰면서 흔하게 겪게 되는 몇 가지 연산

그러면 이러한 bit string을 분석할 때는 어떠한 방법을 쓰겠습니까? 대부분 처음부터 loop를 돌면서 하나씩 정보들을 찾아가게 됩니다. 4byte로 구성된 bit를 모두 loop하기 위해서는 32번의 iteration이 필요하겠지요. 그런데 이런 bit string을 쓰면서 우리는 몇 가지 흔한 문제를 접하게 됩니다. 아래는 unsigned int 타입의 변수 하나를 기준으로 그 안에서의 동작을 의미합니다. 예를 들어 1번의 경우는 unsigned int 타입의 변수 안에서 값이 1인 bit인 총 갯수를 이야기 하는 것이지요.

1. 1 bit의 총 개수
2. 0bit의 총 개수
3. MSB 부터 처음 1이 나타 날 때 까지의 0의 총 개수
4. LSB부터 MSB로 가면서 처음 1이 나타낼 때 까지의 0의 총 개수.

1,2번의 경우 32번 루프를 돌면서 1일 때를 찾으면 몇 개의 1이 있는지 알 수 있겠죠. 하지만 좀 더 효율적으로 하기 위해서 실제 32Byte에서 1의 개수가 존재 하는 만큼만 비교 연산(time complexity of basic unit)을 하는 방법은 어떤 것이 있을까요. 이것이 첫 번째 Quiz입니다. 매번 루프를 도는 것이 결국 O(n) 수준 이기 때문에 별 것 아닐 것이라 생각 할 수 있지만 캐시와 같은 모듈이 매번 자신이 가지고 있는 캐시 중 유효한 메모리 세그먼트의 개수를 파악해야 한다면 그 오버헤드는 정말 존재하는 크기때문에 1의 개수만큼 Iteration만큼 도는 것이 유리할 것입니다.

Leading Zero Counter and Tailing Zero Counter

정말 내고 싶은 Quiz는 3번과 4번입니다. 우리는 일반적으로 3번을 하나의 Instruction으로 해결 할 수 있습니다. 대부분의 MCU들은 LZC와 같은 Leading Zero Counter 인스트럭션을 제공합니다. IBM계열의 경우도 cntlzd라는 이름으로 double word까지 3번의 경우에 대한 0을 인스럭션 한번에 개수를 return해줍니다. 이 것은 inline으로 선언하여 어셈블러상에서 O(1) 시간 안에 해결하게 해줍니다.
 그런데 4번과 같이 Tailing Zero Counter의 경우는 어떻게 해야 할까요. 이 또한 루프를 32번 돌지 않고 몇 개의 인스트럭션 만으로 해결 하고 싶은데 대부분 LZC만 제공하고 4번의 경우는 제공을 하지 않습니다. 이것이 두 번째 Quiz입니다.

Quiz 정리

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

두 개는 모두 실무작업 때 자주 사용할 수 있는 간단한 연산입니다. 해답을 찾으신 후배님들은 덧글 달아주세요. 기간은 9월 말까지. 해답을 찾으신 후배님들은 제가 저녁 식사 및 술을 Treat합니다.(메모리사업부 제외)

부연 설명