Test Your EQ (Engineering Quotient)

EQ #1

10/13/2019
Written by Circuit Cellar Staff

What does the following C function compute?

int foo (int n)
{
  int k = 0;
  int t;
  while (t = n & -n) {
    ++k;
    n &= ~t;
  }
  return k;
}

This function counts the number of ones in the binary representation of the input argument. The expression n & -n has at most one bit set—in the position of the least-significant “one” in n— which is the only bit that a number and its two’s-complement negation have in common.

Each iteration of the loop identifies one “one” bit in n, and then the expression n &= ~t clears that bit for the next iteration. The variable k counts how many times this occurs.

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—

You may also like