Author vstinner PedanticHacker, gvanrossum, mark.dickinson, rhettinger, serhiy.storchaka, tim.peters, vstinner 2021-02-18.21:12:34 -1.0 Yes <1613682754.2.0.773003277313.issue43255@roundup.psfhosted.org>
Content
```> Mr. Stinner, in what way would int.bit_count() be beneficial to me?

I found https://www.chessprogramming.org/Population_Count when I investigated the C implementation of _Py_popcount32(), which is used by int.bit_count().

I read it when I tried to document this surprising code:
---
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
return (uint32_t)((uint64_t)x * (uint64_t)0x01010101) >> 24;
---

I reformatted it as:
---
// 32-bit SWAR (SIMD Within A Register) popcount

// Binary: 0 1 0 1 ...
const uint32_t M1 = 0x55555555;
// Binary: 00 11 00 11. ..
const uint32_t M2 = 0x33333333;
// Binary: 0000 1111 0000 1111 ...
const uint32_t M4 = 0x0F0F0F0F;
// 256**4 + 256**3 + 256**2 + 256**1
const uint32_t SUM = 0x01010101;

// Put count of each 2 bits into those 2 bits
x = x - ((x >> 1) & M1);
// Put count of each 4 bits into those 4 bits
x = (x & M2) + ((x >> 2) & M2);
// Put count of each 8 bits into those 8 bits
x = (x + (x >> 4)) & M4;
// Sum of the 4 byte counts
return (uint32_t)((uint64_t)x * (uint64_t)SUM) >> 24;
---```
History
Date User Action Args
2021-02-18 21:12:34vstinnersetrecipients: + vstinner, gvanrossum, tim.peters, rhettinger, mark.dickinson, serhiy.storchaka, PedanticHacker
2021-02-18 21:12:34vstinnersetmessageid: <1613682754.2.0.773003277313.issue43255@roundup.psfhosted.org>