What does this function do?

Question

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?

Which goes to show that `f` is a terrible name for this function. — David Thornley, Jul 16 '10 at 14:41
The code looks bad, but after 30 seconds it appears rather elegant. And efficient. A good example of "why don't C programmers put more intention into their identifiers? Because they love to be cryptic enough to look powerful when they aren't.". — TheBlastOne, Jul 16 '10 at 14:42
Impressive how fast good answers and comments show up here at Stackoverflow. — TheBlastOne, Jul 16 '10 at 14:44
I approve of this code, I think I've had to hack together a few 'count the bits' routines before, but I think I'll use this next time. — Nick T, Jul 16 '10 at 14:46
I guess you get an "A" on this part of your homework assignment. — aaaa bbbb, Jul 16 '10 at 15:23
Everybody loves bit-twiddle! It's the finest form of discrete mathematics — rwong, Jul 16 '10 at 15:48
If you input 2 to this function it will return 1. Thats called Hacking!! — Praveen S, Jul 16 '10 at 17:11
I suspect that this is a homework assignment or quiz question of some sort, hence the name "f". — Rei Miyasaka, Jul 17 '10 at 00:04
You should simulate code like this by hand to see what it does, that way you'd learn more. — starblue, Jul 18 '10 at 12:55
David's right. f() as a name screams homework or an interview question. Many of user297850's questions seem to be interview questions, so that's probably what this is. — darron, Aug 20 '10 at 14:18

score 39 · Accepted Answer · edited May 23 '17 at 12:00

39

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

edited May 23 '17 at 12:00

Community

1
1

answered Jul 16 '10 at 14:39

Vladimir

170,431
36
387
313

9

I like how this wouldn't have needed to be asked if the function had been called `countBinaryOnes` instead of `f`. Also, +1. – Cam Jul 16 '10 at 14:46
+1. See 2a here - http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/ – Dummy00001 Jul 16 '10 at 15:00
2

Coding elegance: A+. Coding clarity: F. – Jay Jul 16 '10 at 15:29
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 Jul 16 '10 at 16:00
@Jay, B+ perhaps. f(INT_MIN) invokes UB. Should be unsigned f(unsigned) IMHO. – Nordic Mainframe Jul 16 '10 at 16:05
1

Oh, and personally I would have written "n&=n-1" for brevity. On the other hand I probably wouldn't have used a FOR loop, as I avoid having the test refer to a different value from the increment. I find that potentially confusing. – Jay Jul 16 '10 at 21:43

score 6 · Answer 2 · answered Jul 16 '10 at 16:28

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.

Counting set bits in a signed quantity is generally not what you want to do anyway. The function should just accept `unsigned int`. — Karl Knechtel, Aug 27 '11 at 23:48

score 5 · Answer 3 · answered Jul 16 '10 at 15:29

5

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

answered Jul 16 '10 at 15:29

mvds

45,755
8
102
111

score 4 · Answer 4 · answered Jul 16 '10 at 14:39

4

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

answered Jul 16 '10 at 14:39

John Weldon

39,849
11
94
127

Yes, but what is that number of iterations dependent on :P Vlad hit it. – Nick T Jul 16 '10 at 14:43
The answer is at most 1: n & 0 – Amnon Jul 16 '10 at 14:55
3

@Nick; good point. I didn't think of that explanation, so I was just describing the mechanics rather than the intent. – John Weldon Jul 16 '10 at 14:56

score 3 · Answer 5 · edited Mar 25 '18 at 14:43

3

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.

edited Mar 25 '18 at 14:43

Al.G.

4,327
6
31
56

answered Mar 25 '18 at 14:17

sai Charan

31
1

Quonux · Answer 6 · 2010-07-17T19:07:01.760

1

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)

edited Jul 17 '10 at 19:07

answered Jul 16 '10 at 15:18

Quonux

2,975
1
24
32

1

What's the assembly instruction that does it on a Freescale HCS08? :P – Nick T Jul 16 '10 at 15:34
I think you need to justify that a bit more. – BobbyShaftoe Jul 17 '10 at 18:42

score 0 · Answer 7 · answered Jul 16 '10 at 14:39

0

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

answered Jul 16 '10 at 14:39

TheBlastOne

4,291
3
38
72

Although I think @Vladimir's answer is technically accurate, I like this explanation best. – Randolpho Jul 16 '10 at 14:41
2

@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 Jul 16 '10 at 14:45
What does significant bits mean? – Amnon Jul 16 '10 at 14:48
@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 Jul 16 '10 at 14:50
@Nick T: Ahh, I see that now. – Randolpho Jul 16 '10 at 14:52
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 Jul 16 '10 at 14:55
@Andreas: thanks. So the answer would be to replace the 4th line with `n >>= 1`. – Amnon Jul 16 '10 at 14:59
1

Wow am I glad I mentioned that I had not thought about it until the end :) right in the beginning :) – TheBlastOne Jul 16 '10 at 15:13
The number of **set** bits. :) – Karl Knechtel Aug 27 '11 at 23:49

What does this function do?

7 Answers7

Linked

Related