Бітове сортування

Визначимо таке відношення порядку на множині невід'ємних цілих чисел: для двох чисел $A$ і $B$, будемо вважати, що $A$ менше за $B$, якщо виконується одна з наступних умов:

1. Кількість одиниць у двійковому записі числа $A$ менша, ніж у $B$.

2. Кількість одиниць у двійковому записі числа $A$ дорівнює кількості одиниць у $B$, і при цьому A < B (у звичайному сенсі).

Тепер відсортуємо всі цілі числа від $0$ до $n$ включно за зростанням, використовуючи це нове відношення порядку. Ваше завдання — визначити, яке число буде знаходитись на позиції $k$. Нумерація позицій починається з одиниці.