A. Cards for Friends
문제요약
w * h 사이즈의 종이를 규칙에 맞게 최대로 나눌 때, 그 조각이 n개 이상이면 YES, 미만이면 NO 출력
규칙
- w가 짝수면 w/2으로 나눌 수 있다.
- h가 짝수면 h/2으로 나눌 수 있다.
제한 조건
1 <= w, h <= 104
풀이
- 결과는 (w로 나눠지는 개수) * (h로 나눠지는 개수)
- w, h로 나눈 각각의 개수는 2의 거듭제곱 형태이다.
- 즉, w=2^x*a , h = 2^y*b 의 형태일 때, 결과는 (2^x) * (2^y)
코드
- 바보같은 코드
w, h를 2로 나눠가면서 2^x, 2^y 를 구했다.
(2로 나누기 : w>>=1 , 2로 나눈 나머지 : w&1)
- 비트연산 마스터 코드
(w & ~w) * (h & ~h)
or
(w*h) & ~(w*h)
- 참고
~w 는 w의 비트를 뒤집고 +1을 하면 구할 수 있다.
w = 1011100(2) , ~w = 0100100(2)
