SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
util.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_UTIL
9#define INCLUDED_SDSL_UTIL
10
11#include <algorithm>
12#include <atomic>
13#include <cassert>
14#include <chrono>
15#include <cstdlib>
16#include <ctime> // for rand initialization
17#include <functional> // for class_to_hash
18#include <iomanip>
19#include <iosfwd> // forward declaration of ostream
20#include <mutex>
21#include <numeric>
22#include <random>
23#include <sstream> // for to_string method
24#include <stdexcept> // for std::logic_error
25#include <stdint.h> // for uint64_t uint32_t declaration
26#include <string.h> // for strlen and strdup
27#include <string>
28#include <type_traits>
29#include <typeinfo> // for typeid
30#include <typeinfo>
31#include <vector>
32
33#include <sdsl/bits.hpp>
34#include <sdsl/config.hpp> // for constants
35#include <sdsl/ram_fs.hpp>
36#include <sdsl/sfstream.hpp>
37
38#include <sys/stat.h> // for file_size
39#include <sys/types.h> // for file_size
40
41// macros to transform a defined name to a string
42#define SDSL_STR(x) #x
43#define SDSL_XSTR(s) SDSL_STR(s)
44
45#ifndef MSVC_COMPILER
46#include <cxxabi.h>
47#endif
48
49#ifndef _WIN32
50#include <libgen.h> // for basename
51#include <unistd.h> // for getpid, file_size, clock_gettime
52
53#include <sys/resource.h> // for struct rusage
54#include <sys/time.h> // for struct timeval
55#else
56#include <iso646.h>
57#include <process.h>
58#endif
59
61namespace sdsl
62{
63
64template <uint8_t>
65class int_vector; // forward declaration
66
68namespace util
69{
70
71//============= Debug information =========================
72
73SDSL_UNUSED static bool verbose = false;
74
75inline void set_verbose()
76{
77 verbose = true;
78}
79
80//============ Manipulating int_vectors ===================
81
83
88template <class t_int_vec>
89void set_random_bits(t_int_vec & v, int seed = 0);
91template <class t_int_vec>
92void _set_zero_bits(t_int_vec & v);
94template <class t_int_vec>
95void _set_one_bits(t_int_vec & v);
96
98
102template <class t_int_vec>
103void bit_compress(t_int_vec & v);
104
106template <class t_int_vec>
107void expand_width(t_int_vec & v, uint8_t new_width);
108
110template <class t_int_vec>
111void mod(t_int_vec & v, typename t_int_vec::size_type m);
112
113inline void cyclic_shifts(uint64_t * vec, uint8_t & n, uint64_t k, uint8_t int_width);
114
116
122template <class t_int_vec>
123void set_to_value(t_int_vec & v, uint64_t k);
124
126
133template <class t_int_vec, class t_int_vec_iterator>
134void set_to_value(t_int_vec & v, uint64_t k, t_int_vec_iterator it);
135
137template <class t_int_vec>
138void set_to_id(t_int_vec & v);
139
141
144template <class t_int_vec>
145typename t_int_vec::size_type cnt_one_bits(const t_int_vec & v);
146
148
150template <class t_int_vec>
151typename t_int_vec::size_type cnt_onezero_bits(const t_int_vec & v);
152
154
156template <class t_int_vec>
157typename t_int_vec::size_type cnt_zeroone_bits(const t_int_vec & v);
158
160
165template <class t_int_vec>
166typename t_int_vec::size_type next_bit(const t_int_vec & v, uint64_t idx);
167
169
174template <class t_int_vec>
175typename t_int_vec::size_type prev_bit(const t_int_vec & v, uint64_t idx);
176
177//============= Handling files =============================
178
180
183inline size_t file_size(const std::string & file)
184{
185 if (is_ram_file(file)) { return ram_fs::file_size(file); }
186 else
187 {
188 struct stat fs;
189 stat(file.c_str(), &fs);
190 return fs.st_size;
191 }
192}
193
195
198inline std::string basename(std::string file)
199{
200 file = disk_file_name(file); // remove RAM-prefix
201#ifdef _WIN32
202 char * c = _strdup((const char *)file.c_str());
203 char file_name[_MAX_FNAME] = { 0 };
204#ifdef MSVC_COMPILER
205 ::_splitpath_s(c, NULL, 0, NULL, NULL, file_name, _MAX_FNAME, NULL, 0);
206#else
207 ::_splitpath(c, NULL, NULL, file_name, NULL);
208#endif
209 std::string res(file_name);
210#else
211 char * c = strdup((const char *)file.c_str());
212 std::string res = std::string(::basename(c));
213#endif
214 free(c);
215 return res;
216}
217
219
222inline std::string dirname(std::string file)
223{
224 bool ram_file = is_ram_file(file);
225 file = disk_file_name(file); // remove RAM-prefix
226#ifdef _WIN32
227 char * c = _strdup((const char *)file.c_str());
228 char dir_name[_MAX_DIR] = { 0 };
229 char drive[_MAX_DRIVE] = { 0 };
230#ifdef MSVC_COMPILER
231 ::_splitpath_s(c, drive, _MAX_DRIVE, dir_name, _MAX_DIR, NULL, 0, NULL, 0);
232#else
233 ::_splitpath(c, drive, dir_name, NULL, NULL);
234#endif
235 std::string res = std::string(drive) + std::string(dir_name);
236#else
237 char * c = strdup((const char *)file.c_str());
238 std::string res = std::string(::dirname(c));
239 auto it = res.begin();
240 auto next_it = res.begin() + 1;
241 while (it != res.end() and next_it != res.end())
242 {
243 if (*next_it != '/' or *it != '/') { *(++it) = *next_it; }
244 ++next_it;
245 }
246 res.resize(it - res.begin() + 1);
247#endif
248 free(c);
249 if (ram_file)
250 {
251 if ("." == res) { res = ram_file_name(""); }
252 else if ("/" == res)
253 {
254 res = ram_file_name(res);
255 }
256 }
257 return res;
258}
259
261
264inline std::string demangle(const std::string & name)
265{
266#ifndef _WIN32
267 char buf[4096];
268 size_t size = 4096;
269 int status = 0;
270 abi::__cxa_demangle(name.c_str(), buf, &size, &status);
271 if (status == 0) return std::string(buf);
272 return name;
273#else
274 return name;
275#endif
276}
277
279inline std::string demangle2(const std::string & name)
280{
281 std::string result = demangle(name);
282 std::vector<std::string> words_to_delete;
283 words_to_delete.push_back("sdsl::");
284 words_to_delete.push_back("(unsigned char)");
285 words_to_delete.push_back(", unsigned long");
286
287 for (size_t k = 0; k < words_to_delete.size(); ++k)
288 {
289 std::string w = words_to_delete[k];
290 for (size_t i = result.find(w); i != std::string::npos; i = result.find(w, i))
291 {
292 result.erase(i, w.length());
293 ++i;
294 }
295 }
296 size_t index = 0;
297 std::string to_replace = "int_vector<1>";
298 while ((index = result.find(to_replace, index)) != std::string::npos)
299 {
300 result.replace(index, to_replace.size(), "bit_vector");
301 }
302 return result;
303}
304
306template <typename T>
307std::string to_string(const T & t, int w);
308
310template <class T>
311uint64_t hashvalue_of_classname(const T &)
312{
313 std::hash<std::string> str_hash;
314 return str_hash(sdsl::util::demangle2(typeid(T).name()));
315}
316
318template <class T>
319std::string class_to_hash(const T & t)
320{
321 return to_string(hashvalue_of_classname(t));
322}
323
324template <class T>
325std::string class_name(const T & t)
326{
327 std::string result = demangle2(typeid(t).name());
328 size_t template_pos = result.find("<");
329 if (template_pos != std::string::npos) { result = result.erase(template_pos); }
330 return result;
331}
332
333// convert an errno number to a readable msg
334inline char * str_from_errno()
335{
336#ifdef MSVC_COMPILER
337#pragma warning(disable : 4996)
338 return strerror(errno);
339#pragma warning(default : 4996)
340#else
341 return strerror(errno);
342#endif
343}
344
345struct _id_helper_struct
346{
347 uint64_t id = 0;
348};
349
350extern inline uint64_t _id_helper()
351{
352 static _id_helper_struct data;
353 return data.id++;
354}
355
357inline uint64_t pid()
358{
359#ifdef MSVC_COMPILER
360 return _getpid();
361#else
362 return getpid();
363#endif
364}
365
367inline uint64_t id()
368{
369 return _id_helper();
370}
371
372template <typename T>
373std::string to_latex_string(const T & t);
374
375inline std::string to_latex_string(unsigned char c)
376{
377 if (c == '_')
378 return "\\_";
379 else if (c == '\0')
380 return "\\$";
381 else
382 return to_string(c);
383}
384
386inline void delete_all_files(tMSS & file_map)
387{
388 for (auto file_pair : file_map) { sdsl::remove(file_pair.second); }
389 file_map.clear();
390}
391
393
396template <class T>
397void clear(T & x)
398{
399 T y;
400 x = std::move(y);
401}
402
404
412template <class S, class P>
413void swap_support(S & s1, S & s2, const P * p1, const P * p2)
414{
415 std::swap(s1, s2);
416 s1.set_vector(p1);
417 s2.set_vector(p2);
418}
419
421
424template <class S, class X>
425void init_support(S & s, const X * x)
426{
427 S temp(x); // generate a temporary support object
428 s = std::move(temp); // swap its content with the target object
429 s.set_vector(x); // set the support object's pointer to x
430}
431
433/*
434 */
435template <class t_int_vec>
436t_int_vec rnd_positions(uint8_t log_s, uint64_t & mask, uint64_t mod = 0, uint64_t seed = 17)
437{
438 mask = (1 << log_s) - 1;
439 t_int_vec rands(1 << log_s, 0);
440 set_random_bits(rands, seed);
441 if (mod > 0) { util::mod(rands, mod); }
442 return rands;
443}
444
446/* static_assert(is_regular<YOUR_TYPE>::value);
447 * Code is from a talk of Aerix Consulting
448 */
449template <typename T>
450struct is_regular
451 : std::integral_constant<bool,
452 std::is_default_constructible<T>::value && std::is_copy_constructible<T>::value &&
453 std::is_move_constructible<T>::value &&
454 std::is_copy_assignable<T>::value &&
455 std::is_move_assignable<T>::value>
456{};
457
458} // end namespace util
459
460//==================== Template functions ====================
461
462template <class t_int_vec>
463void util::set_random_bits(t_int_vec & v, int seed)
464{
465 std::mt19937_64 rng;
466 if (0 == seed) { rng.seed(std::chrono::system_clock::now().time_since_epoch().count() + util::id()); }
467 else
468 rng.seed(seed);
469
470 uint64_t * data = v.data();
471 if (v.empty()) return;
472 *data = rng();
473 for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i) { *(++data) = rng(); }
474}
475
476// all elements of vector v modulo m
477template <class t_int_vec>
478void util::mod(t_int_vec & v, typename t_int_vec::size_type m)
479{
480 for (typename t_int_vec::size_type i = 0; i < v.size(); ++i) { v[i] = v[i] % m; }
481}
482
483template <class t_int_vec>
484void util::bit_compress(t_int_vec & v)
485{
486 auto max_elem = std::max_element(v.begin(), v.end());
487 uint64_t max = 0;
488 if (max_elem != v.end()) { max = *max_elem; }
489 uint8_t min_width = bits::hi(max) + 1;
490 uint8_t old_width = v.width();
491 if (old_width > min_width)
492 {
493 const uint64_t * read_data = v.data();
494 uint64_t * write_data = v.data();
495 uint8_t read_offset = 0;
496 uint8_t write_offset = 0;
497 for (typename t_int_vec::size_type i = 0; i < v.size(); ++i)
498 {
499 uint64_t x = bits::read_int_and_move(read_data, read_offset, old_width);
500 bits::write_int_and_move(write_data, x, write_offset, min_width);
501 }
502 v.bit_resize(v.size() * min_width);
503 v.width(min_width);
504 // v.shrink_to_fit(); TODO(cpockrandt): comment in once int_vector_mapper has the same interface
505 }
506}
507
508template <class t_int_vec>
509void util::expand_width(t_int_vec & v, uint8_t new_width)
510{
511 uint8_t old_width = v.width();
512 typename t_int_vec::size_type n = v.size();
513 if (new_width > old_width)
514 {
515 if (n > 0)
516 {
517 typename t_int_vec::size_type i, old_pos, new_pos;
518 new_pos = (n - 1) * new_width;
519 old_pos = (n - 1) * old_width;
520 v.bit_resize(v.size() * new_width);
521 for (i = 0; i < n; ++i, new_pos -= new_width, old_pos -= old_width)
522 {
523 v.set_int(new_pos, v.get_int(old_pos, old_width), new_width);
524 }
525 }
526 v.width(new_width);
527 }
528}
529
530template <class t_int_vec>
531void util::_set_zero_bits(t_int_vec & v)
532{
533 std::for_each(v.data(), v.data() + ((v.bit_size() + 63) >> 6), [](uint64_t & value) { value = 0ULL; });
534}
535
536template <class t_int_vec>
537void util::_set_one_bits(t_int_vec & v)
538{
539 std::for_each(v.data(), v.data() + ((v.bit_size() + 63) >> 6), [](uint64_t & value) { value = -1ULL; });
540}
541
542inline void util::cyclic_shifts(uint64_t * vec, uint8_t & n, uint64_t k, uint8_t int_width)
543{
544 n = 0;
545 vec[0] = 0;
546 uint8_t offset = 0;
547 k &= 0xFFFFFFFFFFFFFFFFULL >> (64 - int_width);
548 do { // loop terminates after at most 64 iterations
549 vec[n] |= k << offset;
550 offset += int_width;
551 if (offset >= 64)
552 {
553 ++n;
554 if (int_width == 64) return;
555 assert(int_width - (offset - 64) < 64);
556 vec[n] = k >> (int_width - (offset - 64));
557 offset -= 64;
558 }
559 } while (offset != 0);
560}
561
562template <class t_int_vec>
563void util::set_to_value(t_int_vec & v, uint64_t k)
564{
565 uint64_t * data = v.data();
566 if (v.empty()) return;
567 uint8_t int_width = v.width();
568 if (int_width == 0) { throw std::logic_error("util::set_to_value can not be performed with int_width=0!"); }
569 if (0 == k)
570 {
572 return;
573 }
574 if (bits::lo_set[int_width] == k)
575 {
576 _set_one_bits(v);
577 return;
578 }
579 uint8_t n;
580 uint64_t vec[65];
581 util::cyclic_shifts(vec, n, k, int_width);
582
583 typename t_int_vec::size_type n64 = (v.bit_size() + 63) >> 6;
584 for (typename t_int_vec::size_type i = 0; i < n64;)
585 {
586 for (uint64_t ii = 0; ii < n and i < n64; ++ii, ++i) { *(data++) = vec[ii]; }
587 }
588}
589
590template <class t_int_vec, class t_int_vec_iterator>
591void util::set_to_value(t_int_vec & v, uint64_t k, t_int_vec_iterator it)
592{
593 typedef typename t_int_vec::size_type size_type;
594
595 if (v.empty()) return;
596 uint8_t int_width = v.width();
597 if (int_width == 0) { throw std::logic_error("util::set_to_value can not be performed with int_width=0!"); }
598 uint8_t n;
599 uint64_t vec[65];
600 util::cyclic_shifts(vec, n, k, int_width);
601
602 size_type words = (v.bit_size() + 63) >> 6;
603 size_type word_pos = ((it - v.begin()) * int_width) >> 6;
604 uint8_t pos_in_word = ((it - v.begin()) * int_width) - (word_pos << 6); // ((it - v.begin()) * int_width) % 64
605 uint8_t cyclic_shift = word_pos % n;
606
607 uint64_t * data = v.data() + word_pos;
608 *(data) &= bits::lo_set[pos_in_word]; // unset first bits
609 *(data) |= bits::lo_unset[pos_in_word] & vec[cyclic_shift++]; // set last bits
610 ++word_pos;
611
612 while (word_pos < words)
613 {
614 for (; cyclic_shift < n && word_pos < words; ++cyclic_shift, ++word_pos) { *(++data) = vec[cyclic_shift]; }
615 cyclic_shift = 0;
616 }
617}
618
620template <class t_int_vec>
621void util::set_to_id(t_int_vec & v)
622{
623 std::iota(v.begin(), v.end(), 0ULL);
624}
625
626template <class t_int_vec>
627typename t_int_vec::size_type util::cnt_one_bits(const t_int_vec & v)
628{
629 const uint64_t * data = v.data();
630 if (v.empty()) return 0;
631 typename t_int_vec::size_type result = bits::cnt(*data);
632 for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i) { result += bits::cnt(*(++data)); }
633 if (v.bit_size() & 0x3F) { result -= bits::cnt((*data) & (~bits::lo_set[v.bit_size() & 0x3F])); }
634 return result;
635}
636
637template <class t_int_vec>
638typename t_int_vec::size_type util::cnt_onezero_bits(const t_int_vec & v)
639{
640 const uint64_t * data = v.data();
641 if (v.empty()) return 0;
642 uint64_t carry = 0, oldcarry = 0;
643 typename t_int_vec::size_type result = bits::cnt10(*data, carry);
644 for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
645 {
646 oldcarry = carry;
647 result += bits::cnt10(*(++data), carry);
648 }
649 if (v.bit_size() & 0x3F)
650 { // if bit_size is not a multiple of 64, subtract the counts of the additional bits
651 result -= bits::cnt(bits::map10(*data, oldcarry) & bits::lo_unset[v.bit_size() & 0x3F]);
652 }
653 return result;
654}
655
656template <class t_int_vec>
657typename t_int_vec::size_type util::cnt_zeroone_bits(const t_int_vec & v)
658{
659 const uint64_t * data = v.data();
660 if (v.empty()) return 0;
661 uint64_t carry = 1, oldcarry = 1;
662 typename t_int_vec::size_type result = bits::cnt01(*data, carry);
663 for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
664 {
665 oldcarry = carry;
666 result += bits::cnt01(*(++data), carry);
667 }
668 if (v.bit_size() & 0x3F)
669 { // if bit_size is not a multiple of 64, subtract the counts of the additional bits
670 result -= bits::cnt(bits::map01(*data, oldcarry) & bits::lo_unset[v.bit_size() & 0x3F]);
671 }
672 return result;
673}
674
675template <class t_int_vec>
676typename t_int_vec::size_type util::next_bit(const t_int_vec & v, uint64_t idx)
677{
678 uint64_t pos = idx >> 6;
679 uint64_t node = v.data()[pos];
680 node >>= (idx & 0x3F);
681 if (node) { return idx + bits::lo(node); }
682 else
683 {
684 ++pos;
685 while ((pos << 6) < v.bit_size())
686 {
687 if (v.data()[pos]) { return (pos << 6) | bits::lo(v.data()[pos]); }
688 ++pos;
689 }
690 return v.bit_size();
691 }
692}
693
694template <class t_int_vec>
695typename t_int_vec::size_type util::prev_bit(const t_int_vec & v, uint64_t idx)
696{
697 uint64_t pos = idx >> 6;
698 uint64_t node = v.data()[pos];
699 node <<= 63 - (idx & 0x3F);
700 if (node) { return bits::hi(node) + (pos << 6) - (63 - (idx & 0x3F)); }
701 else
702 {
703 --pos;
704 while ((pos << 6) < v.bit_size())
705 {
706 if (v.data()[pos]) { return (pos << 6) | bits::hi(v.data()[pos]); }
707 --pos;
708 }
709 return v.bit_size();
710 }
711}
712
713template <typename T>
714std::string util::to_string(const T & t, int w)
715{
716 std::stringstream ss;
717 ss << std::setw(w) << t;
718 return ss.str();
719}
720
721template <typename T>
722std::string util::to_latex_string(const T & t)
723{
724 return to_string(t);
725}
726
727} // end namespace sdsl
728#endif
bits.hpp contains the sdsl::bits class.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
Definition: int_vector.hpp:595
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:566
#define SDSL_UNUSED
Definition: config.hpp:13
size_t file_size(const std::string &name)
Get the file size.
Definition: ram_fs.hpp:49
void set_to_id(t_int_vec &v)
Sets each entry of the numerical vector v at position $fi.
Get the size of a file in bytes size_t file_size(const std::string &file)
Definition: util.hpp:183
Returns the directory of a file A trailing will be removed std::string dirname(std::string file)
Definition: util.hpp:222
Returns the basename of a file std::string basename(std::string file)
Definition: util.hpp:198
Get the greatest position f$i leq idx f$ where a bit is set t_int_vec::size_type prev_bit(const t_int_vec &v, uint64_t idx)
uint64_t id()
void set_random_bits(t_int_vec &v, int seed=0)
Sets all bits of the int_vector to pseudo-random bits.
Definition: util.hpp:463
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_onezero_bits(const t_int_vec &v)
void mod(t_int_vec &v, typename t_int_vec::size_type m)
All elements of v modulo m.
Definition: util.hpp:478
void expand_width(t_int_vec &v, uint8_t new_width)
Expands the integer width to new_width >= v.width()
Definition: util.hpp:509
void cyclic_shifts(uint64_t *vec, uint8_t &n, uint64_t k, uint8_t int_width)
Definition: util.hpp:542
void set_verbose()
Definition: util.hpp:75
uint64_t pid()
void bit_compress(t_int_vec &v)
Bit compress the int_vector.
Definition: util.hpp:484
void _set_one_bits(t_int_vec &v)
Sets all bits of the int_vector to 1-bits.
Definition: util.hpp:537
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition: util.hpp:563
std::string to_string(const T &t, int w=1)
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_zeroone_bits(const t_int_vec &v)
Number of set bits in v t_int_vec::size_type cnt_one_bits(const t_int_vec &v)
void _set_zero_bits(t_int_vec &v)
Sets all bits of the int_vector to 0-bits.
Definition: util.hpp:531
Get the smallest position f$i geq idx f$ where a bit is set t_int_vec::size_type next_bit(const t_int_vec &v, uint64_t idx)
Namespace for the succinct data structure library.
bool is_ram_file(const std::string &file)
Determines if the given file is a RAM-file.
Definition: ram_fs.hpp:158
std::map< std::string, std::string > tMSS
Definition: config.hpp:50
uint64_t count(const t_k2_treap &treap, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
Count how many points are in the rectangle (p1,p2)
std::string ram_file_name(const std::string &file)
Returns the corresponding RAM-file name for file.
Definition: ram_fs.hpp:174
std::string disk_file_name(const std::string &file)
Returns for a RAM-file the corresponding disk file name.
Definition: ram_fs.hpp:184
int remove(const std::string &)
Remove a file.
Definition: ram_fs.hpp:194
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
ram_fs.hpp
sfstream.hpp contains a two stream class which can be used to read/write from/to files or strings.
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 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 cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:484
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 uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
Definition: bits.hpp:556
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 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