1 /******************************************************************************
2 ** $Header: svn+ssh://jmmcg@svn.code.sf.net/p/libjmmcg/code/trunk/libjmmcg/core/bit_fiddling.hpp 2055 2017-05-13 19:35:47Z jmmcg $
3 **
4 ** Copyright © 2016 by J.M.McGuiness, coder@hussar.me.uk
5 **
6 ** This library is free software; you can redistribute it and/or
7 ** modify it under the terms of the GNU Lesser General Public
8 ** License as published by the Free Software Foundation; either
9 ** version 2.1 of the License, or (at your option) any later version.
10 **
11 ** This library is distributed in the hope that it will be useful,
12 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 ** Lesser General Public License for more details.
15 **
16 ** You should have received a copy of the GNU Lesser General Public
17 ** License along with this library; if not, write to the Free Software
18 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20
21 namespace jmmcg { namespace mpl {
22
23 /// Create a bitmask of a contiguous block of zeros, then ones, starting at the compile-time constant, input number.
24 /**
25 Because the operator>>() is poorly defined this only works for unsigned types. This is because there may be a sign bit or two's complement representation of the negative number. Then shifting might cause the sign bit to be shifted into the number itself, possibly causing an infinite loop.
26
27 Complexity: compile-time: O(n) where n is at most the number of bits used to represent the input type.
28 run-time: O(1)
29 Space: O(1)
30 */
31 template<
32 unsigned long long MSetBit ///< The all-ones bitmask will start from the non-zero msb.
33 >
34 struct lsb_bitmask {
35 typedef unsigned long long element_type;
36
37 constexpr static element_type number=MSetBit;
38
39 enum : element_type {
40 value=MSetBit|(lsb_bitmask<(MSetBit>>1u)>::value)
41 };
42 };
43 /**
44 We can exit early if the number is shifted to zero.
45 */
46 template<>
47 struct lsb_bitmask<0u> {
48 typedef unsigned long long element_type;
49
50 constexpr static element_type number=0;
51
52 enum : element_type {
53 value=element_type()
54 };
55 };
56
57 /// Compute the bit position of the set bit, starting at the compile-time constant, input number.
58 /**
59 Because the operator>>() is poorly defined this only works for unsigned types. This is because there may be a sign bit or two's complement representation of the negative number. Then shifting might cause the sign bit to be shifted into the number itself, possibly causing an infinite loop.
60
61 Complexity: compile-time: O(n) where n is at most the number of bits used to represent the input type.
62 run-time: O(1)
63 Space: O(1)
64 */
65 template<
66 unsigned long long SetBit ///< The set bit in the field.
67 >
68 struct bit_position {
69 typedef unsigned long long element_type;
70
71 constexpr static element_type number=SetBit;
72
73 enum : element_type {
74 value=bit_position<(SetBit>>1u)>::value+1
75 };
76 };
77 template<>
78 struct bit_position<0ULL> {
79 typedef unsigned long long element_type;
80
81 constexpr static element_type number=0ULL;
82
83 enum : element_type {
84 value=0ULL
85 };
86 };
87
88 } }