You're of course completely correct, but I feel like that misses the point. The great thing about this algorithm is not that it works - there are plenty of ways

You're of course completely correct, but I feel like that misses the point. The great thing about this algorithm is not that it works - there are plenty of ways to figure out the binary representation of a number. Rather, it's that it only needs operations that are easy to perform and requires little state to remember. I'd much rather divide by two and round down than subtract the largest power of two that's less than my number from it. And I don't have to remember which power of N I last worked to know how many zeros I need to add before using the next power of 2 that fits in my number.