557

7
+15  Q:

## What does this function do?

I am reading a program which contains the following function, which is

``````int f(int n) {
int c;
for (c=0;n!=0;++c)
n=n&(n-1);
return c;
}
``````

I don't quite understand what does this function intend to do?

+3  A:

This counts the number of iterations it takes to reduce `n` to `0` by using a binary and.

Yes, but what is that number of iterations dependent on :P Vlad hit it.
@Nick; good point. I didn't think of that explanation, so I was just describing the mechanics rather than the intent.
+32  A:

It counts number of 1's in binary representation of n

I like how this wouldn't have needed to be asked if the function had been called `countBinaryOnes` instead of `f`. Also, +1.
+1. See 2a here - http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/
Coding elegance: A+. Coding clarity: F.
This kind of function not onlyt needs a good name but also a good comment block describing what it does. Even if the name was countBinaryOnes would you trust that is what it did?
@Jay, B+ perhaps. f(INT_MIN) invokes UB. Should be unsigned f(unsigned) IMHO.
A:

Could it be it tries to return the number of significant bits in n? (Haven't thought through it completely...)

Although I think @Vladimir's answer is technically accurate, I like this explanation best.
@Randolpho What? This answer is wrong. Given the input 0b1000 it would return 1, not 4 (the number of significant binary digits--bits)
What does significant bits mean?
@Ammon: The minumum number of binary digits that is required to represent the value, i.e. the position (1-based counting) of the last non-zero bit counting from the LSB (from right).
@Nick T: Ahh, I see that now.
Significant digits are those that have meaning. For integers represented in binary, the *in*significant digits are leading zeros. Fixed/floats are a little different.
@Andreas: thanks. So the answer would be to replace the 4th line with `n >>= 1`.
Wow am I glad I mentioned that I had not thought about it until the end :) right in the beginning :)
+7  A:

It is intended to show how important comments are.

No, it is clearly not. It is intended to show how important good function names are.
A descriptive function name might be considered a comment.
@JeremyP: Nope.
I think it's intended to see if a person is a good candidate for a job :)
@Andreas: I agree, a good function name would have helped a lot!
A:

It shows a way how not to program(for the x86 Instruction set), using a intrinsic/inline assembler instruction is faster and better to read for something simple like this. (but this is only true for a x86 Architecture as far as i know, i don't know how's it about ARM or SPARC or something else)

What's the assembly instruction that does it on a Freescale HCS08? :P
I think you need to justify that a bit more.
+3  A:

It is a (now obsolete) workaround for the lack of the POPCNT instruction in non-military cpu's.

+3  A:

The function is INTENDED to return the number of bits in the representation of n. What is missed out in the other answers is, that the function invokes undefined behaviour for arguments n < 0. This is because the function peels the number away one bit a time, starting from the lowest bit to the highest. For a negative number this means, that the last value of n before the loop terminates (for 32-bit integers in 2-complement) is 0x8000000. This number is INT_MIN and it is now used in the loop for the last time:

``````n = n&(n-1)
``````

Unfortunately, INT_MIN-1 is a overflow and overflows invoke undefined behavior. A conforming implementation is not required to "wrap around" integers, it may for example issue an overflow trap instead or leave all kinds of weird results.