Codesignal Solution: Grouped Bits
Given an integer n
, count the number of groups of consecutive 1
bits in its binary representation.
Example
For n = 1259
, the output should beGroupedBits(n) = 4
.
The binary representation of 1259
is 10011101011
, with the groups in bold.
Input/Output
 [time limit] 4000ms (js)

[input] integer n
Constraints:
0 ≤ n ≤ 10^{9}
. 
[output] integer
The number of groups of
1
bits.
Solution
Analysis of 10011101011: When we work from right to left, we want to count a bit as new block when the previous digit was a zero and the current digit is a one. From this observation we can create a truthtable:
c  p  c&~p 

0  0  0 
0  1  0 
1  0  1 
1  1  0 
From this, the following algorithm can be formed:
GroupedBits = n => { s = p = 0 while (n) { c = n & 1 s+= c & ~p p = c n>>= 1 } return s }
Which simplifies to:
GroupedBits = n => { s = p = 0 while (n) { s+= n & ~p & 1 p = n & 1 n>>= 1 } return s }
But we can do better. We don't need to remember the previous bit, but can extract the last two digits and analyze them. Instead of the current bit, we make the previous bit count, but only if the current but is zero. By taking it mod 3, the last row in the table above becomes zero. By taking mod 2, the third row becomes zero as well and the only remaining bit is what we can sum:
GroupedBits = n => { s = 0 while (n) { s+= n % 4 % 3 % 2 n>>= 1 } return s }
To reduce the code size even more, we can formulate it as a recursive algorithm:
_ = GroupedBits = n => n ? n % 4 % 3 % 2 + _(n >> 1) : 0