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?

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
2010-07-16 14:39:17

Yes, but what is that number of iterations dependent on :P Vlad hit it.

Nick T
2010-07-16 14:43:29
Amnon
2010-07-16 14:55:02

@Nick; good point. I didn't think of that explanation, so I was just describing the mechanics rather than the intent.

John Weldon
2010-07-16 14:56:10
I like how this wouldn't have needed to be asked if the function had been called `countBinaryOnes` instead of `f`. Also, +1.

Cam
2010-07-16 14:46:39
+1. See 2a here - http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

Dummy00001
2010-07-16 15:00:15
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
2010-07-16 16:00:43
@Jay, B+ perhaps. f(INT_MIN) invokes UB. Should be unsigned f(unsigned) IMHO.

Luther Blissett
2010-07-16 16:05:57
Jay
2010-07-16 21:43:27

A:

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

TheBlastOne
2010-07-16 14:39:52

Although I think @Vladimir's answer is technically accurate, I like this explanation best.

Randolpho
2010-07-16 14:41:15
@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
2010-07-16 14:45:15
@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
2010-07-16 14:50:15
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
2010-07-16 14:55:06
@Andreas: thanks. So the answer would be to replace the 4th line with `n >>= 1`.

Amnon
2010-07-16 14:59:56
Wow am I glad I mentioned that I had not thought about it until the end :) right in the beginning :)

TheBlastOne
2010-07-16 15:13:52
No, it is clearly not. It is intended to show how important good function names are.

Andreas Rejbrand
2010-07-16 14:45:01
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
2010-07-16 15:18:08

+3
A:

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

mvds
2010-07-16 15:29:24

+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
2010-07-16 16:28:04