Power of Two
정수 n이 주어집니다. n이 2의 거듭제곱, 즉 어떤 정수 k ≥ 0에 대해 n = 2^k이면 true를 반환하고, 그렇지 않으면 false를 반환하세요. 따라서 1, 2, 4, 8은 해당하지만, 0, 6 및 모든 음수는 해당하지 않습니다.
함수
- ninteger
- 테스트할 정수(0 또는 음수일 수도 있음)
- 반환값boolean
- n이 어떤 k ≥ 0에 대해 2^k와 같으면 true, 그렇지 않으면 false
제약 조건
-231 ≤ n ≤ 231-1
예제
- 입력
- n = 16
- 출력
- true
- 설명
- 16 = 2 × 2 × 2 × 2 = 2^4. 2진수로는
10000이며, 1비트가 하나입니다.
- 입력
- n = 24
- 출력
- false
- 설명
- 24 = 8 × 3입니다. 절반으로 나누면 12, 6, 그리고 3이 되며, 3은 홀수이지만 1은 아닙니다. 24를 이진수로 나타내면
11000이며, 1비트가 두 개입니다.
- 입력
- n = 1
- 출력
- true
- 설명
- 1 = 2^0이므로 2의 거듭제곱입니다. 이진수 형태인
1에는 1비트가 정확히 하나 있습니다.
제출 시 숨은 테스트 +17개
후속 질문
같은 비트 트릭으로, 루프 없이 n이 4의 거듭제곱인지 확인할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
2의 거듭제곱 몇 개를 2진수로 써 보세요:
1,10,100,1000. 이 수들이 모두 공통으로 가지고 있지만 6(110)에는 없는 것은 무엇인가요?2의 거듭제곱에는 1 비트가 정확히 하나 있습니다.
n과n-1을 이진수로 비교해 보세요. 1을 빼면 가장 낮은 위치의 1 비트는 0으로 바뀌고, 그 아래의 모든 0은 1로 바뀝니다.따라서
n이 2의 거듭제곱인 경우는 양수이고n-1과 비트 AND 연산을 했을 때 0이 되는 경우뿐입니다. 0과 음수는 절대 2의 거듭제곱이 아니므로 비트를 확인하기 전에 부호를 검사하세요.
풀이
2의 거듭제곱은 2진수에서 고정된 형태를 갖습니다. 10000이 16을 나타내는 것처럼 1비트 하나 뒤에 0들이 이어집니다. n이 홀수가 될 때까지 절반으로 나누어 이 형태인지 확인할 수 있으며, 최대 31단계가 걸립니다. 또는 n & (n-1)을 사용해 한 단계만에 확인할 수도 있습니다. 이 연산은 가장 낮은 1비트를 지우며, 그 비트가 유일한 1비트였을 때만 0을 남깁니다. 두 방법 모두 부호 검사를 먼저 해야 합니다. 0과 음수는 겉보기에 명백한 코드를 제대로 작동하지 않게 만들기 때문입니다.
수가 짝수인 동안 2로 나누기
핵심 아이디어
n = 2^k라면 이를 정확히 k번 2로 나누어 1에 도달할 수 있으며, 그 과정의 모든 값은 짝수입니다. n에 1보다 큰 홀수 인수가 있으면, 1이 아닌 홀수에서 나누기가 멈춥니다. 16의 경우: 16, 8, 4, 2, 1이므로 답은 true입니다. 24의 경우: 24, 12, 6, 3이며, 3은 홀수이지만 1이 아니므로 답은 false입니다.
루프 전에 n ≤ 0이면 false를 반환합니다. 0이나 음수인 2의 거듭제곱은 없으며, 0은 짝수이고 0의 절반도 여전히 0이므로 루프는 0에서 절대 끝나지 않습니다.
각 단계에서 n을 절반으로 줄이므로, 32비트 입력은 최대 31단계가 걸립니다. 시간 복잡도는 O(log n)이고 공간 복잡도는 O(1)입니다.
알고리즘
n ≤ 0이면 false를 반환합니다.n이 짝수인 동안 2로 나눕니다.- 이제
n이 1인지 여부를 반환합니다.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1n & (n-1)을 사용해 가장 낮은 설정 비트를 지웁니다
핵심 아이디어
2의 거듭제곱을 2진수로 쓰면 1 하나 뒤에 0이 이어집니다. 16은 10000입니다. 1에서 1을 빼면 그 1은 0이 되고 그 아래의 모든 0은 1이 됩니다. 15는 01111입니다. 두 숫자에는 공통으로 1인 비트가 없으므로 16 & 15는 0입니다.
그 외의 양수에는 1 비트가 적어도 두 개 있습니다. 1을 빼면 가장 낮은 1 비트와 그 아래의 0만 바뀌므로, 더 높은 모든 1 비트는 두 숫자에 모두 나타나고 AND 결과는 0이 아닙니다. 11000인 24의 경우, 23 = 10111이 되고 24 & 23은 10000이며, 이는 16입니다.
먼저 n > 0인지 확인하세요. 0 & -1은 0이고, 32비트 산술에서 -2^31은 1 비트 하나 뒤에 0이 31개 이어지므로 AND만으로 검사하면 둘 다 2의 거듭제곱이라고 판정됩니다. 전체 검사는 비교 한 번, 뺄셈 한 번, AND 한 번으로 이루어집니다. 시간과 공간 복잡도는 O(1)입니다. Lua 5.1에는 AND 연산자가 없으므로, Lua 코드는 비트를 하나씩 처리해 AND를 구성하며 32비트 n의 경우 최대 31단계를 거칩니다. 검사의 원리는 같습니다.
알고리즘
n ≤ 0이면 false를 반환합니다.- 가장 낮은 1 비트를 지운
n인n & (n-1)을 계산합니다. - 그 결과가 0인지 여부를 반환합니다.
def isPowerOfTwo(n):
# One set bit: n - 1 flips it and every bit below, so the AND is 0.
return n > 0 and n & (n - 1) == 0
함정과 경계 사례
비트 테스트는 한 줄이면 되며, 대부분의 실수는 이 테스트가 처리하도록 설계되지 않은 입력과 관련이 있습니다.
- 부호 검사를 건너뜁니다.
0 & (0-1)은 0이므로 0은 AND 테스트를 통과합니다. 32비트 정수에서는-2^31도 통과하는데, 이진 표현에서 1비트가 하나뿐이기 때문입니다. 둘 다 false를 반환해야 합니다. - 0에 대해 반감 루프를 실행합니다. 0은 짝수이며, 절반으로 나눠도 다시 0이 되므로 루프가 끝나지 않습니다.
- 괄호를 생략합니다.
==는&보다 우선순위가 높으므로 C, C++ 및 JavaScript에서는n & n - 1 == 0이n & ((n - 1) == 0)으로 해석되어 오류 없이 잘못된 결과를 냅니다. Java와 C#에서는 형식 오류로 거부됩니다.(n & (n - 1)) == 0으로 작성하세요. - 로그를 사용합니다. 배정밀도에서는
log(536870912) / log(2)의 결과가 29가 아니라 29.000000000000004이므로, 정수 여부 검사에서2^29를 false로 판정합니다.
자주 묻는 질문4
숫자가 2의 거듭제곱인지 어떻게 확인하나요?
n > 0이고 n & (n-1)이 0과 같으면 true를 반환합니다. 2의 거듭제곱에는 1 비트가 정확히 하나 있으며, 1을 빼면 그 비트가 지워지고 그 아래의 비트만 설정되므로 AND 연산 결과는 0입니다. 비트 연산을 사용하지 않으려면 n이 짝수인 동안 절반으로 나누고, 최종적으로 1이 되는지 확인하세요.
n & (n-1)은 왜 가장 낮은 설정 비트를 지울까요?
1을 빼면 가장 낮은 1 비트에서 빌림이 발생합니다. 해당 비트는 0이 되고 그 아래의 모든 0은 1이 되며, 더 높은 비트는 그대로 유지됩니다. 원래 값과 AND 연산을 하면 둘 다에서 설정된 비트만 남는데, 이는 바로 더 높은 비트들입니다. 2의 거듭제곱에는 더 높은 비트가 없으므로 결과는 0입니다.
2의 거듭제곱의 시간 복잡도는 얼마인가요?
n & (n-1) 검사는 시간과 공간이 O(1)이고, 비교 한 번, 뺄셈 한 번, AND 한 번을 수행합니다. 절반씩 줄이는 루프는 O(log n) 시간에 실행되며, 32비트 정수의 경우 최대 31단계입니다.
1은 2의 거듭제곱인가요? 0은요?
1은 2의 거듭제곱입니다. 2^0 = 1이고, 이진수 형태에 1 비트가 하나 있기 때문입니다. 0은 그렇지 않습니다. 어떤 정수 지수로도 0이 되지 않고, 1 비트가 전혀 없습니다. 음수도 2의 거듭제곱이 될 수 없습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def isPowerOfTwo(n):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
n = 16
기대값
true