# Hamming weight of powers

Given positive integers $b$ and $e$, what is known about the space and time complexity of finding the Hamming weight (number of binary 1s) of $b^e$?

If $e\log b$ bits are available, the number can simply be calculated by standard techniques and the 1s counted. But what techniques are possible when less memory can be used?

• Why don't you compute in Chinese remainder representation, use the Chiu-Davida-Litow algorithm to convert to binary representation in logarithmic space, and then just count? – Markus Bläser Oct 5 '11 at 21:19
• @MarkusBläser answer ? – Suresh Venkat Oct 5 '11 at 22:21

You can do it with $O(\log e + \log \log b)$ space as follows:
1) First compute $b^e$ in Chinese remainder representation modulo sufficiently many primes.
3) Finally, just count the number of $1$'s.