tlx
Loading...
Searching...
No Matches
ctz.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/math/ctz.hpp
3 *
4 * ctz() count trailing zeros - mainly for portability.
5 *
6 * Part of tlx - http://panthema.net/tlx
7 *
8 * Copyright (C) 2019 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_CTZ_HEADER
14#define TLX_MATH_CTZ_HEADER
15
16#ifdef _MSC_VER
17#include <intrin.h>
18#endif
19
20namespace tlx {
21
22//! \addtogroup tlx_math
23//! \{
24
25/******************************************************************************/
26// ctz() - count trailing zeros
27
28//! ctz (count trailing zeros) - generic implementation
29template <typename Integral>
30static inline unsigned ctz_template(Integral x) {
31 if (x == 0) return 8 * sizeof(x);
32 unsigned r = 0;
33 while ((x & static_cast<Integral>(1)) == 0)
34 x >>= 1, ++r;
35 return r;
36}
37
38/******************************************************************************/
39
40template <typename Integral>
41inline unsigned ctz(Integral x);
42
43#if defined(__GNUC__) || defined(__clang__)
44
45//! ctz (count trailing zeros)
46template <>
47inline unsigned ctz<unsigned>(unsigned i) {
48 if (i == 0) return 8 * sizeof(i);
49 return static_cast<unsigned>(__builtin_ctz(i));
50}
51
52//! ctz (count trailing zeros)
53template <>
54inline unsigned ctz<int>(int i) {
55 return ctz(static_cast<unsigned>(i));
56}
57
58//! ctz (count trailing zeros)
59template <>
60inline unsigned ctz<unsigned long>(unsigned long i) {
61 if (i == 0) return 8 * sizeof(i);
62 return static_cast<unsigned>(__builtin_ctzl(i));
63}
64
65//! ctz (count trailing zeros)
66template <>
67inline unsigned ctz<long>(long i) {
68 return ctz(static_cast<unsigned long>(i));
69}
70
71//! ctz (count trailing zeros)
72template <>
73inline unsigned ctz<unsigned long long>(unsigned long long i) {
74 if (i == 0) return 8 * sizeof(i);
75 return static_cast<unsigned>(__builtin_ctzll(i));
76}
77
78//! ctz (count trailing zeros)
79template <>
80inline unsigned ctz<long long>(long long i) {
81 return ctz(static_cast<unsigned long long>(i));
82}
83
84#elif defined(_MSC_VER)
85
86//! ctz (count trailing zeros)
87template <typename Integral>
88inline unsigned ctz<unsigned>(Integral i) {
89 unsigned long trailing_zeros = 0;
90 if (sizeof(i) > 4) {
91#if defined(_WIN64)
92 if (_BitScanForward64(&trailing_zeros, i))
93 return trailing_zeros;
94 else
95 return 8 * sizeof(i);
96#else
97 return ctz_template(i);
98#endif
99 }
100 else {
101 if (_BitScanForward(&trailing_zeros, static_cast<unsigned>(i)))
102 return trailing_zeros;
103 else
104 return 8 * sizeof(i);
105 }
106}
107
108#else
109
110//! ctz (count trailing zeros)
111template <>
112inline unsigned ctz<int>(int i) {
113 return ctz_template(i);
114}
115
116//! ctz (count trailing zeros)
117template <>
118inline unsigned ctz<unsigned>(unsigned i) {
119 return ctz_template(i);
120}
121
122//! ctz (count trailing zeros)
123template <>
124inline unsigned ctz<long>(long i) {
125 return ctz_template(i);
126}
127
128//! ctz (count trailing zeros)
129template <>
130inline unsigned ctz<unsigned long>(unsigned long i) {
131 return ctz_template(i);
132}
133
134//! ctz (count trailing zeros)
135template <>
136inline unsigned ctz<long long>(long long i) {
137 return ctz_template(i);
138}
139
140//! ctz (count trailing zeros)
141template <>
142inline unsigned ctz<unsigned long long>(unsigned long long i) {
143 return ctz_template(i);
144}
145
146#endif
147
148//! \}
149
150} // namespace tlx
151
152#endif // !TLX_MATH_CTZ_HEADER
153
154/******************************************************************************/
unsigned ctz(Integral x)
unsigned ctz< long long >(long long i)
ctz (count trailing zeros)
Definition ctz.hpp:136
unsigned ctz< unsigned >(unsigned i)
ctz (count trailing zeros)
Definition ctz.hpp:118
unsigned ctz< unsigned long >(unsigned long i)
ctz (count trailing zeros)
Definition ctz.hpp:130
unsigned ctz< unsigned long long >(unsigned long long i)
ctz (count trailing zeros)
Definition ctz.hpp:142
unsigned ctz< int >(int i)
ctz (count trailing zeros)
Definition ctz.hpp:112
unsigned ctz< long >(long i)
ctz (count trailing zeros)
Definition ctz.hpp:124
static unsigned ctz_template(Integral x)
ctz (count trailing zeros) - generic implementation
Definition ctz.hpp:30