Codesignal Solution: Grouped Bits

Original Problem

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 10011101011, with the groups in bold.

Input/Output

• [time limit] 4000ms (js)

• [input] integer n

  Constraints:
  0 ≤ n ≤ 10⁹.

• [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 truth-table:

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