leetcode - 231. Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

 

문제 

자연수 n이 주어지는데, n을 2의 제곱으로 표현할수 있는지 판단

가능하면 true, 아니면 false return 한다.

 

class Solution {
    public boolean isPowerOfTwo(int n) {
        //음수나, 0일경우 표현못함
        if(n <= 0) return false;
        
        int cnt = 0;
		while(n >= 1) {
			if((n & 1) == 1) {
                //n과 1을 and 연산을 통해 1의 갯수를 센다.
				cnt++;
			}
			n = n >> 1;//쉬프트 연산 (오른쪽으로 1번 이동)
            if(cnt>1) return false; //2의 제곱일경우 1의 갯수가 1개여야함
		}
		
		return true;
    }
}

풀이1.

2의 제곱 이진수로 표현

1 -> 1

2 -> 10

3 -> 11

4 -> 100

....

8 -> 1000

...

16 -> 10000

 

만약 n이 4이면, 4를 이진수로 표현하면 100

만약 n이 5이면, 5면 101 이다. 

답은 이진수로 표현했을때 1이 1개가 나와야한다.

 

1. 100(2) & 1 = 0 이다. 따라서 cnt에 더하지 않는다.

2. 100(2) >> 1 쉬프트연산을 하면  n 은 10(2) 가 된다.

3. 10(2) & 1 = 0, cnt에 안더함

4. 10(2) >> 1 , n  은 1(2) 이된다.

5. 1(2) & 1 = 1 이다. 따라서 cnt 에 더한다.

 

따라서 cnt는 1이므로 답은 true

 

 

풀이2. - leetcode 참조

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

 

 

n을 이진수로 표현했을때 1이 1개여야 한다. (위 풀이와동일)

n & (n-1) == 0 의미는, n을 2진수로 변경했을때 1이 한개라는 의미.

 

예를들어

15 -> 2진수로 표현하면 01111 X

16 -> 2진수로 표현하면 10000 (2의 제곱근 표현가능)

17 -> 2진수로 표현하면 10001 X

18 -> 2진수로 표현하면 10010 X

 

만약 n이 16이면, 10000 & 01111(16 & 15) 의 값은 '0' 이 나오므로 n 은 2의 제곱임을 알수있다.

만약 n이 17이면, 10001 & 10000(17 & 16) 의 값은 '1' 이 나오므로 n 은 2의 제곱근이 아니다.