Понимание записи википедии о Кривых Дракона

Question

Я играю с Project Euler Problem 220 , и меня немного смущает статья в Википедии на эту тему Кривая Дракона . На тему вычисления направления n-го поворота без необходимости рисовать всю кривую, он говорит:

Во-первых, выразите n в форме k * 2 ^ m, где k - нечетное число. Направление n-го поворота определяется k mod 4, то есть остаток остается, когда k делится на 4. Если k mod 4 равно 1, то n-й ход равен R; если k mod 4 равно 3, то n-й ход равен L.

Например, для определения направления поворота 76376:

76376 = 9547 x 8.
9547 = 2386x4 + 3
so 9547 mod 4 = 3
so turn 76376 is L

• Есть ли умный способ выяснить, можно ли выразить n как k2 ^ m, кроме проверки делимости последовательными степенями 2?
• Что это значит, если n не может быть выражено таким образом?

(Проблема заключается в том, чтобы вычислить положение точки на кривой Дракона длиной 2 ^ 50, поэтому рисование кривой не может быть и речи.)

Answer 1

m - это число нулевых битов в младшем значащем конце числа. Самый простой алгоритм - делить на 2, пока число четное, но вы также можете использовать двоичный поиск, чтобы ускорить его.

Все целые числа могут быть выражены таким образом.

Answer 2

Любое целое число может быть выражено как k * 2 ^ m, где k нечетно. Чтобы понять почему, напишите любое число в двоичном виде. Начиная справа (младший значащий бит), будет строка из всех нулей. Это может быть пустая строка. Количество нулей м. Остальные биты составляют k. младший значащий бит k равен единице (потому что если бы он был нулем, вы бы просто расширили строку нулей), поэтому k нечетно.

Чтобы найти k и m, вы, вероятно, напишите простой цикл (в данном случае Python):

def k_and_m(n):
    k, m = n, 0
    while (k % 2) == 0:
        k >>= 1
        m += 1
    return k, m