Message387270
> 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;
--- |
|
| Date |
User |
Action |
Args |
| 2021-02-18 21:12:34 | vstinner | set | recipients:
+ vstinner, gvanrossum, tim.peters, rhettinger, mark.dickinson, serhiy.storchaka, PedanticHacker |
| 2021-02-18 21:12:34 | vstinner | set | messageid: <1613682754.2.0.773003277313.issue43255@roundup.psfhosted.org> |
| 2021-02-18 21:12:34 | vstinner | link | issue43255 messages |
| 2021-02-18 21:12:34 | vstinner | create | |
|