tlx
Toggle main menu visibility
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
23
namespace
tlx
{
24
25
//! \addtogroup tlx_math
26
//! \{
27
28
/******************************************************************************/
29
// popcount() - count one bits
30
31
//! popcount (count one bits) - generic SWAR implementation
32
static
inline
unsigned
popcount_generic8
(std::uint8_t x) {
33
x = x - ((x >> 1) & 0x55);
34
x = (x & 0x33) + ((x >> 2) & 0x33);
35
return
static_cast<
std::uint8_t
>
((x + (x >> 4)) & 0x0F);
36
}
37
38
//! popcount (count one bits) - generic SWAR implementation
39
static
inline
unsigned
popcount_generic16
(std::uint16_t x) {
40
x = x - ((x >> 1) & 0x5555);
41
x = (x & 0x3333) + ((x >> 2) & 0x3333);
42
return
static_cast<
std::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
47
static
inline
unsigned
popcount_generic32
(std::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
54
static
inline
unsigned
popcount_generic64
(std::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)
65
static
inline
unsigned
popcount
(
unsigned
i) {
66
return
static_cast<
unsigned
>
(__builtin_popcount(i));
67
}
68
69
//! popcount (count one bits)
70
static
inline
unsigned
popcount
(
int
i) {
71
return
popcount
(
static_cast<
unsigned
>
(i));
72
}
73
74
//! popcount (count one bits)
75
static
inline
unsigned
popcount
(
unsigned
long
i) {
76
return
static_cast<
unsigned
>
(__builtin_popcountl(i));
77
}
78
79
//! popcount (count one bits)
80
static
inline
unsigned
popcount
(
long
i) {
81
return
popcount
(
static_cast<
unsigned
long
>
(i));
82
}
83
84
//! popcount (count one bits)
85
static
inline
unsigned
popcount
(
unsigned
long
long
i) {
86
return
static_cast<
unsigned
>
(__builtin_popcountll(i));
87
}
88
89
//! popcount (count one bits)
90
static
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)
97
template
<
typename
Integral>
98
inline
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)
113
template
<
typename
Integral>
114
inline
unsigned
popcount
(Integral i) {
115
if
(
sizeof
(i) <=
sizeof
(std::uint8_t))
116
return
popcount_generic8
(i);
117
else
if
(
sizeof
(i) <=
sizeof
(std::uint16_t))
118
return
popcount_generic16
(i);
119
else
if
(
sizeof
(i) <=
sizeof
(std::uint32_t))
120
return
popcount_generic32
(i);
121
else
if
(
sizeof
(i) <=
sizeof
(std::uint64_t))
122
return
popcount_generic64
(i);
123
else
124
abort();
125
}
126
127
#endif
128
129
/******************************************************************************/
130
// popcount range
131
132
static
inline
133
size_t
popcount
(
const
void
* data,
size_t
size) {
134
const
std::uint8_t* begin =
reinterpret_cast<
const
std::uint8_t*
>
(data);
135
const
std::uint8_t* end = begin + size;
136
size_t
total = 0;
137
while
(begin + 7 < end) {
138
total +=
popcount
(*
reinterpret_cast<
const
std::uint64_t*
>
(begin));
139
begin += 8;
140
}
141
if
(begin + 3 < end) {
142
total +=
popcount
(*
reinterpret_cast<
const
std::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
/******************************************************************************/
tlx::popcount_generic32
static unsigned popcount_generic32(std::uint32_t x)
popcount (count one bits) - generic SWAR implementation from https://stackoverflow....
Definition
popcount.hpp:47
tlx::popcount_generic16
static unsigned popcount_generic16(std::uint16_t x)
popcount (count one bits) - generic SWAR implementation
Definition
popcount.hpp:39
tlx::popcount_generic64
static unsigned popcount_generic64(std::uint64_t x)
popcount (count one bits) - generic SWAR implementation
Definition
popcount.hpp:54
tlx::popcount_generic8
static unsigned popcount_generic8(std::uint8_t x)
popcount (count one bits) - generic SWAR implementation
Definition
popcount.hpp:32
tlx::popcount
unsigned popcount(Integral i)
popcount (count one bits)
Definition
popcount.hpp:114
tlx
Definition
exclusive_scan.hpp:17
tlx
math
popcount.hpp
Generated on
for tlx by
1.17.0