n&-n
자주 접하지 못했던 식인 n&-n에 대해 쓰는 글이다.
n&-n
n을 음이 아닌 $b$비트 정수라고 하자. 등식 n + (~n) = -1을 상상하면 -n = ~n + 1임을 알 수 있다. n&-n을 평가하기 위해, n의 이진법 표현에서 $2^0$ 자리, $2^1$ 자리, …에 대한 사례 분석을 진행할 수 있다. n = $n_{b - 1} \cdots n_1 n_0$는 ${0, 1}^b$의 원소이고, 즉 수와 동시에 $b$비트 문자열이 된다. 비트 $x$에 대해 $x$의 부정을 $\bar x$로 표기하자. 비트 $x$에 대해 $x \& \bar {x}$는 항상 0이다. $b$비트 표현에서 숫자의 자리를 명확하게 하기 위해, 0, 1 등 상수 비트의 첨자에 자릿수를 표기한다.
n이 1으로 끝나는 경우, $n_0 = 1$이고~n의 $b$비트 표현은 $\bar{n}{b - 1} \cdots \bar{n}_1 0_0$이다. 여기에 1을 더한-n의 $b$비트 표현은 $\bar{n}{b - 1} \cdots \bar{n}1 1_0$이 된다.n&-n의 $b$비트 표현은 $0{b - 1} \cdots 0_1 1_0$이다. 이를 정수로 읽으면 1이다.n이 0으로 끝나는 경우, $n_0 = 0$이고~n의 $b$비트 표현은 $\bar{n}_{b - 1} \cdots \bar{n}_1 1_0$이다. 이전과 달리 여기에 1을 더하면 $2^0$ 자리보다 높은 자리에 영향을 주게 된다. 아직 상황이 잘 보이지 않으므로 사례 분석을 좀 더 해보자.n이 10으로 끝나는 경우, $n_1 n_0 = 10$이고~n의 $b$비트 표현은 $\bar{n}{b - 1} \cdots \bar{n}_2 0_1 1_0$이다. 여기에 1을 더한-n의 $b$비트 표현은 $\bar{n}{b - 1} \cdots \bar{n}2 1_1 0_0$이고n&-n의 $b$비트 표현은 $0{b - 1} \cdots 0_2 1_1 0_0$이다. 이를 정수로 읽으면 2이다.n이 00으로 끝나는 경우, $n_1 n_0 = 00$이고~n의 $b$비트 표현은 $\bar{n}_{b - 1} \cdots \bar{n}_2 1_1 1_0$이다. 다시, 여기에 1을 더하면 $2^0, 2^1$ 자리보다 높은 자리에 영향을 준다. 다시 사례 분석을 하자.n이 100으로 끝나는 경우, $n_2 n_1 n_0 = 100$이고~n의 $b$비트 표현은 $\bar{n}{b - 1} \cdots \bar{n}_3 0_2 1_1 1_0$이다. 여기에 1을 더한-n의 $b$비트 표현은 $\bar{n}{b - 1} \cdots \bar{n}3 1_2 0_1 0_0$이고n&-n의 $b$비트 표현은 $0{b - 1} \cdots 0_3 1_2 0_1 0_0$이다. 이를 정수로 읽으면 4이다.n이 000으로 끝나는 경우, $n_2 n_1 n_0 = 000$이고~n의 $b$비트 표현은 $\bar{n}_{b - 1} \cdots \bar{n}_3 1_2 1_1 1_0$이다. 또 다시, 여기에 1을 더하면 $2^0, 2^1, 2^2$ 자리보다 높은 자리에 영향을 준다…
계속 사례 분석을 할 수 있지만, 잠시 멈추고 각 사례에서 나타나는 패턴을 분석하자. n이 1로 끝날 때 n&-n = 1이고, 10으로 끝날 때 n&-n = 2이고, 100으로 끝날 때 n&-n = 4이다. 아직 결과를 확인하지는 않았지만 n이 1000으로 끝날 때 n&-n = 8이고, 10000으로 끝날 때 n&-n = 16이고, n이
\(1\underbrace{0\cdots00}_{m \mbox{ times}}\)
으로 끝날 때 n&-n = $2^m$일 것 같다. 사례 $b + 1$개를 2개의 류로 나누어 다시 사례 분석을 하자.
n의 $b$비트 표현에서 1이 등장하지 않는 경우,n=-n= 0이고n&-n= 0이다.n의 $b$비트 표현에서 1이 등장하는 경우, 1이 등장하는 자리수의 집합 (예를 들어 $13 1_2 0_1 1_0$의 경우 ${0, 2, 3}$)은 자연수의 부분 집합이므로 집합의 최소원이 존재한다. 이를 $m$이라고 하면, $m < b$이고,n은 1과 $m$개의 0으로 끝난다.n의 $b$비트 표현은 $n{b - 1} \cdots n_{m + 1} 1m 0{m - 1} \cdots 00$이고,-n의 $b$비트 표현은 $\bar{n}{b - 1} \cdots \bar{n}{m + 1} 1_m 0{m - 1} \cdots 00$이고n&-n의 $b$비트 표현은 $0{b - 1} \cdots 0{m + 1} 1_m 0{m - 1} \cdots 0_0$이다. 이를 정수로 읽으면 $2^m$, 또는 부호 있는 정수인 경우 $m = b - 1$일 때 $-2^{b - 1}$이다.
$m = b - 1$인 경우 $1{b - 1} 0{b - 2} \cdots 0_1 0_0$이 읽히는 방법 때문에 n이 부호 있는 정수인지 부호 없는 정수인지에 따라 분석이 약간 다르게 읽히지만, $m < b - 1$일 때는 대체로 같은 분석을 할 수 있다. 모든 경우에 n ↦ n&-n은 n의 비트 표현에서 1이 등장할 경우 가장 낮은 자리에 있는 1만을 그 자리와 함께 남기는 연산이다.
활용
PS 고수들은 n+=n&-n, n-=n&-n 또는 n-=-n&n과 같은 아름다운 표현을 비트 마스크와 관련된 연산을 하고 싶을 때나 어쩌구 트리에서 인덱스를 계산할 때 종종 사용하는 듯 하다. n&-n이 무엇인지 알게 되었다면 n의 이진 표현을 가지고 씨름하거나, n과 비트 and 연산이 0이 아닐 때 까지 2를 곱할 필요 없이 이런 표현이 필요할 때 마음껏 써도 될 듯 하다.