Author vstinner
Recipients PedanticHacker, gvanrossum, mark.dickinson, rhettinger, serhiy.storchaka, tim.peters, vstinner
Date 2021-02-18.21:12:34
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1613682754.2.0.773003277313.issue43255@roundup.psfhosted.org>
In-reply-to
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>
2021-02-18 21:12:34vstinnerlinkissue43255 messages
2021-02-18 21:12:34vstinnercreate