재귀가 아닌 Bit로 Power of Two 찾기

jaehan·2025년 8월 9일

핵심 아이디어

n & (n-1)

해당 표현식은 n의 최하위 비트를 끄는 연산

n이 2의 거듭제곱이면 이진수로 딱 1개의 1만 켜져 있습니다.

그 1개를 끄면 0이 되므로 (n > 0 && (n & (n-1))) == 0이면 참

n = ... x x x 1 0 0 0 0
              ^----- 최하위 1비트 (그 오른쪽은 모두 0)

n - 1을 하면,

최하위 1비트를 0으로 바꾸고

그보다 오른쪽(하위) 비트들은 모두 1로 채워집니다.

즉,

n     = ... x x x 1 0 0 0 0
n - 1 = ... x x x 0 1 1 1 1
---------------------------
AND   = ... x x x 0 0 0 0 0  (= 그 위치의 1이 꺼짐)

따라서 n & (n-1)은 최하위 1비트를 제거한 값이 됩니다.

만약 n이 2의 거듭제곱(예: 1, 2, 4, 8, …)이라면 최하위 1비트가 유일한 1이므로 결과가 0.

하나라도 더 1이 있으면 0이 아닙니다.

예시

n = 8  (1000)
n-1= 7  (0111)
&  = 0  (0000)  -> 0 이므로 2의 거듭제곱

n = 12 (1100)
n-1= 11 (1011)
&  = 8  (1000)  -> 0이 아님 -> 2의 거듭제곱 아님

공부공부