n&(n-1)

오늘 동칸이 퀴즈를 하나 냈다. 어떤 int n 이 있으면 그게 2진수에서 1로 시작한 다음 0이 주욱 나오다가 1로 끝나는지 어떻게 아는가 하는 것이었다. 101 이라던가, 1000001 이라던가. 답은 !((n-1)&(n-2)) 였다. 나는 처음에 1 빼고 남은 수에서 1이 한 개만 있는지 판정하는 법을 고민했는데, 앞 퀴즈의 답을 생각하면 1이 한 개만 있는지 판정하는 식은 !(n&(n-1))이다. 이거 어디서 분명히 본 적이 있는 식이다…싶었는데, ‘Beautiful Code’ 책에 나왔다는 게 생각났다. 거기서는 n&(n-1)이 가장 오른쪽의 1을 지워주는 식이라고 소개되었다.

거꾸로 저 식에서 다시 원래 퀴즈의 답을 연역해 내려면 어떻게 해야할지도 궁금해졌다. 일단 n&(n-1) 이 가장 오른쪽의 1을 지워주니까, x 개의 1을 지우려면 저걸 x 번 불러주면 된다.

for (int i=x; (i>0)&&n; –i) n=n&(n-1);

1이 두 개면 x가 2 인데, 루프를 풀어주면 이렇다.

n=n&(n-1); n=n&(n-1);

그런데 퀴즈의 조건과 같이 두 개의 1 가운데 하나가 반드시 가장 오른쪽(낮은 자리)에 있다면, 처음에는 그냥 n-1만 하면 된다.

n=n-1; n=n&(n-1);

즉,

n=(n-1)&(n-2);

그래서, 이게 1로 끝나는 수에서 오른쪽에서부터 두 개의 1을 지우는 식, 처음 퀴즈의 답이로다. 오오…역시 신기한 bitwise의 세계.