Двоичные единицы

면접 대비

시간 제한1초메모리 제한1024 MB

요약

x가 10^18 이하이고 k가 60 이하일 때, x+y의 이진 표현에 1이 정확히 k개 있게 하는 가장 작은 음이 아닌 정수 y를 구한다.

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

문제

Рассмотрим натуральное число $x$ . Требуется прибавить к нему минимальное возможное целое неотрицательное число $y$ , чтобы двоичная запись получившегося числа $x+y$ имела ровно $k$ единиц.

입력

Первая строка ввода содержит натуральное число $x$ ( $1 \le x \le 10^{18}$ ).

Вторая строка ввода содержит натуральное число $k$ ( $1 \le k \le 60$ ).

출력

Выведите минимальное возможное целое неотрицательное число $y$ , такое что двоичная запись числа $x+y$ имеет ровно $k$ единиц.

예제1

예제 1
입력
```
20
4
```
예상 출력
```
3
```