tlx
Loading...
Searching...
No Matches
popcount.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/math/popcount.hpp
3 *
4 * popcount() population count number of one bits - mainly for portability.
5 *
6 * Part of tlx - http://panthema.net/tlx
7 *
8 * Copyright (C) 2018 Timo Bingmann <tb@panthema.net>
9 *
10 * All rights reserved. Published under the Boost Software License, Version 1.0
11 ******************************************************************************/
12
13#ifndef TLX_MATH_POPCOUNT_HEADER
14#define TLX_MATH_POPCOUNT_HEADER
15
16#include <cstdint>
17#include <cstdlib>
18
19#ifdef _MSC_VER
20#include <intrin.h>
21#endif
22
23namespace tlx {
24
25//! \addtogroup tlx_math
26//! \{
27
28/******************************************************************************/
29// popcount() - count one bits
30
31//! popcount (count one bits) - generic SWAR implementation
32static inline unsigned popcount_generic8(uint8_t x) {
33 x = x - ((x >> 1) & 0x55);
34 x = (x & 0x33) + ((x >> 2) & 0x33);
35 return static_cast<uint8_t>((x + (x >> 4)) & 0x0F);
36}
37
38//! popcount (count one bits) - generic SWAR implementation
39static inline unsigned popcount_generic16(uint16_t x) {
40 x = x - ((x >> 1) & 0x5555);
41 x = (x & 0x3333) + ((x >> 2) & 0x3333);
42 return static_cast<uint16_t>(((x + (x >> 4)) & 0x0F0F) * 0x0101) >> 8;
43}
44
45//! popcount (count one bits) -
46//! generic SWAR implementation from https://stackoverflow.com/questions/109023
47static inline unsigned popcount_generic32(uint32_t x) {
48 x = x - ((x >> 1) & 0x55555555);
49 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
50 return (((x + (x >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
51}
52
53//! popcount (count one bits) - generic SWAR implementation
54static inline unsigned popcount_generic64(uint64_t x) {
55 x = x - ((x >> 1) & 0x5555555555555555);
56 x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
57 return (((x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) >> 56;
58}
59
60/******************************************************************************/
61
62#if defined(__GNUC__) || defined(__clang__)
63
64//! popcount (count one bits)
65static inline unsigned popcount(unsigned i) {
66 return static_cast<unsigned>(__builtin_popcount(i));
67}
68
69//! popcount (count one bits)
70static inline unsigned popcount(int i) {
71 return popcount(static_cast<unsigned>(i));
72}
73
74//! popcount (count one bits)
75static inline unsigned popcount(unsigned long i) {
76 return static_cast<unsigned>(__builtin_popcountl(i));
77}
78
79//! popcount (count one bits)
80static inline unsigned popcount(long i) {
81 return popcount(static_cast<unsigned long>(i));
82}
83
84//! popcount (count one bits)
85static inline unsigned popcount(unsigned long long i) {
86 return static_cast<unsigned>(__builtin_popcountll(i));
87}
88
89//! popcount (count one bits)
90static inline unsigned popcount(long long i) {
91 return popcount(static_cast<unsigned long long>(i));
92}
93
94#elif defined(_MSC_VER)
95
96//! popcount (count one bits)
97template <typename Integral>
98inline unsigned popcount(Integral i) {
99 if (sizeof(i) <= sizeof(int))
100 return __popcnt(i);
101 else {
102#if defined(_WIN64)
103 return __popcnt64(i);
104#else
105 return popcount_generic64(i);
106#endif
107 }
108}
109
110#else
111
112//! popcount (count one bits)
113template <typename Integral>
114inline unsigned popcount(Integral i) {
115 if (sizeof(i) <= sizeof(uint8_t))
116 return popcount_generic8(i);
117 else if (sizeof(i) <= sizeof(uint16_t))
118 return popcount_generic16(i);
119 else if (sizeof(i) <= sizeof(uint32_t))
120 return popcount_generic32(i);
121 else if (sizeof(i) <= sizeof(uint64_t))
122 return popcount_generic64(i);
123 else
124 abort();
125}
126
127#endif
128
129/******************************************************************************/
130// popcount range
131
132static inline
133size_t popcount(const void* data, size_t size) {
134 const uint8_t* begin = reinterpret_cast<const uint8_t*>(data);
135 const uint8_t* end = begin + size;
136 size_t total = 0;
137 while (begin + 7 < end) {
138 total += popcount(*reinterpret_cast<const uint64_t*>(begin));
139 begin += 8;
140 }
141 if (begin + 3 < end) {
142 total += popcount(*reinterpret_cast<const uint32_t*>(begin));
143 begin += 4;
144 }
145 while (begin < end) {
146 total += popcount(*begin++);
147 }
148 return total;
149}
150
151//! \}
152
153} // namespace tlx
154
155#endif // !TLX_MATH_POPCOUNT_HEADER
156
157/******************************************************************************/
static unsigned popcount_generic8(uint8_t x)
popcount (count one bits) - generic SWAR implementation
Definition: popcount.hpp:32
unsigned popcount(Integral i)
popcount (count one bits)
Definition: popcount.hpp:114
static unsigned popcount_generic32(uint32_t x)
popcount (count one bits) - generic SWAR implementation from https://stackoverflow....
Definition: popcount.hpp:47
static unsigned popcount_generic16(uint16_t x)
popcount (count one bits) - generic SWAR implementation
Definition: popcount.hpp:39
static unsigned popcount_generic64(uint64_t x)
popcount (count one bits) - generic SWAR implementation
Definition: popcount.hpp:54