A code snippet to count the number of similar 1's in a bit-stream

Question

I was trying to count the number of consecutive bits of a bit-stream and I have this code. I assume that, this has to to run until when the number becomes 0 and the count then should return the value. But why is there no conditional statement to equate the number to zero(otherwise i doubt this can be an infinite loop) so that the execution jumps out of the loop and returns the count value once it's over. Please don't duplicate it as I'm only a kid without adequate reputation to comment any doubt.

 int count_consecutive_ones(int in) {
     int count = 0;
     while (in)
     {
         in = (in & (in << 1));
         count++;
     }
     return count;
 }

@shmosel Please don't mind the tag. I'm asking about the logic here. — Liswin, Jan 15 '17 at 06:29
This seems like C code. And in fact you have a conditional `in = (in & (in << 1))` Read this answer for more information: http://stackoverflow.com/a/141873/460557 — Jorge Campos, Jan 15 '17 at 06:32
In some languages, booleans and integers are interchangeable, with zero equating to false, and nonzero equating to true. `while (in)` means *while `in` is true*, or *while `in` is not 0*, or *until `in` equals 0*. — shmosel, Jan 15 '17 at 06:32
@shmosel That helped. I had to put a conditional statement inside the while loop. I tried using the above code with some necessary improvisations to use in Java and the thing worked. — Liswin, Jan 15 '17 at 07:26

score 0 · Answer 1 · answered Jan 15 '17 at 06:59

First of all: The code does not count the number of consecutive bits of a bitstream. All bits in a bitstream are consecutive. That's way it is called a bit stream. It counts the number of consecutive ones in a bitstream. No, not in a bitstream, but in an integer.

Let me explain that:

while(in)
{
  …
}

… is a while loop that runs as long as its condition is true. In C for a long time there has been no boolean type at all. A condition is false if the expression of any type is not a representation of zero, otherwise true. For integers that means, that the value of 0 is false, each other value is true. You can read that as …

while( in != 0)
{
  …
}

… with != in the meaning of unequal.

Inside the loop you have …:

in = (in & (in << 1));

This is a bit tricky: It moves the integer by one bit to the left (in << 1) and then computes the bit-and operation with the original value itself. This produces 1's on all places, where a 1 is aside a 1. Doing that over and over, it counts 1's being aside.

So you do not have to iterate over the bits to find a leading 1 and then the number of 1's following.

A code snippet to count the number of similar 1's in a bit-stream

1 Answers1