2의 제곱수 판별, 작거나 같은 수들 중 가장 큰 2의 제곱수 구하기

2의 제곱수인지 판별하기

public class PowerOfTwoChecker {

    public static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    public static void main(String[] args) {
        System.out.println(isPowerOfTwo(1)); // true
        System.out.println(isPowerOfTwo(2)); // true
        System.out.println(isPowerOfTwo(16)); // true
        System.out.println(isPowerOfTwo(18)); // false
    }
}

 

 

2의 제곱수는 이진수로 표현했을 때, 1 뒤에 0만 여러 개 있는 형태를 가진다. (예: 1, 10, 100, 1000, ...). 이러한 특성을 활용하여 아래와 같은 로직을 구현할 수 있다.

 

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

 

이진수 1000에서 1을 빼면 이진수 0111이 되기 때문에 1000 & 0111 == 0 즉, 각자리의 숫자가 무조건 달라진다는 특성이 있다. 따라서 비트 and 연산을 수행했을 때 0이 나오게 된다.

 

 

주어진 숫자보다 작거나 같은 가장 큰 2의 제곱수 찾기 (right shift 연산 활용)

public static long findLargestPowerOfTwoLessThanOrEqual(long n) {
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n |= n >> 32;
        return (n + 1) >> 1;
    }

 

주어진 수 보다 작거나 같은 수들 중 가장 큰 2의 제곱수를 찾기 위해선 우선 2의 제곱의 특징을 알아야한다. 앞에서도 말했듯이 2의 제곱수는 이진수로 표현했을 때, 1 뒤에 0만 여러 개 있는 형태를 가진다. (예: 1, 10, 100, 1000, ...). 

 

그래서 해당 수 보다 같거나 작은 수들 중 가장 큰 2의 제곱수를 구하기 위해선 해당 수 이진 표현의 최상위 비트 1을 제외한 하위 비트들이 0이면 된다.  

ex) 101101 보다 작거나 같은 수 중 가장 큰 2의 제곱수는 100000이 된다.

111111 => 100000

10101 => 1000

1010 => 1000

1011 => 1000

 

즉 우리의 목표는 최상위 비트 1을 제외한 하위비트들이 0인 수를 반환하는 것이다.

이를 위해 우선 주어진 수 n의 최상위 비트 1부터 최하위 비트까지 모두 1로 만든다.   ex) 1001010 => 1111111

 

이제 최상위 비트 1을 제외한 하위 비트 모든 1들을 0으로 만들어 주면 되는데 이는 단순히 1을 더해주면 된다.

1111111 + 1 => 10000000

우리가 원하는 것은 0이 하나 적은 이진수(1000000)이므로 right shift 1 (>>1 연산)을 통해 구할 수 있다.

 

10000000 >> 1 => 1000000

 

 

주어진 수 n의 최상위 비트 1부터 최하위 비트까지 모두 1로 만드는 과정을 조금 더 자세히 설명해보면 

n |= n >> 1;   // 첫 단계에서 상위 2비트가 1이 된다
n |= n >> 2;  // 상위 2비트가 1이므로 2번 쉬프트 연산을 한뒤 bitwise or 연산을 해주면 상위 4비트가 1이된다.
n |= n >> 4;  // 상위 4비트가 1이므로 4번 쉬프트 연산을 해준뒤 bitwise or 연산을 해주면 상위 8비트가 1이된다.
n |= n >> 8; // 상위 8비트가 1이므로 8번 쉬프트 연산을 해준뒤 bitwise or 연산을 해주면 상위 16비트가 1이된다.
n |= n >> 16; // 상위 16비트가 1이므로 16번 쉬프트 연산을 해준뒤 bitwise or 연산을 해주면 상위 32비트가 1이된다.
n |= n >> 32;  // 상위 32비트가 1이므로 32번 쉬프트 연산을 해준뒤 bitwise or 연산을 해주면 상위 64비트가 1이된다.

 

이를 통해 양수 long 범위(2^63-1 까지)의 모든 수를 커버하며 최상위 비트 1부터 하위 비트들을 모두 1로 만들수 있다.

 

 

 

 

응용문제

 

https://www.hackerrank.com/challenges/counter-game/problem

Counter game | HackerRank