https://codeforces.com/contest/1527/problem/A
시간 1초, 메모리 256MB
input :
output :
k
.k
를 출력하시오.조건 :
n
, find the maximum value of integer k
such that the following condition holds:n
에 대해서, 아래의 조건을 수행할 때 가장 큰 k
를 출력하시오.n & (n−1) & (n−2) & (n−3) & ... (k) = 0
입력된 값에 AND연산을 계속 수행해서 0으로 만드는 연산을 수행한다.
입력값이 17일 경우 비트로 나타내면 10001(2) 이다.
이를 AND 연산을 해서 0으로 만들려면 01110(2)이 필요한데 이 보다 큰 경우가 존재할까?
AND 연산을 꼭 바로 써야 하는 것이 아니다. 값을 더 줄인 후에 AND 연산을 수행해도 된다는 것이다.
10001(2)이 아닌 10000(2)에 AND 연산을 수행할 때 우리는 가장 큰 k
를 얻을 수 있다.
즉 n과 같거나 작은 수들 중 가장 큰 2의 제곱을 구해서 -1을 한 것이 정답이다.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
low, high = 1, 2
while high <= n:
low = high
high *= 2
print(low - 1)