사이에 있는 가장 희소한 수

면접 대비

시간 제한2초메모리 제한2048 MB

요약

a 이상 b 이하의 정수 중 이진수에서 1의 개수가 가장 적은 수를 구하되, 그런 수가 여러 개면 가장 작은 수를 찾습니다.

난이도: 보통10점 중 5점
유형: 비트 연산, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

양의 정수 $a$ 와 $b$ ( $a ≤ b$ )가 주어진다. $a$ 이상 $b$ 이하인 정수 중에서 이진수 표현에 1이 가장 적은 수, 즉 가장 희소한 수를 찾는다. 그런 수가 두 개 이상이면 그중 가장 작은 수를 찾는다.

예를 들어 $a = 10$ , $b = 13$ 이라고 하자. $a$ 부터 $b$ 까지의 정수는 $10$ , $11$ , $12$ , $13$ 이고, 이진수 표현은 각각 1010, 1011, 1100, 1101이다. $10$ 과 $12$ 는 모두 1의 개수가 가장 적고, $10$ 이 $12$ 보다 작으므로 답은 $10$ 이다.

입력

입력은 다음 형식으로 주어지는 테스트 케이스 하나이다.

$a$ $b$

여기서 $a$ 와 $b$ ( $a ≤ b$ )는 $1$ 이상 $10^{18}$ 이하의 정수이다.

출력

$a$ 이상 $b$ 이하인 가장 희소한 정수 중 가장 작은 수를 한 줄에 출력한다.

예제5

예제 1
입력
```
10 13
```
예상 출력
```
10
```
예제 2
입력
```
11 15
```
예상 출력
```
12
```
예제 3
입력
```
11 20
```
예상 출력
```
16
```
예제 4
입력
```
1 1000000000000000000
```
예상 출력
```
1
```
예제 5
입력
```
9876543210 9876543210
```
예상 출력
```
9876543210
```