Understanding the wikipedia entry on Dragon Curves

Question

I'm playing around with Project Euler's Problem 220, and I'm a little confused about the Wikipedia article on the topic, Dragon Curve. On the topic of calculating the direction of the nth turn without having to draw the entire curve, it says:

First, express n in the form k * 2^m where k is an odd number. The direction of the nth turn is determined by k mod 4 i.e. the remainder left when k is divided by 4. If k mod 4 is 1 then the nth turn is R; if k mod 4 is 3 then the nth turn is L.

For example, to determine the direction of turn 76376:

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

• Is there a clever way to figure out if n can be expressed as k2^m, apart from checking divisibility by successive powers of 2?
• What does it mean if n cannot be expressed in such a way?

(The problem involves calculating the position of a point on a Dragon curve with length 2^50, so actually drawing the curve is out of the question.)

Answer 1

m is the number of zero bits at the least significant end of the number. The simplest algorithm is to divide by 2 as long as the number is even, but you could also use binary search to speed it up.

All integers can be expressed in this way.

Answer 2

Any integer can be expressed as k * 2^m where k is odd. To see why, write any number in binary. Starting from the right (least significant bit), there will be a string of all zeros. It might be an empty string. The number of zeros is m. The rest of the bits make up k. k's least significant bit is a one (because if it were a zero, you'd simply extend your string of zeros), so k is odd.

To find k and m, you'll probably write a simple loop (Python in this case):

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