Thrill  0.1
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 <[email protected]>
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 
20 namespace tlx {
21 
22 //! \addtogroup tlx_math
23 //! \{
24 
25 /******************************************************************************/
26 // ctz() - count trailing zeros
27 
28 //! ctz (count trailing zeros) - generic implementation
29 template <typename Integral>
30 static 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 
40 template <typename Integral>
41 inline unsigned ctz(Integral x);
42 
43 #if defined(__GNUC__) || defined(__clang__)
44 
45 //! ctz (count trailing zeros)
46 template <>
47 inline 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)
53 template <>
54 inline unsigned ctz<int>(int i) {
55  return ctz(static_cast<unsigned>(i));
56 }
57 
58 //! ctz (count trailing zeros)
59 template <>
60 inline 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)
66 template <>
67 inline unsigned ctz<long>(long i) {
68  return ctz(static_cast<unsigned long>(i));
69 }
70 
71 //! ctz (count trailing zeros)
72 template <>
73 inline 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)
79 template <>
80 inline 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)
87 template <typename Integral>
88 inline 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)
111 template <>
112 inline unsigned ctz<int>(int i) {
113  return ctz_template(i);
114 }
115 
116 //! ctz (count trailing zeros)
117 template <>
118 inline unsigned ctz<unsigned>(unsigned i) {
119  return ctz_template(i);
120 }
121 
122 //! ctz (count trailing zeros)
123 template <>
124 inline unsigned ctz<long>(long i) {
125  return ctz_template(i);
126 }
127 
128 //! ctz (count trailing zeros)
129 template <>
130 inline unsigned ctz<unsigned long>(unsigned long i) {
131  return ctz_template(i);
132 }
133 
134 //! ctz (count trailing zeros)
135 template <>
136 inline unsigned ctz<long long>(long long i) {
137  return ctz_template(i);
138 }
139 
140 //! ctz (count trailing zeros)
141 template <>
142 inline 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< unsigned >(unsigned i)
ctz (count trailing zeros)
Definition: ctz.hpp:118
static unsigned ctz_template(Integral x)
ctz (count trailing zeros) - generic implementation
Definition: ctz.hpp:30
unsigned ctz< long long >(long long i)
ctz (count trailing zeros)
Definition: ctz.hpp:136
unsigned ctz< unsigned long >(unsigned long i)
ctz (count trailing zeros)
Definition: ctz.hpp:130
unsigned ctz< long >(long i)
ctz (count trailing zeros)
Definition: ctz.hpp:124
list x
Definition: gen_data.py:39
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