tags:

views:

557

answers:

7

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.

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

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

Vladimir
I like how this wouldn't have needed to be asked if the function had been called `countBinaryOnes` instead of `f`. Also, +1.
Cam
+1. See 2a here - http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/
Dummy00001
Coding elegance: A+. Coding clarity: F.
Jay
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?
Martin York
@Jay, B+ perhaps. f(INT_MIN) invokes UB. Should be unsigned f(unsigned) IMHO.
Luther Blissett
Jay
A: 

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

TheBlastOne
Although I think @Vladimir's answer is technically accurate, I like this explanation best.
Randolpho
@Randolpho What? This answer is wrong. Given the input 0b1000 it would return 1, not 4 (the number of significant binary digits--bits)
Nick T
What does significant bits mean?
Amnon
@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).
Andreas Rejbrand
@Nick T: Ahh, I see that now.
Randolpho
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.
Nick T
@Andreas: thanks. So the answer would be to replace the 4th line with `n >>= 1`.
Amnon
Wow am I glad I mentioned that I had not thought about it until the end :) right in the beginning :)
TheBlastOne
+7  A: 

It is intended to show how important comments are.

progrmr
No, it is clearly not. It is intended to show how important good function names are.
Andreas Rejbrand
A descriptive function name might be considered a comment.
JeremyP
@JeremyP: Nope.
Cam
I think it's intended to see if a person is a good candidate for a job :)
Amnon
@Andreas: I agree, a good function name would have helped a lot!
progrmr
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)

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

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

mvds
+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.

Luther Blissett