Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
clz.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/math/clz.hpp
3  *
4  * clz() count leading zeros - mainly for portability.
5  *
6  * Part of tlx - http://panthema.net/tlx
7  *
8  * Copyright (C) 2017 Timo Bingmann <[email protected]>
9  *
10  * All rights reserved. Published under the Boost Software License, Version 1.0
11  ******************************************************************************/
12 
13 #ifndef TLX_MATH_CLZ_HEADER
14 #define TLX_MATH_CLZ_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 // clz() - count leading zeros
27 
28 //! clz (count leading zeros) - generic implementation
29 template <typename Integral>
30 static inline unsigned clz_template(Integral x) {
31  if (x == 0) return 8 * sizeof(x);
32  unsigned r = 0;
33  while ((x & (static_cast<Integral>(1) << (8 * sizeof(x) - 1))) == 0)
34  x <<= 1, ++r;
35  return r;
36 }
37 
38 /******************************************************************************/
39 
40 template <typename Integral>
41 inline unsigned clz(Integral x);
42 
43 #if defined(__GNUC__) || defined(__clang__)
44 
45 //! clz (count leading zeros)
46 template <>
47 inline unsigned clz<unsigned>(unsigned i) {
48  if (i == 0) return 8 * sizeof(i);
49  return static_cast<unsigned>(__builtin_clz(i));
50 }
51 
52 //! clz (count leading zeros)
53 template <>
54 inline unsigned clz<int>(int i) {
55  return clz(static_cast<unsigned>(i));
56 }
57 
58 //! clz (count leading zeros)
59 template <>
60 inline unsigned clz<unsigned long>(unsigned long i) {
61  if (i == 0) return 8 * sizeof(i);
62  return static_cast<unsigned>(__builtin_clzl(i));
63 }
64 
65 //! clz (count leading zeros)
66 template <>
67 inline unsigned clz<long>(long i) {
68  return clz(static_cast<unsigned long>(i));
69 }
70 
71 //! clz (count leading zeros)
72 template <>
73 inline unsigned clz<unsigned long long>(unsigned long long i) {
74  if (i == 0) return 8 * sizeof(i);
75  return static_cast<unsigned>(__builtin_clzll(i));
76 }
77 
78 //! clz (count leading zeros)
79 template <>
80 inline unsigned clz<long long>(long long i) {
81  return clz(static_cast<unsigned long long>(i));
82 }
83 
84 #elif defined(_MSC_VER)
85 
86 //! clz (count leading zeros)
87 template <typename Integral>
88 inline unsigned clz<unsigned>(Integral i) {
89  unsigned long leading_zeros = 0;
90  if (sizeof(i) > 4) {
91 #if defined(_WIN64)
92  if (_BitScanReverse64(&leading_zeros, i))
93  return 63 - leading_zeros;
94  else
95  return 8 * sizeof(i);
96 #else
97  return clz_template(i);
98 #endif
99  }
100  else {
101  if (_BitScanReverse(&leading_zeros, static_cast<unsigned>(i)))
102  return 31 - leading_zeros;
103  else
104  return 8 * sizeof(i);
105  }
106 }
107 
108 #else
109 
110 //! clz (count leading zeros)
111 template <>
112 inline unsigned clz<int>(int i) {
113  return clz_template(i);
114 }
115 
116 //! clz (count leading zeros)
117 template <>
118 inline unsigned clz<unsigned>(unsigned i) {
119  return clz_template(i);
120 }
121 
122 //! clz (count leading zeros)
123 template <>
124 inline unsigned clz<long>(long i) {
125  return clz_template(i);
126 }
127 
128 //! clz (count leading zeros)
129 template <>
130 inline unsigned clz<unsigned long>(unsigned long i) {
131  return clz_template(i);
132 }
133 
134 //! clz (count leading zeros)
135 template <>
136 inline unsigned clz<long long>(long long i) {
137  return clz_template(i);
138 }
139 
140 //! clz (count leading zeros)
141 template <>
142 inline unsigned clz<unsigned long long>(unsigned long long i) {
143  return clz_template(i);
144 }
145 
146 #endif
147 
148 //! \}
149 
150 } // namespace tlx
151 
152 #endif // !TLX_MATH_CLZ_HEADER
153 
154 /******************************************************************************/
unsigned clz(Integral x)
unsigned clz< unsigned long >(unsigned long i)
clz (count leading zeros)
Definition: clz.hpp:130
unsigned clz< unsigned >(unsigned i)
clz (count leading zeros)
Definition: clz.hpp:118
list x
Definition: gen_data.py:39
unsigned clz< long long >(long long i)
clz (count leading zeros)
Definition: clz.hpp:136
static unsigned clz_template(Integral x)
clz (count leading zeros) - generic implementation
Definition: clz.hpp:30
unsigned clz< int >(int i)
clz (count leading zeros)
Definition: clz.hpp:112
unsigned clz< unsigned long long >(unsigned long long i)
clz (count leading zeros)
Definition: clz.hpp:142
unsigned clz< long >(long i)
clz (count leading zeros)
Definition: clz.hpp:124