Time complexity of writing a number as power of 2's I'm wondering about the time complexity of writing a number as power of 2's. For example writing $n=218$ as $2 + 2^3 + 2^4 + 2^6 + 2^7$.
It seems to me that we do $\lceil \log_2n \rceil $ divisions. Each division costs $O(n^2)$ so an upper bound is $O(n^2 \cdot \log_2n)$. However, this seems like a very loose upper bound to me as the number we start with gets smaller with each division. So, what would be a better upper bound on the time complexity of writing an integer $n$ as power of 2's ?
Division by 2 is linear in the number of digits (lets call that $s$) $O(s)$ aka. $O(\log n)$.

output = [];
bool carry;
for(digit in digits){ // most significant digit first
    if(carry) digit+=10;

    carry = isOdd(digit);
    push_front(output, floor(digit/2));

}
if(output.front == 0) pop_front(output);
//carry is the new bit to push to the front of the result
// and output is the new digit array


Because the number of digits decreases with a constant rate (1 digit every 3 to 4 divisions). This algorithm results in a $O(s^2)$ time complexity aka. $O(\log^2 n)$.