#### Topic: Prompt with the decision of task LeetCode

Given a nonnegative integer number num. For every number i in the range 0 <= i <= num calculate the number of 1's in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
The standard decision of the task:

``````int [] bits = new int [num + 1];
for (int i = 1; i &lt;= num; i ++) {
bits [i] = bits [i&gt;&gt; 1] + (i AND 1);
}
return bits;``````

Question: why "i&gt;&gt; 1"? We do shift in the right and as though bits look how many was in the previous digit?
But after all then it would be possible to do simply bits [i - 1] and it is stupid to take previous...
With "i&1" it is clear, it signals us that in the end of current number costs 1 or 0 and here it is necessary to increase/not to increase the counter

#### Re: Prompt with the decision of task LeetCode

drcosmo wrote:

Question: why "i&gt;&gt; 1"? We do shift in the right and as though bits look how many was in the previous digit?
But after all then it would be possible to do simply bits [i - 1] and it is stupid to take previous...

It turns out what stupidly to take previous does not quit, as the number  cannot grow all time

#### Re: Prompt with the decision of task LeetCode

"i&gt;&gt; 1" it i / 2, instead of previous.

#### Re: Prompt with the decision of task LeetCode

drcosmo;
Substantiation - unsuitable

#### Re: Prompt with the decision of task LeetCode

wrote:

drcosmo;
Substantiation - unsuitable

Yes.
Not about the previous number it is necessary to speak, and about number in binary representation without the most right bit. We also consider it at determination how many will be bits in other number (not is mandatory following for it in decimal representation), only without shift

#### Re: Prompt with the decision of task LeetCode

drcosmo;
f (n) =f (n/2) +lowerbit (n)