Is there a way to determine if half of an even number will be odd or even? For example 100 is even and 100/2= 50 is also even
But 30 is also even but 30/2=15 is odd
Now let's say I have a number as large as 10^10000000000...
I want to know how many steps are involved in cutting this number in half. When the number is even, I divide it by 2. When it's odd, I subtract 1. I continue this process until I hit 0.
However, when the number is too high, I can't actually manipulate it directly (elaboration: too big to write out, and too big to fit into memory on a computer), so I am curious if there's a way for me to do this by just knowing the even/odd attributes along the chain.
I hope this makes sense!
Example:
If n=100, I have the following chain
100, 50, 25, 24, 12, 6, 3, 2, 1, 0
Which is a total of 9 "splitting steps" (10 if you count the original number)
And the following parities
Even, Even, Odd, Even, Even, Even, Odd, Even, Odd, Even
I am asking if, given n=10, there is a way to get this parity chain
 A: Yes you can get the chain for $n=10$, but for large numbers it is not easy.
Write your number $n$ in binary. What you are doing is the following:


*

*If the last digit is 0, you erase it.

*If the last digit is 1, you make it a zero.


For $n=10$ in binary you have $n=1010$. Thus your string is
$$1010 \to 101 \to 100 \to 10 \to 1 \to 0$$
In total, the number of digits is exactly the number of digits in binary (which is exactly $\log_2 n$ rounded up) plus the number of 1 in the binary representation 
A: Your sequence corresponds quirte directly with the binary representation of the original number: Starting form the least significant binary digit, each $0$ corresponds to "even, dide by two" and each $1$ corresponds to "odd, subtract one; even, divide by two".
For your example $n=100$, which is $1100100$ in binary we thus obtain
Even, divide by two;
even, divide by two; 
odd, subtract one, then  even, divide by two;
even, divide by two; 
even, divide by two; 
odd, subtract one, then even, divide by two;
odd, subtract one. Finally zero is even.
Thus determining your even/odd sequence is equivalent to determinig the binary representation of the given number.
