Timeline for Count the number of set bits in a 32-bit integer
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 13, 2021 at 3:45 | comment | added | Peter Cordes | @Alex: The first part of this is the same bithack as the accepted answer, it simply uses multiple two shift+add steps to horizontally sum 4 bytes into 1, instead of one multiply by a 0x01010101 constant to sum all 4 bytes into the high byte. (I would have done the x>>16 part first, to make the reduction work by narrowing the valuable part in half twice.) On a CPU without a fast multiplier, yes this is preferable (especially if it can do large shifts efficiently, not like 1 bit per cycle. Or if it has some other way to extract the high half; e.g. on a 16-bit CPU it would already be split | |
| Mar 5, 2019 at 10:56 | comment | added | Albert van der Horst | Note that in generalizing to 64-bit there is a problem. The result cannot be 64, because of the mask. | |
| Jul 7, 2017 at 13:23 | comment | added | Alex | And, this requires no multiplications, like the code in the accepted answer. | |
| Mar 18, 2015 at 18:51 | comment | added | Maarten Bodewes | Maybe hackers delight is delightful, but I would give a good kicking to anybody calling this pop instead of population_count (or pop_cnt if you must have an abreviation). @MarcoBolis I presume that will be true of all versions of Java, but officially that would be implementation dependent :) | |
| Feb 24, 2015 at 7:23 | comment | added | Jeremy Blum | Having a little trouble following this - how would it change if we only cared about 16-bit values, instead of 32-bit? | |
| Jan 5, 2015 at 16:33 | comment | added | Marco Bolis | The Java method Integer.bitCount(int) uses this same exact implementation. | |
| Apr 12, 2013 at 19:14 | history | made wiki | Post Made Community Wiki by vidit | ||
| Aug 9, 2012 at 21:38 | history | suggested | Pete | CC BY-SA 3.0 | link to citation |
| Aug 9, 2012 at 21:37 | review | Suggested edits | |||
| Aug 9, 2012 at 21:38 | |||||
| Sep 20, 2008 at 19:38 | history | answered | Kevin Little | CC BY-SA 2.5 |