Given an integer range [A,B],
(1) What’s the probability to get a 1-bit if we first randomly choose a number x in the range and then randomly choose a bit from x? (2) What’s the expected number of bit 1s if we randomly choose a number x in the range?
My approach is to iterate all the integers within [A,B], convert each one to binary numbers, and count the number of '1'. But I believe there are algorithms much faster?
Hint: The $2^j$'s bit of $x$ is $1$ iff $\lfloor x/2^j\rfloor$ is even. Find a formula for $f_j(x)$, the total number of $1$'s in $2^j$'s bits of integers from $0$ to $x$. Then the total number of $1$'s in $2^j$'s bits of integers from $A$ to $B$ (inclusive) is $f_j(B) - f_j(A-1)$.
Don't forget that you don't want to consider leading zeros, so if the range $[A,B]$ includes some powers of $2$ that has to be taken into account.