[C++] Interview Question : Bitwise Operator

Question

Debuger 다음 코드가 하는 일을 설명하라
(( n & (n-1)) == 0)

제약사항

---

Solution

---

Solution

먼저 A & B의 연산 결과가 0 이란 뜻은 A와 B의 사이에 공통된 비트가 없다는 뜻이다.

그렇다면 A와 B의 의미에 대해 자세히 보면 n에서 1을 뺀다는 것은 n의 비트 값이 1인 것 중 최하위 비트에서 1을 뺀다는 의미이다. 그 수와 &연산을 하면 그 아랫 값들이 모두 0이 된다는 소리이다.

 

예를 들어, n 이 110101010111 이라고 하면 

 

110101010100 : (n)

110101010011 : (n-1) 

---------------------------

110101010000 : (n) & (n-1)

 

즉, 회색 표시 위의 값엔 영향을 안미치고, 이를 활용한다면, 값이 1인 비트가 단 한 개인 경우 해당 식을 만족한다는 뜻이다. 

 

즉 위의 식을 다시 설명하면 

n 의 비트 개수가 1개인가? 혹은

n 이 2의 거듭제곱인가?라고 판단하는 역할을 수행한다. 

 

---

+) 추가로 이를 응용할 수 있다.

어떤 두 수 A, B가 있을 때, 서로 다른 비트가 1개 이하인지 알아볼 수 있다. 

A & B를 연산한 결과를 C라 할 때, ((C) & (C -1)) == 0 이면 A와 B의 서로 다른 비트가 1개 이하이다.

역으로 생각해보면 A와 B의 결과로 값이 1인 비트가 하나 혹은 0이어야 해당식을 만족하고, 즉 &연산을 하였는데 겹치는 부분이 1개 이하라는 뜻으로, 서로 다른 비트가 1개 이하라고 판단할 수 있다.