게시판에 아무 글이나 써보고 싶어서 무슨 글 쓸지 고민하던 중에 최근에 공부해서 알게 된 내용을 적어보기로 했음.

반말하면 예의없어보일거같아서 존댓말쓸까 했는데 그냥 디씨의 분위기를 따라갈게.

내가 보고 있는 C언어 책의 연습문제를 풀던 중에 이런 문제를 만났음.

(a) 비트열에서 1의 갯수를 세는 프로그램 작성:

예를 들어 1100 이 주어지면, 1이 2개 있으니까, 결과는 2

비트연산자랑 반복문을 써서 (a) 는 어떻게든 했는데

for (비트열 길이)

if (이번 자리가 1이면)

count++;

다음 문제인 (b)는 어떻게 접근을 해야될지 모르겠어서 검색을 해봤음.

(b) 똑같은 일을 하는데 이번에는 반복문 없이 작성 ㅋㅋ

찾아보는 과정에서, 재귀적으로 1의 갯수를 세는 코드를 봤는데 내 생각엔 이게 문제가 의도한 방법인 것 같기도 하고 또 상식적인 접근인 것 같음.

근데 "비상식적인" 방법들도 있는거임 ㅋㅋ 이해해보려고 몸부림을 쳐봐도--물론 머릿속에서--잘 모르겠어서 그냥 레딧에 질문글을 올림...

(비트열의 1의 갯수를 세는 문제를 뭐라고 일컫는지, 그리고 그 방법/구현에는 어떤 것들이 있는지는 위에 있는 하이퍼링크를 참고)

내가 이해를 못했던 문제의 함수는 아래와 같이 생겼다.

int BitCount(unsigned int u) {

unsigned int uCount;

uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);

return ((uCount + (uCount >> 3)) & 030707070707) % 63;

}

출처: https://web.archive.org/web/20151229003112/http://blogs.msdn.com/b/jeuge/archive/2005/06/08/hakmem-bit-count.aspx

근데 다행히 어떤 고마우신 분께서 댓글로 친절한 해설을 달아주신 덕분에 조금이나마 이해를 할 수 있게 되었다.

그리하여, 저 함수에 대해 내가 이해한 바를 설명하는 것이 이 글의 목표가 되겠다.

지금 여기서, n이 3개의 비트로 이루어진 숫자라고 하자. 즉

n = 2² * a₂ + 2¹ * a₁ + 2⁰ * a₀

여기서 a₂, a₁, a₀은 비트라는 점으로부터

a₂, a₁, a₀ = 0 또는 1

[예시] 5 = 101₍₂₎ = 2² * 1 + 2¹ * 0 + 2⁰ * 1 = 4 + 0 + 1

나아가, n의 비트를 왼쪽으로 한 칸, 그리고 두 칸 밀은 숫자를 생각하고,

그것들을 각각 n >> 1 그리고 n >> 2라고 하자. 따라서,

n >> 1 = 2¹ * a₂ + 2⁰ * a₁

n >> 2 = 2⁰ * a₂

[예시]

5 >> 1 = 10₍₂₎ = 2¹ * 1 + 2⁰ * 0 = 2

5 >> 2 = 1₍₂₎ = 2⁰ * 1 = 1

이때, 다음이 성립하는 것은 분명하다.

n - (n >> 1) - (n >> 2) = a₂ + a₁ + a₀

[증명]

항등식이므로, 좌변이 우변으로 이행됨을 보여주면 충분하다.

n - n >> 1 - n >> 2

= (2² * a₂ + 2¹ * a₁ + 2⁰ * a₀)

- (2¹ * a₂ + 2⁰ * a₁)

- (2⁰ * a₂) 정의에 의해

= 2² * a₂ - 2¹ * a₂ - 2⁰ * a₂

+ 2¹ * a₁ - 2⁰ * a₁

+ 2⁰ * a₀ 동류항끼리 정리

= 4 * a₂ - 2 * a₂ - 1 * a₂

+ 2 * a₁ - 1 * a₁

+ 1 * a0 2의 제곱을 계산

= (4 - 2 - 1) * a₂

+ (2 - 1) * a₁

+ 1 * a₀ 분배법칙

= a₂ + a₁ + a₀

이것이 원하던 답이며, 또한 마땅히 보여져야 할 것이었다.

※ (참고) 항등식의 증명법

일반적으로 어떤 등식이 항등식인 것을 증명하는 데에는, 식의 연산 법칙을 이용하는데,

「한쪽 변을 다른 쪽 변으로 변형한다.」

「양변을 각각 변형하여 똑같은 식으로 한다.」

「양변의 차가 0이 됨을 보인다.」

등의 방법에 따르면 됩니다.

출처: 수학독본 1권 163페이지 (한길사)

이러한 사실을 머릿속에 상기한 채로, 이제 32비트 숫자를 고려하자.

우리의 전략은 32비트 숫자를 11개의 부분으로 나눈 뒤, 각 부분마다 1이 몇 개 있는지 셈한 결과를 다 더해서 최종적인 결론을 얻어내는 것이다.

그 최종적인 결론이란, 환언하면, 32비트로 된 숫자가 총 몇 개의 1로 이루어져 있는지, 다시 말하면 길이가 32인 비트열에 총 몇 개의 1이 포함되어 있는지를 알아내는 것이다.

그리고 이 때, 한 부분에 1이 몇 개 있는지 세는 방법이 바로 위에서 논의한 n - n >> 1 - n >> 2 이다.

왜냐하면, 정의에 의해 a₂, a₁, a₀는 0 또는 1의 값을 가지므로, a₂ + a₁ + a₀의 결과는 곧 3비트에서의 1의 갯수가 된다.

뭔가 마법같이 느껴지지만 (나만 그런가?) 그렇게 느껴지는 이유는 아마도 수를 진법으로 표기하는 것에 너무 익숙한 나머지 어떤 수를 이루는 개개의 수들을 그것이 자리로서 가지는 의미를 무시하고 개별적으로 더하는 것이 어색해서인게 아닌가 싶다.

그러나 어쨌건간에 지금은 이진수를 다루고 있고 각 자리는 0과 1 외에는 될 수 없으니까, 이진수를 이루는 각 자리의 수를 다 더한 결과가 해당 이진수가 몇 개의 1로 이루어져 있는지를 의미하는 것은 분명하다.

위에서 예를 든 5의 경우, 이진수로는 101이니까, 1 + 0 + 1 = 2이고, 101은 확실히 2개의 1로 이루어져 있음을 쉽게 확인할 수 있다.

우선 앞으로의 논의를 위해 32비트 숫자 n을 정의하자:

(여기서 / 은 나누기 연산자가 아니라,

부분 간 시인성을 높이기 위해 추가한 의미 없는 기호임에 유의하자.)

n = aa / bbb / ccc / ddd / eee / fff / ggg / hhh / iii / jjj / kkk

이로부터,

n >> 1 = a / abb / bcc / cdd / dee / eff / fgg / ghh / hii / ijj / jkk

n >> 2 = / aab / bbc / ccd / dde / eef / ffg / ggh / hhi / iij / jjk

이때, 그대로 n - n >> 1 - n >> 2 를 계산하는 것엔 문제가 있다.

왜냐하면, 예를 들어, bbb라는 부분에 몇 개의 1이 있는지 알려면,

위에서 논의한 대로, bbb - bb - b 를 해야 되는데,

지금까지대로라면, bbb - abb - aab 가 되어버린다.

따라서, abb로부터는 불필요한 a를, 그리고 aab로부터는 불필요한 aa를 제거해야 할 필요성이 제기된다.

그리고 그 역할을 하는 것이 3과의, 그리고 1과의 비트 AND 연산이다.

아래에 왜 그렇게 되는지를 보인다.

abb & 3

= abb & 011 (2)

abb

& 011

= 0bb & 연산의 정의에 의해 (참참참, 참거거, 거참거, 거거거)

a & 0 은, 0과의 AND연산이라는 것에서부터 이미, a의 값에 관계없이, 거짓이다. 따라서 0이다.

(초보라서 잘 몰겠는데 단축평가[short-circuit evaluation]의 원리가 아마 이게 아닌가 싶네여)

한편, b & 1 은, b의 값에 따라 참이거나 거짓이다. 만약 참이면--즉, b = 1이면--참참이므로 참이고, 거짓이라면 (b = 0) 거참이므로 거짓이다.

어쨌든간에 우리의 목적은 a를 생략시키고 b만 원래의 값으로 두는 것이었으므로,

방금의 논의에 의해 AND연산이 그 목적에 적합함이 분명해졌다.

본래의 코드상에서는 8진법 수 33... 을 썼는데, 그 이유는 이진수 011 011 ... 을 보기 좋게 표현하려고 한 것이 아닌가 싶다.

10진법으로 적자니 한 눈에 보기에 의미를 알 수 없는 길다란 수일 것이고 (= 3681400539 ㅋㅋ),

그렇다고 2진법으로 적자니 그건 C언어 문법에 (내가 알고 있기로는) 없고... (C Programming: A Modern Approach 2nd Edition p. 128)

그렇다고 16진법? 10진법이랑 같은 처지이지 않은가?

각 부분을 3비트로 나눴기 때문에 각 부분이 나타낼 수 있는 수의 범위는 0 ~ 7 인데,

한편 8진법에서 각 자리는 0 ~ 7의 값을 가질 수 있으니까 따라서 8진법이어야 각 부분이 하나의 자리로 표현되어 아름다운...

분명함을 위해 아래에 011011(2) 가 33(8) 과 같음을 보인다.

33 (8)

= 8^1 * 3 + 8^0 * 3 정의에 의해

= 8^1 * (2 + 1) + 8^0 * (2 + 1) 2+1=3 이므로

= 8^1 * (2^1 * 1 + 2^0 * 1) + 8^0 * (2^1 * 1 + 2^0 * 1) 2와 1을 2진법적으로 나타내기

= 2^3 * (2^1 * 1 + 2^0 * 1) + 2^0 * (2^1 * 1 + 2^0 * 1) 지수법칙에 의해 8^1 = (2^3)^1 = 2^(3*1) = 2^3

= (2^3 * 2^1 * 1) + (2^3 * 2^0 * 1) + (2^0 * 2^1 * 1 + 2^0 * 2^0 * 1) 분배법칙

= (2^4 * 1) + (2^3 * 1) + (2^1 * 1) + (2^0 * 1) 지수법칙

= 011011 (2) 증명완료

※ (참고) 지수법칙

정수 m, n에 대해

(am)^n = a^(mn)

[증명]

= a^m * a^m * ... * a^m am을 n번 곱함, 정의에 의해.

= (a * a * ... * a) * (a * a * ... * a) * ... (a * a * ... * a) 정의에 의해

= a^(mn) a를 m * n 번 곱했으므로. 증명완료.

a^m * a^n = a^(m+n)

[증명]

생략할게여 넘 번거롭네여 이거 수식 편집하는게...

html 편집기로 바꿔서 일일히 아랫첨자에 대해  그리고 윗첨자에 대해 sup 넣어야되고...

latex 렌더링(?) 지원해줬으면 편했을거같은데... 수식을 사진으로 만들어서 여기 붙여넣는것도 비슷한 귀찮음일거같은...

이 글을 보고 계신 여러분이라면 분명 슬기로우실테니 증명이 없어도 지수법칙을,

또한 고매하시기 때문에 저의 게으름도 충분히 이해해주시리라 믿어 의심치 않습니다.

가능한 한 자세히 적어보려다 보니까 자꾸 옆길로 빠져서 얘길 진행하기가 힘들긴 한데 어쨌든,

같은 원리로 1과의 AND연산을 하면 aab가 b로 된다. 00과 &하니까 aa가 죽는것이다.

이러한 사실으로부터, n - ((n >> 1) & 0o33...3) - ((n >> 2) & 0o11...1) 을 하면,

각 부분에 1이 몇 개 있는지에 대한 값을 얻게 된다. 즉, 예를 들어,

n = 110 111 (2) 이었다면, n - ((n >> 1) * 0o33) - ((n >> 2) * 0o11) = 010 011 (2) (230911 수정)

n = 110 111 (2) 이었다면, n - ((n >> 1) & 0o33) - ((n >> 2) & 0o11) = 010 011 (2)

왜냐하면 110에 있는 1의 갯수는 2개이고 (따라서 010), 111에 있는 1의 갯수는 3개니까 (따라서 011).

이것으로, 지금 탐구하고 있는 함수의 첫번째 비밀이 풀렸다.

이제 이 함수의 두번째 비밀이 우리를 다음의 논의로 이끌고 있다.

지금, k를 n - ((n >> 1) * 0o33...3) - ((n >> 2) * 0o11...1) 라고 하자. (k도 32비트임) (230911 수정)

지금, k를 n - ((n >> 1) & 0o33...3) - ((n >> 2) & 0o11...1) 라고 하자. (k도 32비트임)

위에서의 논의대로 이것은 n을 11개의 부분으로 나눈 후 각 부분에 있는 1의 갯수를 센 결과이다.

따라서 k도 11개의 부분으로 이루어져 있으며, 각 부분이 가질 수 있는 수의 범위는 0 ~ 3이다.

왜냐하면, n에서의 한 부분은 3비트였으므로, 따라서 1의 갯수는 최소 0개 최대 3개일수밖에 없다.

즉 최대 3이므로 2비트로 표현가능하며, 따라서 다음과 같이 쓸 수 있다.

k = aa / 0bb / 0cc / 0dd / 0ee / 0ff / 0gg / 0hh / 0ii / 0jj / 0kk

이때 k >> 3을 고려한다. 즉,

k >> 3 = / 0aa / 0bb / 0cc / 0dd / 0ee / 0ff / 0gg / 0hh / 0ii / 0jj

그러므로

k + k >> 3

= aa / bb + aa / cc + bb / dd + cc / ee + dd / ff + ee / gg + ff / hh + gg / ii + hh / jj + ii / kk + jj

여기서 aa = A, bb = B 와 같은 식으로 치환하고 식을 알파벳순으로 정리해보면

= A / A + B / B + C / C + D / D + E / E + F / F + G / G + H / H + I / I + J / J + K

따라서, 식의 모양을 보아하니 중간에 껴 있는 A + B, C + D 같은 애들만 kill 해버리면 뭔가 식의 모양이 예뻐질 것 같다고 생각한다.

그 암살의 역할을 수행하는게 바로 0o30707070707 과의 AND연산이다.

따라서,

(k + k >> 3) & 0o30707070707

= A / A + B / B + C / C + D / D + E / E + F / F + G / G + H / H + I / I + J / J + K

& 011 / 000 / 111 / ...

한마디로, 위에서 이미 관찰했다시피, 000과의 AND연산은 무조건 그 결과로 000을 산출하고 111과의 AND연산은 무조건 그 결과로 나머지 피연산자를 그대로 산출한다.

그리고, B + C 와 같은 값이 무조건 0 ~ 6 인 것은, 아까 얘기했다시피 B, C 등이 0 ~ 3 이라는 것으로부터 분명하다.

왜냐하면, 상식적으로 최대로 3인 놈 + 최대로 3인 놈 = 최대로 6인 놈이 될 테니까.

그렇기 때문에 살려야 될 부분에 대해서는 111과 AND연산을 하는것이라고 생각한다. 0 ~ 6을 표현하려면 3개의 비트가 필요하니까.

따라서

(k + k >> 3) & 0o30707070707

= A / 000 / B + C / 000 / D + E / 000 / F + G / 000 / H + I / 000 / J + K

이것으로 이 함수의 두번째 비밀이 성공리에 해석되었다.

이제 세번째 비밀에 대해서 알아보자.

A라는 것은 정확히 이야기하면 사실상, (여기서 n31, n30와 같은 것은 k를 이루고 있는 비트라고 하자. 즉 그 값은 0 또는 1)

A = (2^31 * n31) + (2^30 * n30)

왜냐하면 k의 31번째, 30번째 비트이므로.

따라서

(k + k >> 3) & 0o30707070707

= A / 000 / B + C / 000 / D + E / 000 / F + G / 000 / H + I / 000 / J + K

= (2^31 * n31) + (2^30 * n30)

+ (2^26 * n26) + (2^25 * n25) + (2^24 * n24)

+ (2^20 * n20) + (2^19 * n19) + (2^18 * n18)

+ (2^14 * n14) + (2^13 * n13) + (2^12 * n12)

+ (2^8 * n8) + (2^7 * n7) + (2^6 * n6)

+ (2^2 * n2) + (2^1 * n1) + (2^0 * n0)

그런데 우리가 원하는 것은 저게 아니라

2^0 * n0 + 2^1 * n1 + 2^2 * n2

+ 2^0 * n6 + 2^1 * n7 + 2^2 * n8

+ ...

+ 2^0 * n30 + 2^1 * n31 이기 때문에,

이번에는 2의 6승의 n승 (=2^(6n)) 을 kill 하는 방법이 필요하다.

이제 이 글의 흐름을 예측했겠지만 그것이 바로 % 63이다.

이제 왜 63과의 나머지연산이 2의 6n승을 없애는지에 대한 해명을 진행한다.

제일 간단한 해명은 (이것은 아는 분께 깨우침을 얻어서 알게 된 것임),

예를 들어

J + K = p * 2^0

H + I = q * 2^6 // 한마디로 2^6으로 묶었다고 보면 된다. 즉 2^6 * ( (2^0 * n6) + (2^1 * n7) + (2^2 * n8) )

F + G = r * 2^12

라고 하자. 이 때 2^6 = 64 이고 2^12 = 4096 이므로,

p + 64q + 4096r

= p + q + r + 63q + 4095r

= (p + q + r) + 63 * (q + 65r)

= t 라고 하자.

※ (x * x) - 1 은 x - 1 로 나눠진다. 왜 나눠질까? x - 1 이 공약수니까 그렇지 않을까요 수학초보라서 잘 모름 ( x^2 - 1 = (x + 1)(x - 1) )

아무튼간에 (64 * 64) - 1 이 64 - 1 로 나눠짐을 보여주고 싶었음

따라서 t를 63으로 나누게 되면 (정수 나눗셈임 즉 5/2 = 2...1)

t / 63 = (q + 65r)... (p + q + r)

그러므로

t % 63

= p + q + r

= (2^0 * n0) + (2^1 * n1) + (2^2 * n2) J와 K부분에 있던 1의 갯수

+ (2^0 * n6) + (2^1 * n7) + (2^2 * n8) H와 I부분에 있던 1의 갯수

+ (2^0 * n12) + (2^1 * n13) + (2^2 * n14) F와 G부분에 있던 1의 갯수

이것으로 % 63을 하면 2의 6n승이 날아간다는것이 분명하다.

다음 해명은 아까 질문글에서 나에게 가르침을 주신 분께서 말씀해 주신 것으로,

모듈러 연산의 법칙에 따라 그렇게 된다고 한다.

근데 문제는 내가 mod라든지, 작대기 3개 있는 기호같은게 뭔지 모르고, 또 나머지 연산자랑 무슨 관련이 있는지 모른다는 것이다.

공부하겠다고 위키피디아 문서는 켜놨는데 귀찮아서 한달째 안읽고있는.

아는 사람이 있으면 강좌글을 써서 고견을 좀 나눠주시면 소중히 간직하겠음.

마지막 해명은 내가 몇시간동안 머리쥐어뜯다가 우연하게 깨달은 것인데 한번 소개해 보겠다.

(틀렸을 수 있으니 주의 필요)

0 <= a, b, c 이고,

a + b + c < 7 이며,

foo = a + 8b + 64c 일때,

foo % 7 = a + b + c 임을 증명하자.

지금 여기서,

foo = body + rem

으로 되어 있다고 가정하고,

rem = foo % 7 즉 foo를 7로 나눈 나머지

이라고 하자.

이때, 문제의 조건인

a + b + c < 7

으로부터, a는 이미 body의 일부가 아니다.

왜냐하면, a는 7보다 작은데 7로 나눠지려면 최소 7이어야 하기 때문이다.

따라서 나눠질 수 없으므로 a는 rem의 일부임.

또한, 이로부터 8b + 64c를 7로 나눈 나머지가 rem을 마저 구성함을 알 수 있음.

잠깐 논의에서 벗어나 정수 나눗셈의 한 성질을 관찰해보자.

1 * 8 / 7 = 1... 1

2 * 8 / 7 = 2... 2 8이 2묶음 있는데 각 묶음에서 7개씩 뺀다 하면 2번 뺄 수 있고 묶음당 나머지가 1개 남으니까.

...

n * 8 / 7 = n... n

다시 논의로 돌아와서,

part = 8b + 64c 라고 하자. 따라서

= 8 * (b + 8c)

따라서

7 < part b=c=0 이 아니라면.

즉 part는 7보다 크므로 7로 나눠질 수 있다. 즉,

part / 7

= 8 * (b + 8c) / 7

= (b + 8c) * 8 / 7

= (b + 8c)... (b + 8c)

이때 나머지는

7 < b + 8c c=0이 아니라면.

따라서 b + 8c 또한 7로 나눠질 수 있으며, 그 결과는

(b + 8c) / 7

= c... c + b

왜냐하면 문제의 조건으로부터 b는 7보다 작아서 몫에 영향을 주지 않으니까. 따라서 b는 무조건 나머지이다.

그리고 문제의 조건으로부터 c + b는 7보다 작기 때문에 더 이상 나눌 수도 없다.

따라서 일찍이 정의되었듯 rem = a + @인데

part를 7로 나눠가면서 @ = b + c 라는것이 분명해졌음

따라서 rem = a + b + c인데,

rem = foo % 7 이고, foo = a + 8b + 64이므로,

(a + 8b + 64) % 7 = a + b + c 이 분명하다. 증명완료.

이런 명쾌한 순간이 논리의 재미인거 같음...

여기에선 % 7을 썼지만 같은 논리가 % 63에도 적용될 수 있을 거라고 생각한다. 왜냐하면 다른 조건은 동일하니까...

아무튼간에 이것으로 % 63을 적용해야 원하는 결과--32비트 숫자 내의 1인 비트 갯수--를 얻을 수 있음이 해명되었다.

또한 이것으로 이 함수의 작동원리가 모두 잘 분석되었다고 생각한다.

내가 이 함수의 작동원리를 올바르게 설명했는지도, 또 내가 잘 이해했는지도 잘 모르겠지만,

어쨌건간에 이 글이 여러분께 충분하고, 또 직관적인 설명이 되었다면 그것이 나의 기쁨이 되겠음.

추가적으로, 비트열에서 1의 갯수를 세는 방법은 대충 아래와 같이 되는 것 같음

1. 반복문/재귀를 이용해서, if문으로 특정 자리가 0인지 1인지 검사후 1이면 카운트 올리기
2. n & (n - 1) 이 0이 될 때까지 n을 갱신하면서 반복. 반복횟수가 곧 비트열 내 1의 갯수임. 왜 그렇게 되는지는 모르겠음
3. 비트열을 여러 개의 부분으로 나눈 후, 각 부분에 "필터"를 적용해서 1의 갯수를 세고, 부분별 결과를 다 더하기
4. 미리 모든 숫자에 대한 룩업테이블 구비 ㅋㅋ 이건 "갯수를 센다" 기 보다는 배열의 원소를 참조한다고 해야 하는 것이 아닌?
5. 내장 명령어(?) 사용. 컴퓨터초보라 무슨의민지 잘 모름