EQ #38

Suppose you have a 32-bit word in your microprocessor, and you want to count how many contiguous strings ones that appear in it. For example, the word “01110001000111101100011100011111” contains six such strings. Can you come up with an algorithm that uses simple shifts, bitwise logical and arithmetic operators, but —here’s the twist—does not require iterating over each bit in the word?

Here’s a solution that iterates over the number of strings, rather than the number of bits in the word.

`int nstrings (unsigned long int x){   int result = 0;   /* convert x into a word that has a '1' for every    * transition from 0 to 1 or 1 to 0 in the original    * word.    */   x ^= (x << 1);   /* every pair of ones in the new word represents   * a string of ones in the original word. Remove    * them two at a time and keep count.    */   while (x) {     /* remove the lowest set bit from x; this      * represents the start of a string of ones.      */     x &= ~(x & -x);     ++result;     /* remove the next set bit from x; this      * represents the end of that string of ones.      */     x &= ~(x & -x);   }   return result;}`

Keep up-to-date with our FREE Weekly Newsletter!

Don't miss out on upcoming issues of Circuit Cellar.