Fenwick Tree Traversal using Binary value of Index
Answering Question 2:

Simply count the number of 1's in the binary value. 

This is part of the beauty of Fenwick trees, they're very simple to implement. The whole algorithm for finding the sum up to some index i is:

sum = 0
while i &gt; 0:
    sum = sum + f_tree[i]
    i = i - (last set bit of i) // remove last set bit
return sum


At each step, we remove the last set bit from the index. Intuitively, the total amount of iterations is equal to however many set bits there are. You can find this in $O(\log i)$.

Answering Question 1:

Yes you do need to remove the last set bit. That is implicit on the structure of the tree. 

Let's say the last set bit of some index $i$ is bit $r$ (e.g. if $r = 0$ it is the least significant bit). The value in the Fenwick Tree at index $i$ is "responsible" for the sum of all values $[(i - 2^r + 1) \dots i]$. 

Now let's say index $i$ has set bits $\{r_0, r_1, \dots r_k\}$, that is, $i = \sum_{j = 0}^k 2^{r_j}$. We can then get the sum up to index $i$ in segments (iterations of the sum algorithm). Let $S_n$ denote the range that the accumulating some covers after the $n$th iteration.

$$\begin{align}
S_0 &amp; = [(i - 2^{r_0} + 1) \dots i]\\
S_1 &amp; = [(i - 2^{r_0} - 2^{r_1} + 1) \dots (i - 2^{r_0})] + [(i - 2^{r_0} + 1) \dots i]\\
&amp; \vdots\\
S_k &amp; = [1 \dots 2^k] + \dots + [(i - 2^{r_0} - 2^{r_1} + 1) \dots (i - 2^{r_0})] + [(i - 2^{r_0} + 1) \dots i] \\
S_k &amp; = [1 \dots i]
\end{align}$$

Example

This may be easier to visualize with an example. Take your first one for instance:


  001100100100100011$_2$ = 51491$_{10}$


I'm not going to go through all the math, I encourage you to do that. This is, in short, how it would work out with a total of 7 iterations.

$$\begin{align}
S_0 &amp; = [51491 \dots 51491]\\
S_1 &amp; = [51489 \dots 51490] + [51491 \dots 51491]\\
&amp; \vdots \\
S_6 &amp; = [1 \dots 32768] + \dots + [51489 \dots 51490] + [51491 \dots 51491]\\
S_6 &amp; = [1 \dots 51491]
\end{align}$$



A lot of this information came from this Topcoder Article on Binary Indexed Trees. I would highly recommend reading it if you have confusion with Fenwick Trees.