SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
bits.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef INCLUDED_SDSL_BITS
9#define INCLUDED_SDSL_BITS
10
11#include <cassert>
12#include <iostream> // for cerr
13#include <stdint.h> // for uint64_t uint32_t declaration
14#ifdef __SSE4_2__
15#include <xmmintrin.h>
16#endif
17#ifdef __BMI2__
18#include <x86intrin.h>
19#endif
20
21#ifdef WIN32
22#include <iso646.h>
23#endif
24
26namespace sdsl
27{
28
30
44template <typename T = void>
46{
47 bits_impl() = delete;
49 constexpr static uint64_t all_set{ -1ULL };
50
52
57 constexpr static uint64_t deBruijn64{ 0x0218A392CD3D5DBFULL };
58
60
62 constexpr static uint32_t lt_deBruijn_to_idx[64] = {
63 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15, 46,
64 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47,
65 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58
66 };
67
69 constexpr static uint64_t lt_fib[92] = { 1,
70 2,
71 3,
72 5,
73 8,
74 13,
75 21,
76 34,
77 55,
78 89,
79 144,
80 233,
81 377,
82 610,
83 987,
84 1597,
85 2584,
86 4181,
87 6765,
88 10946,
89 17711,
90 28657,
91 46368,
92 75025,
93 121393,
94 196418,
95 317811,
96 514229,
97 832040,
98 1346269,
99 2178309,
100 3524578,
101 5702887,
102 9227465,
103 14930352,
104 24157817,
105 39088169,
106 63245986,
107 102334155,
108 165580141,
109 267914296,
110 433494437,
111 701408733,
112 1134903170,
113 1836311903,
114 2971215073ULL,
115 0x11e8d0a40ULL,
116 0x1cfa62f21ULL,
117 0x2ee333961ULL,
118 0x4bdd96882ULL,
119 0x7ac0ca1e3ULL,
120 0xc69e60a65ULL,
121 0x1415f2ac48ULL,
122 0x207fd8b6adULL,
123 0x3495cb62f5ULL,
124 0x5515a419a2ULL,
125 0x89ab6f7c97ULL,
126 0xdec1139639ULL,
127 0x1686c8312d0ULL,
128 0x2472d96a909ULL,
129 0x3af9a19bbd9ULL,
130 0x5f6c7b064e2ULL,
131 0x9a661ca20bbULL,
132 0xf9d297a859dULL,
133 0x19438b44a658ULL,
134 0x28e0b4bf2bf5ULL,
135 0x42244003d24dULL,
136 0x6b04f4c2fe42ULL,
137 0xad2934c6d08fULL,
138 0x1182e2989ced1ULL,
139 0x1c5575e509f60ULL,
140 0x2dd8587da6e31ULL,
141 0x4a2dce62b0d91ULL,
142 0x780626e057bc2ULL,
143 0xc233f54308953ULL,
144 0x13a3a1c2360515ULL,
145 0x1fc6e116668e68ULL,
146 0x336a82d89c937dULL,
147 0x533163ef0321e5ULL,
148 0x869be6c79fb562ULL,
149 0xd9cd4ab6a2d747ULL,
150 0x16069317e428ca9ULL,
151 0x23a367c34e563f0ULL,
152 0x39a9fadb327f099ULL,
153 0x5d4d629e80d5489ULL,
154 0x96f75d79b354522ULL,
155 0xf444c01834299abULL,
156 0x18b3c1d91e77decdULL,
157 0x27f80ddaa1ba7878ULL,
158 0x40abcfb3c0325745ULL,
159 0x68a3dd8e61eccfbdULL,
160 0xa94fad42221f2702ULL };
161
163 constexpr static uint8_t lt_cnt[256] = {
164 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2,
165 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
166 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
167 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
168 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4,
169 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
170 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
171 };
172
174 constexpr static uint32_t lt_hi[256] = {
175 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
176 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
177 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
178 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
179 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
180 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
181 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
182 };
183
185
187 constexpr static uint64_t lo_set[65] = {
188 0x0000000000000000ULL, 0x0000000000000001ULL, 0x0000000000000003ULL, 0x0000000000000007ULL,
189 0x000000000000000FULL, 0x000000000000001FULL, 0x000000000000003FULL, 0x000000000000007FULL,
190 0x00000000000000FFULL, 0x00000000000001FFULL, 0x00000000000003FFULL, 0x00000000000007FFULL,
191 0x0000000000000FFFULL, 0x0000000000001FFFULL, 0x0000000000003FFFULL, 0x0000000000007FFFULL,
192 0x000000000000FFFFULL, 0x000000000001FFFFULL, 0x000000000003FFFFULL, 0x000000000007FFFFULL,
193 0x00000000000FFFFFULL, 0x00000000001FFFFFULL, 0x00000000003FFFFFULL, 0x00000000007FFFFFULL,
194 0x0000000000FFFFFFULL, 0x0000000001FFFFFFULL, 0x0000000003FFFFFFULL, 0x0000000007FFFFFFULL,
195 0x000000000FFFFFFFULL, 0x000000001FFFFFFFULL, 0x000000003FFFFFFFULL, 0x000000007FFFFFFFULL,
196 0x00000000FFFFFFFFULL, 0x00000001FFFFFFFFULL, 0x00000003FFFFFFFFULL, 0x00000007FFFFFFFFULL,
197 0x0000000FFFFFFFFFULL, 0x0000001FFFFFFFFFULL, 0x0000003FFFFFFFFFULL, 0x0000007FFFFFFFFFULL,
198 0x000000FFFFFFFFFFULL, 0x000001FFFFFFFFFFULL, 0x000003FFFFFFFFFFULL, 0x000007FFFFFFFFFFULL,
199 0x00000FFFFFFFFFFFULL, 0x00001FFFFFFFFFFFULL, 0x00003FFFFFFFFFFFULL, 0x00007FFFFFFFFFFFULL,
200 0x0000FFFFFFFFFFFFULL, 0x0001FFFFFFFFFFFFULL, 0x0003FFFFFFFFFFFFULL, 0x0007FFFFFFFFFFFFULL,
201 0x000FFFFFFFFFFFFFULL, 0x001FFFFFFFFFFFFFULL, 0x003FFFFFFFFFFFFFULL, 0x007FFFFFFFFFFFFFULL,
202 0x00FFFFFFFFFFFFFFULL, 0x01FFFFFFFFFFFFFFULL, 0x03FFFFFFFFFFFFFFULL, 0x07FFFFFFFFFFFFFFULL,
203 0x0FFFFFFFFFFFFFFFULL, 0x1FFFFFFFFFFFFFFFULL, 0x3FFFFFFFFFFFFFFFULL, 0x7FFFFFFFFFFFFFFFULL,
204 0xFFFFFFFFFFFFFFFFULL
205 };
206
208
210 constexpr static uint64_t lo_unset[65] = {
211 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFF8ULL,
212 0xFFFFFFFFFFFFFFF0ULL, 0xFFFFFFFFFFFFFFE0ULL, 0xFFFFFFFFFFFFFFC0ULL, 0xFFFFFFFFFFFFFF80ULL,
213 0xFFFFFFFFFFFFFF00ULL, 0xFFFFFFFFFFFFFE00ULL, 0xFFFFFFFFFFFFFC00ULL, 0xFFFFFFFFFFFFF800ULL,
214 0xFFFFFFFFFFFFF000ULL, 0xFFFFFFFFFFFFE000ULL, 0xFFFFFFFFFFFFC000ULL, 0xFFFFFFFFFFFF8000ULL,
215 0xFFFFFFFFFFFF0000ULL, 0xFFFFFFFFFFFE0000ULL, 0xFFFFFFFFFFFC0000ULL, 0xFFFFFFFFFFF80000ULL,
216 0xFFFFFFFFFFF00000ULL, 0xFFFFFFFFFFE00000ULL, 0xFFFFFFFFFFC00000ULL, 0xFFFFFFFFFF800000ULL,
217 0xFFFFFFFFFF000000ULL, 0xFFFFFFFFFE000000ULL, 0xFFFFFFFFFC000000ULL, 0xFFFFFFFFF8000000ULL,
218 0xFFFFFFFFF0000000ULL, 0xFFFFFFFFE0000000ULL, 0xFFFFFFFFC0000000ULL, 0xFFFFFFFF80000000ULL,
219 0xFFFFFFFF00000000ULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFF800000000ULL,
220 0xFFFFFFF000000000ULL, 0xFFFFFFE000000000ULL, 0xFFFFFFC000000000ULL, 0xFFFFFF8000000000ULL,
221 0xFFFFFF0000000000ULL, 0xFFFFFE0000000000ULL, 0xFFFFFC0000000000ULL, 0xFFFFF80000000000ULL,
222 0xFFFFF00000000000ULL, 0xFFFFE00000000000ULL, 0xFFFFC00000000000ULL, 0xFFFF800000000000ULL,
223 0xFFFF000000000000ULL, 0xFFFE000000000000ULL, 0xFFFC000000000000ULL, 0xFFF8000000000000ULL,
224 0xFFF0000000000000ULL, 0xFFE0000000000000ULL, 0xFFC0000000000000ULL, 0xFF80000000000000ULL,
225 0xFF00000000000000ULL, 0xFE00000000000000ULL, 0xFC00000000000000ULL, 0xF800000000000000ULL,
226 0xF000000000000000ULL, 0xE000000000000000ULL, 0xC000000000000000ULL, 0x8000000000000000ULL,
227 0x0000000000000000ULL
228 };
229
231 constexpr static uint8_t lt_lo[256] = {
232 0x00, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00,
233 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00,
234 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00,
235 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
236 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00,
237 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
238 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00,
239 0x01, 0x00, 0x07, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
240 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00,
241 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00,
242 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x06, 0x00, 0x01, 0x00, 0x02, 0x00,
243 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
244 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00,
245 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
246 0x02, 0x00, 0x01, 0x00
247 };
248
250
253 constexpr static uint8_t lt_sel[256 * 8] = {
254 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2,
255 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0,
256 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1,
257 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0,
258 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,
259 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
260 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
261
262 0, 0, 0, 1, 0, 2, 2, 1, 0, 3, 3, 1, 3, 2, 2, 1, 0, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 0, 5, 5, 1, 5,
263 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 0, 6, 6, 1, 6, 2, 2, 1, 6, 3,
264 3, 1, 3, 2, 2, 1, 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2,
265 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 0, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1, 7, 4, 4, 1,
266 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4,
267 3, 3, 1, 3, 2, 2, 1, 7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2,
268 2, 1, 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
269
270 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 3, 3, 2, 0, 0, 0, 4, 0, 4, 4, 2, 0, 4, 4, 3, 4, 3, 3, 2, 0, 0, 0, 5, 0,
271 5, 5, 2, 0, 5, 5, 3, 5, 3, 3, 2, 0, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2, 0, 0, 0, 6, 0, 6, 6, 2, 0, 6,
272 6, 3, 6, 3, 3, 2, 0, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2, 0, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3,
273 2, 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2, 0, 0, 0, 7, 0, 7, 7, 2, 0, 7, 7, 3, 7, 3, 3, 2, 0, 7, 7, 4,
274 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2, 0, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2, 7, 5, 5, 4, 5, 4, 4, 2, 5,
275 4, 4, 3, 4, 3, 3, 2, 0, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2, 7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3,
276 3, 2, 7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2, 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
277
278 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 4, 0, 4, 4, 3, 0, 0, 0, 0, 0,
279 0, 0, 5, 0, 0, 0, 5, 0, 5, 5, 3, 0, 0, 0, 5, 0, 5, 5, 4, 0, 5, 5, 4, 5, 4, 4, 3, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0,
280 0, 6, 0, 6, 6, 3, 0, 0, 0, 6, 0, 6, 6, 4, 0, 6, 6, 4, 6, 4, 4, 3, 0, 0, 0, 6, 0, 6, 6, 5, 0, 6, 6, 5, 6, 5, 5,
281 3, 0, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 3, 0, 0, 0, 7,
282 0, 7, 7, 4, 0, 7, 7, 4, 7, 4, 4, 3, 0, 0, 0, 7, 0, 7, 7, 5, 0, 7, 7, 5, 7, 5, 5, 3, 0, 7, 7, 5, 7, 5, 5, 4, 7,
283 5, 5, 4, 5, 4, 4, 3, 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 3, 0, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4,
284 4, 3, 0, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3, 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
285
286 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0,
287 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 5, 5, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
288 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 4, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6,
289 5, 0, 0, 0, 6, 0, 6, 6, 5, 0, 6, 6, 5, 6, 5, 5, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0,
290 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 4, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 5, 0, 0, 0, 7, 0, 7, 7, 5, 0,
291 7, 7, 5, 7, 5, 5, 4, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6, 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6,
292 6, 4, 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 5, 0, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
293
294 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
295 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
296 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
297 6, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
298 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 7, 0,
299 0, 0, 7, 0, 7, 7, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7,
300 7, 6, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6, 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 5,
301
302 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
303 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
304 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
305 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
306 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
307 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
308 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
309
310 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
311 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
312 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
313 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
314 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
315 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
316 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
317 };
318
320 constexpr static uint64_t ps_overflow[65] = {
321 0x8080808080808080ULL, 0x7f7f7f7f7f7f7f7fULL, 0x7e7e7e7e7e7e7e7eULL, 0x7d7d7d7d7d7d7d7dULL,
322 0x7c7c7c7c7c7c7c7cULL, 0x7b7b7b7b7b7b7b7bULL, 0x7a7a7a7a7a7a7a7aULL, 0x7979797979797979ULL,
323 0x7878787878787878ULL, 0x7777777777777777ULL, 0x7676767676767676ULL, 0x7575757575757575ULL,
324 0x7474747474747474ULL, 0x7373737373737373ULL, 0x7272727272727272ULL, 0x7171717171717171ULL,
325 0x7070707070707070ULL, 0x6f6f6f6f6f6f6f6fULL, 0x6e6e6e6e6e6e6e6eULL, 0x6d6d6d6d6d6d6d6dULL,
326 0x6c6c6c6c6c6c6c6cULL, 0x6b6b6b6b6b6b6b6bULL, 0x6a6a6a6a6a6a6a6aULL, 0x6969696969696969ULL,
327 0x6868686868686868ULL, 0x6767676767676767ULL, 0x6666666666666666ULL, 0x6565656565656565ULL,
328 0x6464646464646464ULL, 0x6363636363636363ULL, 0x6262626262626262ULL, 0x6161616161616161ULL,
329 0x6060606060606060ULL, 0x5f5f5f5f5f5f5f5fULL, 0x5e5e5e5e5e5e5e5eULL, 0x5d5d5d5d5d5d5d5dULL,
330 0x5c5c5c5c5c5c5c5cULL, 0x5b5b5b5b5b5b5b5bULL, 0x5a5a5a5a5a5a5a5aULL, 0x5959595959595959ULL,
331 0x5858585858585858ULL, 0x5757575757575757ULL, 0x5656565656565656ULL, 0x5555555555555555ULL,
332 0x5454545454545454ULL, 0x5353535353535353ULL, 0x5252525252525252ULL, 0x5151515151515151ULL,
333 0x5050505050505050ULL, 0x4f4f4f4f4f4f4f4fULL, 0x4e4e4e4e4e4e4e4eULL, 0x4d4d4d4d4d4d4d4dULL,
334 0x4c4c4c4c4c4c4c4cULL, 0x4b4b4b4b4b4b4b4bULL, 0x4a4a4a4a4a4a4a4aULL, 0x4949494949494949ULL,
335 0x4848484848484848ULL, 0x4747474747474747ULL, 0x4646464646464646ULL, 0x4545454545454545ULL,
336 0x4444444444444444ULL, 0x4343434343434343ULL, 0x4242424242424242ULL, 0x4141414141414141ULL,
337 0x4040404040404040ULL
338 };
339
341
344 constexpr static uint64_t cnt(uint64_t x);
345
347
352 constexpr static uint32_t hi(uint64_t x);
353
355
360 constexpr static uint32_t lo(uint64_t x);
361
363
369 constexpr static uint32_t cnt32(uint32_t x);
370
372
376 constexpr static uint32_t cnt11(uint64_t x, uint64_t & c);
377
379
382 constexpr static uint32_t cnt11(uint64_t x);
383
385
389 constexpr static uint32_t cnt10(uint64_t x, uint64_t & c);
390
392
396 constexpr static uint32_t cnt01(uint64_t x, uint64_t & c);
397
399 constexpr static uint64_t map10(uint64_t x, uint64_t c = 0);
400
402 constexpr static uint64_t map01(uint64_t x, uint64_t c = 1);
403
405
411 constexpr static uint32_t sel(uint64_t x, uint32_t i);
412 constexpr static uint32_t _sel(uint64_t x, uint32_t i);
413
415
423 constexpr static uint32_t sel11(uint64_t x, uint32_t i, uint32_t c = 0);
424
426
432 constexpr static uint32_t hi11(uint64_t x);
433
435 constexpr static void write_int(uint64_t * word, uint64_t x, const uint8_t offset = 0, const uint8_t len = 64);
436
438 constexpr static void write_int_and_move(uint64_t *& word, uint64_t x, uint8_t & offset, const uint8_t len);
439
441 constexpr static uint64_t read_int(const uint64_t * word, uint8_t offset = 0, const uint8_t len = 64);
442 constexpr static uint64_t read_int_bounded(const uint64_t * word, uint8_t offset = 0, const uint8_t len = 64);
443
445 constexpr static uint64_t read_int_and_move(const uint64_t *& word, uint8_t & offset, const uint8_t len = 64);
446
448 constexpr static uint64_t read_unary(const uint64_t * word, uint8_t offset = 0);
449 constexpr static uint64_t read_unary_bounded(const uint64_t * word, uint8_t offset = 0);
450
452 constexpr static uint64_t read_unary_and_move(const uint64_t *& word, uint8_t & offset);
453
455
460 constexpr static void move_right(const uint64_t *& word, uint8_t & offset, const uint8_t len);
461
463
468 constexpr static void move_left(const uint64_t *& word, uint8_t & offset, const uint8_t len);
469
471 constexpr static uint64_t next(const uint64_t * word, uint64_t idx);
472
474 constexpr static uint64_t prev(const uint64_t * word, uint64_t idx);
475
477 constexpr static uint64_t rev(uint64_t x);
478};
479
480// ============= inline - implementations ================
481
482// see page 11, Knuth TAOCP Vol 4 F1A
483template <typename T>
484constexpr uint64_t bits_impl<T>::cnt(uint64_t x)
485{
486#ifdef __SSE4_2__
487 return __builtin_popcountll(x);
488#else
489#ifdef POPCOUNT_TL
490 return lt_cnt[x & 0xFFULL] + lt_cnt[(x >> 8) & 0xFFULL] + lt_cnt[(x >> 16) & 0xFFULL] +
491 lt_cnt[(x >> 24) & 0xFFULL] + lt_cnt[(x >> 32) & 0xFFULL] + lt_cnt[(x >> 40) & 0xFFULL] +
492 lt_cnt[(x >> 48) & 0xFFULL] + lt_cnt[(x >> 56) & 0xFFULL];
493#else
494 x = x - ((x >> 1) & 0x5555555555555555ull);
495 x = (x & 0x3333333333333333ull) + ((x >> 2) & 0x3333333333333333ull);
496 x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0full;
497 return (0x0101010101010101ull * x >> 56);
498#endif
499#endif
500}
501
502template <typename T>
503constexpr uint32_t bits_impl<T>::cnt32(uint32_t x)
504{
505#ifdef __SSE4_2__
506 return __builtin_popcount(x);
507#else
508 x = x - ((x >> 1) & 0x55555555);
509 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
510 return (0x10101010 * x >> 28) + (0x01010101 * x >> 28);
511#endif
512}
513
514// We produce a 1 bit in the upper bit of each disjoint 2-bit group of
515// ones, and then count the 1 bits.
516//
517// Consider a 2-bit group at an even position that does not receive a
518// carry from the '+':
519//
520// x ^ + ^ & carry
521// 00 01 10 11 00
522// 01 00 01 00 00
523// 10 11 00 01 00 x
524// 11 10 11 10 10
525//
526// We get an 1 bit if and only if we have a 2-bit group that is to be
527// counted, and a carry is produced if and only if the top bit is a 1
528// that could start another 2-bit group.
529//
530// For a 2-bit group that does receive a carry:
531//
532// ^ + ^ & carry
533// 00 01 11 10 00
534// 01 00 10 11 01
535// 10 11 01 00 00 x
536// 11 10 00 01 01 x
537//
538// Also here we get the correct 1 bits and carries.
539//
540template <typename T>
541constexpr uint32_t bits_impl<T>::cnt11(uint64_t x, uint64_t & c)
542{
543 uint64_t t1 = x ^ 0x5555555555555555ULL;
544 uint64_t t2 = t1 + 0x5555555555555555ULL + c;
545 c = t1 > t2; // detect overflow in the sum
546 return cnt((t2 ^ 0x5555555555555555ULL) & x);
547}
548
549template <typename T>
550constexpr uint32_t bits_impl<T>::cnt11(uint64_t x)
551{
552 return cnt((((x ^ 0x5555555555555555ULL) + 0x5555555555555555ULL) ^ 0x5555555555555555ULL) & x);
553}
554
555template <typename T>
556constexpr uint32_t bits_impl<T>::cnt10(uint64_t x, uint64_t & c)
557{
558 uint32_t res = cnt(((x << 1) | c) & (~x));
559 c = (x >> 63);
560 return res;
561}
562
563template <typename T>
564constexpr uint64_t bits_impl<T>::map10(uint64_t x, uint64_t c)
565{
566 return (((x << 1) | c) & (~x));
567}
568
569template <typename T>
570constexpr uint32_t bits_impl<T>::cnt01(uint64_t x, uint64_t & c)
571{
572 uint32_t res = cnt((x ^ ((x << 1) | c)) & x);
573 c = (x >> 63);
574 return res;
575}
576
577template <typename T>
578constexpr uint64_t bits_impl<T>::map01(uint64_t x, uint64_t c)
579{
580 return ((x ^ ((x << 1) | c)) & x);
581}
582
583template <typename T>
584constexpr uint32_t bits_impl<T>::sel(uint64_t x, uint32_t i)
585{
586#if defined(__BMI__) && defined(__BMI2__)
587 // taken from folly
588 return _tzcnt_u64(_pdep_u64(1ULL << (i - 1), x));
589#endif
590#ifdef __SSE4_2__
591 uint64_t s = x, b{};
592 s = s - ((s >> 1) & 0x5555555555555555ULL);
593 s = (s & 0x3333333333333333ULL) + ((s >> 2) & 0x3333333333333333ULL);
594 s = (s + (s >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
595 s = 0x0101010101010101ULL * s;
596 // now s contains 8 bytes s[7],...,s[0]; s[j] contains the cumulative sum
597 // of (j+1)*8 least significant bits of s
598 b = (s + ps_overflow[i]) & 0x8080808080808080ULL;
599 // ps_overflow contains a bit mask x consisting of 8 bytes
600 // x[7],...,x[0] and x[j] is set to 128-j
601 // => a byte b[j] in b is >= 128 if cum sum >= j
602
603 // __builtin_ctzll returns the number of trailing zeros, if b!=0
604 int byte_nr = __builtin_ctzll(b) >> 3; // byte nr in [0..7]
605 s <<= 8;
606 i -= (s >> (byte_nr << 3)) & 0xFFULL;
607 return (byte_nr << 3) + lt_sel[((i - 1) << 8) + ((x >> (byte_nr << 3)) & 0xFFULL)];
608#endif
609 return _sel(x, i);
610}
611
612template <typename T>
613constexpr uint32_t bits_impl<T>::_sel(uint64_t x, uint32_t i)
614{
615 uint64_t s = x, b{}; // s = sum
616 s = s - ((s >> 1) & 0x5555555555555555ULL);
617 s = (s & 0x3333333333333333ULL) + ((s >> 2) & 0x3333333333333333ULL);
618 s = (s + (s >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
619 s = 0x0101010101010101ULL * s;
620 b = (s + ps_overflow[i]); //&0x8080808080808080ULL;// add something to the partial sums to cause overflow
621 i = (i - 1) << 8;
622 if (b & 0x0000000080000000ULL) // byte <=3
623 if (b & 0x0000000000008000ULL) // byte <= 1
624 if (b & 0x0000000000000080ULL)
625 return lt_sel[(x & 0xFFULL) + i];
626 else
627 return 8 + lt_sel[(((x >> 8) & 0xFFULL) + i - ((s & 0xFFULL) << 8)) & 0x7FFULL]; // byte 1;
628 else // byte >1
629 if (b & 0x0000000000800000ULL) // byte <=2
630 return 16 + lt_sel[(((x >> 16) & 0xFFULL) + i - (s & 0xFF00ULL)) & 0x7FFULL]; // byte 2;
631 else
632 return 24 + lt_sel[(((x >> 24) & 0xFFULL) + i - ((s >> 8) & 0xFF00ULL)) & 0x7FFULL]; // byte 3;
633 else // byte > 3
634 if (b & 0x0000800000000000ULL) // byte <=5
635 if (b & 0x0000008000000000ULL) // byte <=4
636 return 32 + lt_sel[(((x >> 32) & 0xFFULL) + i - ((s >> 16) & 0xFF00ULL)) & 0x7FFULL]; // byte 4;
637 else
638 return 40 + lt_sel[(((x >> 40) & 0xFFULL) + i - ((s >> 24) & 0xFF00ULL)) & 0x7FFULL]; // byte 5;
639 else // byte >5
640 if (b & 0x0080000000000000ULL) // byte<=6
641 return 48 + lt_sel[(((x >> 48) & 0xFFULL) + i - ((s >> 32) & 0xFF00ULL)) & 0x7FFULL]; // byte 6;
642 else
643 return 56 + lt_sel[(((x >> 56) & 0xFFULL) + i - ((s >> 40) & 0xFF00ULL)) & 0x7FFULL]; // byte 7;
644 return 0;
645}
646
647// using built-in method or
648// 64-bit version of 32-bit proposal of
649// http://www-graphics.stanford.edu/~seander/bithacks.html
650template <typename T>
651constexpr uint32_t bits_impl<T>::hi(uint64_t x)
652{
653#ifdef __SSE4_2__
654 if (x == 0) return 0;
655 return 63 - __builtin_clzll(x);
656#else
657 uint64_t t{}, tt{}; // temporaries
658 if ((tt = x >> 32))
659 { // hi >= 32
660 if ((t = tt >> 16))
661 { // hi >= 48
662 return (tt = t >> 8) ? 56 + lt_hi[tt] : 48 + lt_hi[t];
663 }
664 else
665 { // hi < 48
666 return (t = tt >> 8) ? 40 + lt_hi[t] : 32 + lt_hi[tt];
667 }
668 }
669 else
670 { // hi < 32
671 if ((t = x >> 16))
672 { // hi >= 16
673 return (tt = t >> 8) ? 24 + lt_hi[tt] : 16 + lt_hi[t];
674 }
675 else
676 { // hi < 16
677 return (tt = x >> 8) ? 8 + lt_hi[tt] : lt_hi[x];
678 }
679 }
680#endif
681}
682
683// details see: http://citeseer.ist.psu.edu/leiserson98using.html
684// or page 10, Knuth TAOCP Vol 4 F1A
685template <typename T>
686constexpr uint32_t bits_impl<T>::lo(uint64_t x)
687{
688#ifdef __SSE4_2__
689 if (x == 0) return 0;
690 return __builtin_ctzll(x);
691#else
692 if (x & 1) return 0;
693 if (x & 3) return 1;
694 if (x & 7) return 2;
695 if (x & 0x7FF)
696 { // in average every second random number x can be answered this way
697 return lt_lo[(x & 0x7FF) >> 3] + 3;
698 }
699 // x&-x equals x with only the lsb set
700 return lt_deBruijn_to_idx[((x & -x) * deBruijn64) >> 58];
701#endif
702}
703
704template <typename T>
705constexpr uint32_t bits_impl<T>::hi11(uint64_t x)
706{
707 return hi((((x ^ 0x5555555555555555ULL) + 0x5555555555555555ULL) ^ 0x5555555555555555ULL) & x);
708}
709
710template <typename T>
711constexpr uint32_t bits_impl<T>::sel11(uint64_t x, uint32_t i, uint32_t c)
712{
713 return sel((((x ^ 0x5555555555555555ULL) + 0x5555555555555555ULL + c) ^ 0x5555555555555555ULL) & x, i);
714}
715
716template <typename T>
717constexpr void bits_impl<T>::write_int(uint64_t * word, uint64_t x, uint8_t offset, const uint8_t len)
718{
719 x &= bits_impl<T>::lo_set[len];
720 if (offset + len < 64)
721 {
722 *word &= ((bits_impl<T>::all_set << (offset + len)) | bits_impl<T>::lo_set[offset]); // mask 1..10..01..1
723 *word |= (x << offset);
724 // *word ^= ((*word ^ x) & (bits_impl<T>::lo_set[len] << offset) );
725 // surprisingly the above line is slower than the lines above
726 }
727 else
728 {
729 *word &= ((bits_impl<T>::lo_set[offset])); // mask 0....01..1
730 *word |= (x << offset);
731 if ((offset = (offset + len) & 0x3F))
732 { // offset+len > 64
733 *(word + 1) &= (~bits_impl<T>::lo_set[offset]); // mask 1...10..0
734 // *(word+1) &= bits_impl<T>::lo_unset[offset]; // mask 1...10..0
735 // surprisingly the above line is slower than the line above
736 *(word + 1) |= (x >> (len - offset));
737 }
738 }
739}
740
741template <typename T>
742constexpr void bits_impl<T>::write_int_and_move(uint64_t *& word, uint64_t x, uint8_t & offset, const uint8_t len)
743{
744 x &= bits_impl<T>::lo_set[len];
745 if (offset + len < 64)
746 {
747 *word &= ((bits_impl<T>::all_set << (offset + len)) | bits_impl<T>::lo_set[offset]); // mask 1..10..01..1
748 *word |= (x << offset);
749 offset += len;
750 }
751 else
752 {
753 *word &= ((bits_impl<T>::lo_set[offset])); // mask 0....01..1
754 *word |= (x << offset);
755 if ((offset = (offset + len)) > 64)
756 { // offset+len >= 64
757 offset &= 0x3F;
758 *(++word) &= (~bits_impl<T>::lo_set[offset]); // mask 1...10..0
759 *word |= (x >> (len - offset));
760 }
761 else
762 {
763 offset = 0;
764 ++word;
765 }
766 }
767}
768
769template <typename T>
770constexpr uint64_t bits_impl<T>::read_int(const uint64_t * word, uint8_t offset, const uint8_t len)
771{
772 uint64_t w1 = (*word) >> offset;
773 if ((offset + len) > 64)
774 { // if offset+len > 64
775 return w1 | // w1 or w2 adepted:
776 ((*(word + 1) & bits_impl<T>::lo_set[(offset + len) & 0x3F]) // set higher bits zero
777 << (64 - offset)); // move bits to the left
778 }
779 else
780 {
781 return w1 & bits_impl<T>::lo_set[len];
782 }
783}
784
785template <typename T>
786constexpr uint64_t bits_impl<T>::read_int_bounded(const uint64_t * word, uint8_t offset, const uint8_t len)
787{
788 return ((*word) >> offset) & bits_impl<T>::lo_set[len];
789}
790
791template <typename T>
792constexpr uint64_t bits_impl<T>::read_int_and_move(const uint64_t *& word, uint8_t & offset, const uint8_t len)
793{
794 uint64_t w1 = (*word) >> offset;
795 if ((offset = (offset + len)) >= 64)
796 { // if offset+len > 64
797 if (offset == 64)
798 {
799 offset &= 0x3F;
800 ++word;
801 return w1;
802 }
803 else
804 {
805 offset &= 0x3F;
806 return w1 | (((*(++word)) & bits_impl<T>::lo_set[offset]) << (len - offset));
807 }
808 }
809 else
810 {
811 return w1 & bits_impl<T>::lo_set[len];
812 }
813}
814
815template <typename T>
816constexpr uint64_t bits_impl<T>::read_unary(const uint64_t * word, uint8_t offset)
817{
818 uint64_t w = *word >> offset;
819 if (w) { return bits_impl<T>::lo(w); }
820 else
821 {
822 if (0 != (w = *(++word))) return bits_impl<T>::lo(w) + 64 - offset;
823 uint64_t cnt = 2;
824 while (0 == (w = *(++word))) ++cnt;
825 return bits_impl<T>::lo(w) + (cnt << 6) - offset;
826 }
827 return 0;
828}
829
830template <typename T>
831constexpr uint64_t bits_impl<T>::read_unary_bounded(const uint64_t * word, uint8_t offset)
832{
833 uint64_t w = *word >> offset;
834 if (w) { return bits_impl<T>::lo(w); }
835 else
836 {
837 return 0;
838 }
839}
840
841template <typename T>
842constexpr uint64_t bits_impl<T>::read_unary_and_move(const uint64_t *& word, uint8_t & offset)
843{
844 uint64_t w = (*word) >> offset; // temporary variable is good for the performance
845 if (w)
846 {
847 uint8_t r = bits_impl<T>::lo(w);
848 offset = (offset + r + 1) & 0x3F;
849 // we know that offset + r +1 <= 64, so if the new offset equals 0 increase word
850 word += (offset == 0);
851 return r;
852 }
853 else
854 {
855 uint8_t rr = 0;
856 if (0 != (w = *(++word)))
857 {
858 rr = bits_impl<T>::lo(w) + 64 - offset;
859 offset = (offset + rr + 1) & 0x3F;
860 word += (offset == 0);
861 return rr;
862 }
863 else
864 {
865 uint64_t cnt_1 = 1;
866 while (0 == (w = *(++word))) ++cnt_1;
867 rr = bits_impl<T>::lo(w) + 64 - offset;
868 offset = (offset + rr + 1) & 0x3F;
869 word += (offset == 0);
870 return ((cnt_1) << 6) + rr;
871 }
872 }
873 return 0;
874}
875
876template <typename T>
877constexpr void bits_impl<T>::move_right(const uint64_t *& word, uint8_t & offset, const uint8_t len)
878{
879 if ((offset += len) & 0xC0)
880 { // if offset >= 65
881 offset &= 0x3F;
882 ++word;
883 }
884}
885
886template <typename T>
887constexpr void bits_impl<T>::move_left(const uint64_t *& word, uint8_t & offset, const uint8_t len)
888{
889 if ((offset -= len) & 0xC0)
890 { // if offset-len<0
891 offset &= 0x3F;
892 --word;
893 }
894}
895
896template <typename T>
897constexpr uint64_t bits_impl<T>::next(const uint64_t * word, uint64_t idx)
898{
899 word += (idx >> 6);
900 if (*word & ~lo_set[idx & 0x3F]) { return (idx & ~((size_t)0x3F)) + lo(*word & ~lo_set[idx & 0x3F]); }
901 idx = (idx & ~((size_t)0x3F)) + 64;
902 ++word;
903 while (*word == 0)
904 {
905 idx += 64;
906 ++word;
907 }
908 return idx + lo(*word);
909}
910
911template <typename T>
912constexpr uint64_t bits_impl<T>::prev(const uint64_t * word, uint64_t idx)
913{
914 word += (idx >> 6);
915 if (*word & lo_set[(idx & 0x3F) + 1]) { return (idx & ~((size_t)0x3F)) + hi(*word & lo_set[(idx & 0x3F) + 1]); }
916 idx = (idx & ~((size_t)0x3F)) - 64;
917 --word;
918 while (*word == 0)
919 {
920 idx -= 64;
921 --word;
922 }
923 return idx + hi(*word);
924}
925
926template <typename T>
927constexpr uint64_t bits_impl<T>::rev(uint64_t x)
928{
929 x = ((x & 0x5555555555555555ULL) << 1) | ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1);
930 x = ((x & 0x3333333333333333ULL) << 2) | ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2);
931 x = ((x & 0x0F0F0F0F0F0F0F0FULL) << 4) | ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4);
932 x = ((x & 0x00FF00FF00FF00FFULL) << 8) | ((x & 0xFF00FF00FF00FF00ULL) >> 8);
933 x = ((x & 0x0000FFFF0000FFFFULL) << 16) | ((x & 0xFFFF0000FFFF0000ULL) >> 16);
934 x = ((x & 0x00000000FFFFFFFFULL) << 32) | ((x & 0xFFFFFFFF00000000ULL) >> 32);
935 return x;
936}
937
938template <typename T>
939constexpr uint8_t bits_impl<T>::lt_cnt[256];
940template <typename T>
941constexpr uint32_t bits_impl<T>::lt_deBruijn_to_idx[64];
942template <typename T>
943constexpr uint32_t bits_impl<T>::lt_hi[256];
944template <typename T>
945constexpr uint64_t bits_impl<T>::lo_set[65];
946template <typename T>
947constexpr uint64_t bits_impl<T>::lo_unset[65];
948template <typename T>
949constexpr uint64_t bits_impl<T>::ps_overflow[65];
950template <typename T>
951constexpr uint8_t bits_impl<T>::lt_sel[256 * 8];
952template <typename T>
953constexpr uint64_t bits_impl<T>::lt_fib[92];
954template <typename T>
955constexpr uint8_t bits_impl<T>::lt_lo[256];
956
958
959} // end namespace sdsl
960
961#endif
Namespace for the succinct data structure library.
A helper class for bitwise tricks on 64 bit words.
Definition: bits.hpp:46
static constexpr uint32_t sel(uint64_t x, uint32_t i)
Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.
Definition: bits.hpp:584
static constexpr uint64_t read_int(const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
Reads a value from a bit position in an array.
Definition: bits.hpp:770
static constexpr uint64_t lt_fib[92]
Array containing Fibonacci numbers less than .
Definition: bits.hpp:69
static constexpr void write_int(uint64_t *word, uint64_t x, const uint8_t offset=0, const uint8_t len=64)
Writes value x to an bit position in an array.
Definition: bits.hpp:717
static constexpr uint32_t sel11(uint64_t x, uint32_t i, uint32_t c=0)
Calculates the position of the i-th rightmost 11-bit-pattern which terminates a Fibonacci coded integ...
Definition: bits.hpp:711
static constexpr uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
Definition: bits.hpp:686
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651
static constexpr uint64_t lo_unset[65]
lo_unset[i] is a 64-bit word with the i least significant bits not set and the high bits set.
Definition: bits.hpp:210
static constexpr uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
Definition: bits.hpp:570
static constexpr uint64_t prev(const uint64_t *word, uint64_t idx)
Get the one bit with the greatest position in the interval .
Definition: bits.hpp:912
static constexpr void write_int_and_move(uint64_t *&word, uint64_t x, uint8_t &offset, const uint8_t len)
Writes value x to an bit position in an array and moves the bit-pointer.
Definition: bits.hpp:742
static constexpr uint64_t next(const uint64_t *word, uint64_t idx)
Get the first one bit in the interval .
Definition: bits.hpp:897
static constexpr uint64_t all_set
64bit mask with all bits set to 1.
Definition: bits.hpp:49
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:484
static constexpr uint64_t rev(uint64_t x)
reverses a given 64 bit word
Definition: bits.hpp:927
static constexpr uint8_t lt_sel[256 *8]
Lookup table for select on bytes.
Definition: bits.hpp:253
static constexpr uint64_t read_int_bounded(const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
Definition: bits.hpp:786
static constexpr uint32_t cnt11(uint64_t x, uint64_t &c)
Count the number of consecutive and distinct 11 in the 64bit integer x.
Definition: bits.hpp:541
static constexpr uint64_t map01(uint64_t x, uint64_t c=1)
Map all 01 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
Definition: bits.hpp:578
static constexpr uint64_t read_unary(const uint64_t *word, uint8_t offset=0)
Reads an unary decoded value from a bit position in an array.
Definition: bits.hpp:816
static constexpr uint32_t lt_deBruijn_to_idx[64]
This table maps a 6-bit subsequence S[idx...idx+5] of constant deBruijn64 to idx.
Definition: bits.hpp:62
static constexpr uint64_t deBruijn64
This constant represents a de Bruijn sequence B(k,n) for k=2 and n=6.
Definition: bits.hpp:57
static constexpr uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
Definition: bits.hpp:556
static constexpr uint32_t lt_hi[256]
Lookup table for most significant set bit in a byte.
Definition: bits.hpp:174
static constexpr uint64_t read_unary_and_move(const uint64_t *&word, uint8_t &offset)
Reads an unary decoded value from a bit position in an array and moves the bit-pointer.
Definition: bits.hpp:842
static constexpr uint8_t lt_lo[256]
Lookup table for least significant set bit in a byte.
Definition: bits.hpp:231
static constexpr uint32_t cnt32(uint32_t x)
Counts the number of 1-bits in the 32bit integer x.
Definition: bits.hpp:503
static constexpr void move_left(const uint64_t *&word, uint8_t &offset, const uint8_t len)
Move the bit-pointer (=uint64_t word and offset) len to the left.
Definition: bits.hpp:887
static constexpr uint64_t read_unary_bounded(const uint64_t *word, uint8_t offset=0)
Definition: bits.hpp:831
static constexpr uint64_t ps_overflow[65]
Use to help to decide if a prefix sum stored in a byte overflows.
Definition: bits.hpp:320
static constexpr uint64_t read_int_and_move(const uint64_t *&word, uint8_t &offset, const uint8_t len=64)
Reads a value from a bit position in an array and moved the bit-pointer.
Definition: bits.hpp:792
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition: bits.hpp:187
static constexpr uint32_t hi11(uint64_t x)
Calculates the position of the leftmost 11-bit-pattern which terminates a Fibonacci coded integer in ...
Definition: bits.hpp:705
static constexpr uint8_t lt_cnt[256]
Lookup table for byte popcounts.
Definition: bits.hpp:163
static constexpr void move_right(const uint64_t *&word, uint8_t &offset, const uint8_t len)
Move the bit-pointer (=uint64_t word and offset) len to the right.
Definition: bits.hpp:877
static constexpr uint32_t _sel(uint64_t x, uint32_t i)
Definition: bits.hpp:613
bits_impl()=delete
static constexpr uint64_t map10(uint64_t x, uint64_t c=0)
Map all 10 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
Definition: bits.hpp:564