bits.cpp

/* sdsl - succinct data structures library
    Copyright (C) 2008 Simon Gog

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see http://www.gnu.org/licenses/ .
*/
#include "sdsl/bits.hpp"

namespace sdsl
{

const uint8_t bits::lt_cnt[] = {
    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, 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, 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, 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, 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, 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, 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
};



const uint32_t bits::lt_deBruijn_to_idx[] = {
    0, 1, 2, 7, 3,13, 8,19,
    4,25,14,28, 9,34,20,40,
    5,17,26,38,15,46,29,48,
    10,31,35,54,21,50,41,57,
    63, 6,12,18,24,27,33,39,
    16,37,45,47,30,53,49,56,
    62,11,23,32,36,44,52,55,
    61,22,43,51,60,42,59,58
};

const uint32_t bits::lt_hi[] = {
    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, 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, 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, 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, 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, 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, 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
};

const uint64_t bits::lo_set[] = {
    0x0000000000000000ULL,
    0x0000000000000001ULL,
    0x0000000000000003ULL,
    0x0000000000000007ULL,
    0x000000000000000FULL,
    0x000000000000001FULL,
    0x000000000000003FULL,
    0x000000000000007FULL,
    0x00000000000000FFULL,
    0x00000000000001FFULL,
    0x00000000000003FFULL,
    0x00000000000007FFULL,
    0x0000000000000FFFULL,
    0x0000000000001FFFULL,
    0x0000000000003FFFULL,
    0x0000000000007FFFULL,
    0x000000000000FFFFULL,
    0x000000000001FFFFULL,
    0x000000000003FFFFULL,
    0x000000000007FFFFULL,
    0x00000000000FFFFFULL,
    0x00000000001FFFFFULL,
    0x00000000003FFFFFULL,
    0x00000000007FFFFFULL,
    0x0000000000FFFFFFULL,
    0x0000000001FFFFFFULL,
    0x0000000003FFFFFFULL,
    0x0000000007FFFFFFULL,
    0x000000000FFFFFFFULL,
    0x000000001FFFFFFFULL,
    0x000000003FFFFFFFULL,
    0x000000007FFFFFFFULL,
    0x00000000FFFFFFFFULL,
    0x00000001FFFFFFFFULL,
    0x00000003FFFFFFFFULL,
    0x00000007FFFFFFFFULL,
    0x0000000FFFFFFFFFULL,
    0x0000001FFFFFFFFFULL,
    0x0000003FFFFFFFFFULL,
    0x0000007FFFFFFFFFULL,
    0x000000FFFFFFFFFFULL,
    0x000001FFFFFFFFFFULL,
    0x000003FFFFFFFFFFULL,
    0x000007FFFFFFFFFFULL,
    0x00000FFFFFFFFFFFULL,
    0x00001FFFFFFFFFFFULL,
    0x00003FFFFFFFFFFFULL,
    0x00007FFFFFFFFFFFULL,
    0x0000FFFFFFFFFFFFULL,
    0x0001FFFFFFFFFFFFULL,
    0x0003FFFFFFFFFFFFULL,
    0x0007FFFFFFFFFFFFULL,
    0x000FFFFFFFFFFFFFULL,
    0x001FFFFFFFFFFFFFULL,
    0x003FFFFFFFFFFFFFULL,
    0x007FFFFFFFFFFFFFULL,
    0x00FFFFFFFFFFFFFFULL,
    0x01FFFFFFFFFFFFFFULL,
    0x03FFFFFFFFFFFFFFULL,
    0x07FFFFFFFFFFFFFFULL,
    0x0FFFFFFFFFFFFFFFULL,
    0x1FFFFFFFFFFFFFFFULL,
    0x3FFFFFFFFFFFFFFFULL,
    0x7FFFFFFFFFFFFFFFULL,
    0xFFFFFFFFFFFFFFFFULL
};

const uint64_t bits::lo_unset[] = {
    0xFFFFFFFFFFFFFFFFULL,
    0xFFFFFFFFFFFFFFFEULL,
    0xFFFFFFFFFFFFFFFCULL,
    0xFFFFFFFFFFFFFFF8ULL,
    0xFFFFFFFFFFFFFFF0ULL,
    0xFFFFFFFFFFFFFFE0ULL,
    0xFFFFFFFFFFFFFFC0ULL,
    0xFFFFFFFFFFFFFF80ULL,
    0xFFFFFFFFFFFFFF00ULL,
    0xFFFFFFFFFFFFFE00ULL,
    0xFFFFFFFFFFFFFC00ULL,
    0xFFFFFFFFFFFFF800ULL,
    0xFFFFFFFFFFFFF000ULL,
    0xFFFFFFFFFFFFE000ULL,
    0xFFFFFFFFFFFFC000ULL,
    0xFFFFFFFFFFFF8000ULL,
    0xFFFFFFFFFFFF0000ULL,
    0xFFFFFFFFFFFE0000ULL,
    0xFFFFFFFFFFFC0000ULL,
    0xFFFFFFFFFFF80000ULL,
    0xFFFFFFFFFFF00000ULL,
    0xFFFFFFFFFFE00000ULL,
    0xFFFFFFFFFFC00000ULL,
    0xFFFFFFFFFF800000ULL,
    0xFFFFFFFFFF000000ULL,
    0xFFFFFFFFFE000000ULL,
    0xFFFFFFFFFC000000ULL,
    0xFFFFFFFFF8000000ULL,
    0xFFFFFFFFF0000000ULL,
    0xFFFFFFFFE0000000ULL,
    0xFFFFFFFFC0000000ULL,
    0xFFFFFFFF80000000ULL,
    0xFFFFFFFF00000000ULL,
    0xFFFFFFFE00000000ULL,
    0xFFFFFFFC00000000ULL,
    0xFFFFFFF800000000ULL,
    0xFFFFFFF000000000ULL,
    0xFFFFFFE000000000ULL,
    0xFFFFFFC000000000ULL,
    0xFFFFFF8000000000ULL,
    0xFFFFFF0000000000ULL,
    0xFFFFFE0000000000ULL,
    0xFFFFFC0000000000ULL,
    0xFFFFF80000000000ULL,
    0xFFFFF00000000000ULL,
    0xFFFFE00000000000ULL,
    0xFFFFC00000000000ULL,
    0xFFFF800000000000ULL,
    0xFFFF000000000000ULL,
    0xFFFE000000000000ULL,
    0xFFFC000000000000ULL,
    0xFFF8000000000000ULL,
    0xFFF0000000000000ULL,
    0xFFE0000000000000ULL,
    0xFFC0000000000000ULL,
    0xFF80000000000000ULL,
    0xFF00000000000000ULL,
    0xFE00000000000000ULL,
    0xFC00000000000000ULL,
    0xF800000000000000ULL,
    0xF000000000000000ULL,
    0xE000000000000000ULL,
    0xC000000000000000ULL,
    0x8000000000000000ULL,
    0x0000000000000000ULL
};

const uint64_t bits::ps_overflow[] = {
    0x8080808080808080ULL,
    0x7f7f7f7f7f7f7f7fULL,
    0x7e7e7e7e7e7e7e7eULL,
    0x7d7d7d7d7d7d7d7dULL,
    0x7c7c7c7c7c7c7c7cULL,
    0x7b7b7b7b7b7b7b7bULL,
    0x7a7a7a7a7a7a7a7aULL,
    0x7979797979797979ULL,
    0x7878787878787878ULL,
    0x7777777777777777ULL,
    0x7676767676767676ULL,
    0x7575757575757575ULL,
    0x7474747474747474ULL,
    0x7373737373737373ULL,
    0x7272727272727272ULL,
    0x7171717171717171ULL,
    0x7070707070707070ULL,
    0x6f6f6f6f6f6f6f6fULL,
    0x6e6e6e6e6e6e6e6eULL,
    0x6d6d6d6d6d6d6d6dULL,
    0x6c6c6c6c6c6c6c6cULL,
    0x6b6b6b6b6b6b6b6bULL,
    0x6a6a6a6a6a6a6a6aULL,
    0x6969696969696969ULL,
    0x6868686868686868ULL,
    0x6767676767676767ULL,
    0x6666666666666666ULL,
    0x6565656565656565ULL,
    0x6464646464646464ULL,
    0x6363636363636363ULL,
    0x6262626262626262ULL,
    0x6161616161616161ULL,
    0x6060606060606060ULL,
    0x5f5f5f5f5f5f5f5fULL,
    0x5e5e5e5e5e5e5e5eULL,
    0x5d5d5d5d5d5d5d5dULL,
    0x5c5c5c5c5c5c5c5cULL,
    0x5b5b5b5b5b5b5b5bULL,
    0x5a5a5a5a5a5a5a5aULL,
    0x5959595959595959ULL,
    0x5858585858585858ULL,
    0x5757575757575757ULL,
    0x5656565656565656ULL,
    0x5555555555555555ULL,
    0x5454545454545454ULL,
    0x5353535353535353ULL,
    0x5252525252525252ULL,
    0x5151515151515151ULL,
    0x5050505050505050ULL,
    0x4f4f4f4f4f4f4f4fULL,
    0x4e4e4e4e4e4e4e4eULL,
    0x4d4d4d4d4d4d4d4dULL,
    0x4c4c4c4c4c4c4c4cULL,
    0x4b4b4b4b4b4b4b4bULL,
    0x4a4a4a4a4a4a4a4aULL,
    0x4949494949494949ULL,
    0x4848484848484848ULL,
    0x4747474747474747ULL,
    0x4646464646464646ULL,
    0x4545454545454545ULL,
    0x4444444444444444ULL,
    0x4343434343434343ULL,
    0x4242424242424242ULL,
    0x4141414141414141ULL,
    0x4040404040404040ULL
};

const uint8_t bits::lt_sel[] = {
    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,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,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,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,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,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,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,

    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,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,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,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,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,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,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,

    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,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,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,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,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,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,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,

    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,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,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,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,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,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,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,

    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,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,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,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,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,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,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,

    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,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,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,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,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,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,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,

    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,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,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,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,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,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,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,

    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,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,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,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,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,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,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
};

const uint64_t bits::lt_fib[] = {
    1,
    2,
    3,
    5,
    8,
    13,
    21,
    34,
    55,
    89,
    144,
    233,
    377,
    610,
    987,
    1597,
    2584,
    4181,
    6765,
    10946,
    17711,
    28657,
    46368,
    75025,
    121393,
    196418,
    317811,
    514229,
    832040,
    1346269,
    2178309,
    3524578,
    5702887,
    9227465,
    14930352,
    24157817,
    39088169,
    63245986,
    102334155,
    165580141,
    267914296,
    433494437,
    701408733,
    1134903170,
    1836311903,
    2971215073ULL,
    0x11e8d0a40ULL,
    0x1cfa62f21ULL,
    0x2ee333961ULL,
    0x4bdd96882ULL,
    0x7ac0ca1e3ULL,
    0xc69e60a65ULL,
    0x1415f2ac48ULL,
    0x207fd8b6adULL,
    0x3495cb62f5ULL,
    0x5515a419a2ULL,
    0x89ab6f7c97ULL,
    0xdec1139639ULL,
    0x1686c8312d0ULL,
    0x2472d96a909ULL,
    0x3af9a19bbd9ULL,
    0x5f6c7b064e2ULL,
    0x9a661ca20bbULL,
    0xf9d297a859dULL,
    0x19438b44a658ULL,
    0x28e0b4bf2bf5ULL,
    0x42244003d24dULL,
    0x6b04f4c2fe42ULL,
    0xad2934c6d08fULL,
    0x1182e2989ced1ULL,
    0x1c5575e509f60ULL,
    0x2dd8587da6e31ULL,
    0x4a2dce62b0d91ULL,
    0x780626e057bc2ULL,
    0xc233f54308953ULL,
    0x13a3a1c2360515ULL,
    0x1fc6e116668e68ULL,
    0x336a82d89c937dULL,
    0x533163ef0321e5ULL,
    0x869be6c79fb562ULL,
    0xd9cd4ab6a2d747ULL,
    0x16069317e428ca9ULL,
    0x23a367c34e563f0ULL,
    0x39a9fadb327f099ULL,
    0x5d4d629e80d5489ULL,
    0x96f75d79b354522ULL,
    0xf444c01834299abULL,
    0x18b3c1d91e77decdULL,
    0x27f80ddaa1ba7878ULL,
    0x40abcfb3c0325745ULL,
    0x68a3dd8e61eccfbdULL,
    0xa94fad42221f2702ULL
};

const uint8_t bits::lt_lo[]= {
    0x00,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x04,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x05,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x04,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x06,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x04,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x05,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x04,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x07,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x04,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x05,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x04,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x06,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x04,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x05,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x04,0x00,0x01,0x00,0x02,0x00,0x01,0x00,
    0x03,0x00,0x01,0x00,0x02,0x00,0x01,0x00
};

} // end namespace sdsl