[Solved]: counting binary, with moving position (turing machine)

Problem Detail: 

I'm trying to make a turing machine that will take in a binary string as input x and output the binary representation of the length of x. So M(0110) returns 100, M(1010101010) returns 1010, ect. It also has to have a runtime of O(N).

So I can prove that the number of "flips" (changing a 0 to a 1 or a 1 to a 0) that occur when counting from 1 to n in base 2 approaches 2n as n goes to infinity. meaning it's O(n) in terms of runtime, but i'm not sure how to factor in the movement of the head of the tape that is writing the binary. Near as I can tell, the head may have to move at most log(n) place to go from the 1s place to the last power of 2s place. For example, going from 11111 to 000001 requires moving from the 1s to the 64s place, or 6 places. It then has to move back to the ones to create the binary representation for 65.

How is this operation as a not O(nlogn)?

Asked By : Sveniat

Answered By : Terence Hang

Noting that every increment starts from the lowest significant bit (LSB). Consider each increment operation this way: starting from LSB, move towards MSB, flipping 1's to 0's until a 0 is encountered. Flip it to 1 and move back to LSB, stop. It is then clear that the total move distance is just double the number of flips.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/46954