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.
| Keep up-to-date with our FREE Weekly Newsletter! | Don't miss out on upcoming issues of Circuit Cellar. Note: We’ve made the May 2020 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. — ADVERTISMENT— |
| 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. |
