# Codefights: 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 be`GroupedBits(n) = 4`

.

The binary representation of `1259`

is

, with the groups in bold.**1**00**111**0**1**0**11**

**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 **1**00**111**0**1**0**11: **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 truth-table:

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