diff options
| author | Marc Mutz <marc.mutz@kdab.com> | 2012-05-18 20:12:35 +0200 |
|---|---|---|
| committer | The Qt Project <gerrit-noreply@qt-project.org> | 2013-04-03 11:38:35 +0200 |
| commit | 76e0223619da02911d02813961ef631a5e02d826 (patch) | |
| tree | 0fafdd9293508a89c7baed92b8d269dc93a36670 /src/corelib/tools/qalgorithms.h | |
| parent | 6e7b8f79cb852ee1a6262a22aabd328b0e1b6dc0 (diff) | |
Add qPopulationCount() function, extracted from QBitArray
This functionality is used in multiple places in Qt itself, so it makes
sense to have a global function for this. This also allows to map this
onto specialized assembler instructions, should an architecture provide
them, later on.
Also added comprehensive tests, using a 4-bit lookup-table implementation
as a reference.
Change-Id: I8c4ea72cce54506ebb9fbe61141dbb5f1b7a660f
Reviewed-by: Stephen Kelly <stephen.kelly@kdab.com>
Diffstat (limited to 'src/corelib/tools/qalgorithms.h')
| -rw-r--r-- | src/corelib/tools/qalgorithms.h | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h index e3b76886f1..2658cfc2c2 100644 --- a/src/corelib/tools/qalgorithms.h +++ b/src/corelib/tools/qalgorithms.h @@ -516,6 +516,44 @@ Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator } //namespace QAlgorithmsPrivate +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint32 v) +{ + // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint8 v) +{ + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint16 v) +{ + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint64 v) +{ + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 36) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 48) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 60) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(long unsigned int v) +{ + return qPopulationCount(static_cast<quint64>(v)); +} + QT_END_NAMESPACE #endif // QALGORITHMS_H |