Test Your EQ (Engineering Quotient)

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;
}


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

 
 
Note: We’ve made the October 2017 issue of Circuit Cellar available as a free sample issue. In it, you’ll find a rich variety of the kinds of articles and information that exemplify a typical issue of the current magazine.


Would you like to write for Circuit Cellar? We are always accepting articles/posts from the technical community. Get in touch with us and let's discuss your ideas.

— ADVERTISMENT—

Advertise Here