20240120_2의 거듭 제곱

오늘의 TIL은 특정 수가 2의 거듭 제곱인지 확인하는 방법에 대한 내용이다.

 

알고리즘 문제를 풀다가

 

'특정 수가 2의 거듭 제곱'인지 판단해야되는 로직이 들어간 문제를 풀게되었다.

 

이 특정 수가 2의 거듭 제곱인지 확인하는 과정은 다른 알고리즘 문제들에서 많이 사용될 것으로 생각되어 정리한다.

 

1. 2의 거듭 제곱의 특성

2의 거듭 제곱은 이진수로 표현하였을 때, 하나의 비트만 1이고 나머지는 0인 특징을 가진다.

예를 들면, 8(1000), 4(0100), 2(0010).

 

2. 2의 거듭 제곱에서 1을 뺀 숫자와의 차이점

2의 거듭 제곱에서 1을 빼면 이진수에서 1이었던 숫자가 0이되고 그 아래의 숫자들은 모두 1이된다.

예를 들면, 8에서 1을 빼면 (1000)에서 (0111)이 되고 4에서 1을 빼면 (0100)에서 (0011)이 된다.

 

3. 비트 AND 연산(&)

두 이진수에서 동일한 위치에 있는 비트가 모두 1일 때만 결과의 해당 비트가 1이되는 연산이다.

따라서 2의 거듭 제곱 수와 그 수에서 1을 뺀 값의 비트 AND 연산 결과는 0이 되게 된다.

예를 들어서 4(0100)과 3(0011)의 AND 연산 결과는 0이다.

 

4. 2의 거듭 제곱인지 확인하는 방법

이 TIL에서 아래의 식만 기억해도 되는데, int i가 2의 거듭 제곱인지 판단하는 방법은

 

if (i & (i - 1) == 0)
{
    Console.WriteLine("i는 2의 거듭 제곱입니다");
}
else
{
    Console.WriteLine("i는 2의 거듭 제곱이 아닙니다");
}

 

간단하게 i & (i - 1) == 0 에서 참이 나오는 숫자들은 2의 거듭 제곱이다 라고 정리할 수 있다.