Reputation: 8005

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?

Upvotes: 22

Answers (7)

sai Charan

Reputation: 31

The expression n = n & (n - 1) is a bitwise operation which replaces the rightmost bit '1' to '0' in n.

For examle, take an integer 5 (0101). Then n & (n - 1) → (0101) & (0100) → 0100 (removes first '1' bit from right side).

So the above code returns the number of 1's in binary form of given integer.

Upvotes: 3

Quonux

Reputation: 2991

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)

Upvotes: 1

Nordic Mainframe

Reputation: 28737

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.

Upvotes: 6