// -*- C++ -*- // automatically generated by autodoc // ========== HEADER FILE src/bits/average.h: ========== static inline ulong floor_average(ulong x, ulong y); // Return floor( (x+y)/2 ) // Result is correct even if (x+y) wouldn't fit into a ulong // Use: x+y == ((x&y)<<1) + (x^y) // that is: sum == carries + sum_without_carries static inline ulong ceil_average(ulong x, ulong y); // Return ceil( (x+y)/2 ) // Result is correct even if (x+y) wouldn't fit into a ulong // Use: x+y == ((x|y)<<1) - (x^y) // ceil_average(x,y) == average(x,y) + ((x^y)&1)) // ========== HEADER FILE src/bits/bin-to-sl-gray.h: ========== static inline ulong bin_to_sl_gray(ulong k, ulong ldn); // Unranking for binary SL-Gray: // Convert binary number to corresponding word in SL-Gray order. // Successive transitions are adjacent (one-close) or three-close. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 static inline ulong sl_gray_to_bin(ulong k, ulong ldn); // Ranking for binary SL-Gray: // Convert binary word in SL-Gray order to binary number. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/bits/bin2naf.h: ========== static inline void bin2naf(ulong x, ulong &np, ulong &nm); // Compute (nonadjacent form, NAF) signed binary representation of x: // the unique representation of x as // x=\sum_{k}{d_k*2^k} where d_j \in {-1,0,+1} // and no two adjacent digits d_j, d_{j+1} are both nonzero. // np has bits j set where d_j==+1 // nm has bits j set where d_j==-1 // We have: x = np - nm static inline ulong naf2bin(ulong np, ulong nm); // Inverse of bin2naf() // Works also for signed-binary pairs np, nm // that are not nonadjacent forms. static inline void bin2sbin(ulong x, ulong &np, ulong &nm); // Compute a signed binary representation of x: // a representation of x as // x=\sum_{k}{d_k*2^k} where d_j \in {-1,0,+1} // Inverse function is naf2bin(). // ========== HEADER FILE src/bits/bit-dragon-r13.h: ========== static inline bool bit_dragon_r13_turn(ulong &x); // Increment the radix-13 word x and // return (tr) whether the lowest nonzero digit // of the incremented word is either 3, 6, 8, 9, 11, or 12. // tr determines whether to turn left or right (by 90 degrees) // with the R13-dragon fractal. // // Starting with x==0: // x tr // ......... 0 // ........1 0 // .......1. 1 // .......11 0 // ......1.. 0 // ......1.1 1 // ......11. 0 // ......111 1 // .....1... 1 // .....1..1 0 // .....1.1. 1 // .....1.11 1 // .....11.. 0 // ....1.... 0 // ....1...1 0 // ....1..1. 1 // ....1..11 0 // ....1.1.. 0 // ....1.1.1 1 // ....1.11. 0 // ....1.111 1 // ....11... 1 // ....11..1 0 // ....11.1. 1 // ....11.11 1 // ....111.. 0 // ...1..... 0 // ...1....1 0 // ...1...1. 1 // // The sequence tr is the fixed point // of the morphism 0 |--> 0010010110110, 1 |--> 0010010110111. // // Also fixed point of morphism (identify + with 0 and - with 1) // F |--> F+F+F-F+F+F-F+F-F-F+F-F-F, + |--> +, - |--> - // ========== HEADER FILE src/bits/bit-dragon-r4.h: ========== static inline int bit_dragon_r4_turn(ulong &x); // Increment the radix-4 word x and // return (tr) as follows: // +1 if lowest nonzero digit of the incremented word is 1, // 0 if it is 2, otherwise -1 (when it is 3). // tr determines whether to turn left(-1), right(+1), or not at all(0) // (by 120 degrees) with the R4-dragon fractal. // // The sequence tr starts // +0-++0-0+0--+0-++0-++0-0+0--+0-0+0-++0-0+0--+0--+0-++0-0+0--+0- // // The sequence tr is the fixed point of morphism // + |--> +0-+, 0 |--> +0-0, - |--> +0-- // // Also fixed point of morphism // F |--> F+F0F-F, 0 |--> 0, - |--> -, + |--> + // (after omitting the symbols F) // // The OEIS sequence A035263 gives the absolute values, // see also A029883 (different signs). // ========== HEADER FILE src/bits/bit-dragon-r5.h: ========== static inline bool bit_dragon_r5_turn(ulong &x); // Increment the radix-5 word x and // return (tr) whether the lowest nonzero digit // of the incremented word is > 2. // tr determines whether to turn left or right (by 90 degrees) // with the R5-dragon fractal. // // Starting with x==0: // x tr // ......... 0 // ........1 0 // .......1. 1 // .......11 1 // ......1.. 0 // .....1... 0 // .....1..1 0 // .....1.1. 1 // .....1.11 1 // .....11.. 0 // ....1.... 0 // ....1...1 0 // ....1..1. 1 // ....1..11 1 // ....1.1.. 1 // ....11... 0 // // The sequence tr is the fixed point // of the morphism 0 |--> 00110, 1 |--> 00111. // Cf. OEIS sequence A175337. // // Also fixed point of morphism (identify + with 0 and - with 1) // F |--> F+F+F-F-F, + |--> +, - |--> - // ========== HEADER FILE src/bits/bit-dragon-r7.h: ========== static inline bool bit_dragon_r7_turn(ulong &x); // Increment the radix-7 word x and // return (tr) whether the lowest nonzero digit // of the incremented word is either 2, 3, or 6. // tr determines whether to turn left or right (by 120 degrees) // with the R7-dragon fractal. // // Starting with x==0: // x tr // ......... 0 // ........1 1 // .......1. 1 // .......11 0 // ......1.. 0 // ......1.1 1 // ......11. 0 // .....1... 0 // .....1..1 1 // .....1.1. 1 // .....1.11 0 // .....11.. 0 // .....11.1 1 // .....111. 1 // ....1.... 0 // ....1...1 1 // ....1..1. 1 // ....1..11 0 // ....1.1.. 0 // // The sequence tr is the fixed point // of the morphism 0 |--> 0100110, 1 |--> 0110110. // Cf. OEIS sequence A176405. // // Also fixed point of morphism (identify + with 0 and - with 1) // F |--> F+F-F-F+F+F-F, + |--> +, - |--> - static inline int bit_dragon_r7_2_turn(ulong &x); // Increment the radix-7 word x and // return (tr) according to the lowest nonzero digit d // of the incremented word: // d==[1,2,3,4,5,6] ==> rt:=[0,+1,+1,-1,-1,0] // (tr * 120deg) is the turn with the second R7-dragon. // // Starting with x==0: // x tr // ......... 0 // ........1 + // .......1. + // .......11 - // ......1.. - // ......1.1 0 // ......11. 0 // .....1... 0 // .....1..1 + // .....1.1. + // .....1.11 - // .....11.. - // .....11.1 0 // .....111. + // ....1.... 0 // ....1...1 + // ....1..1. + // ....1..11 - // ....1.1.. - // ....1.1.1 0 // ....1.11. + // ....11... 0 // ....11..1 + // // The sequence tr is the fixed point of the morphism // 0 |--> 0++--00, + |--> 0++--0+, - |--> 0++--0- // Cf. OEIS sequence A176416. // // Also fixed point of morphism // F |--> F0F+F+F-F-F0F, + |--> +, - |--> -, 0 |--> 0 // ========== HEADER FILE src/bits/bit-dragon-r9.h: ========== static inline bool bit_dragon_r9_turn(ulong &x); // Increment the radix-9 word x and // return (tr) whether the lowest nonzero digit // of the incremented word is either 2, 3, 5, or 8. // tr determines whether to turn left or right (by 120 degrees) // with the R9-dragon fractal. // // Starting with x==0: // x tr // ......... 0 // ........1 1 // .......1. 1 // .......11 0 // ......1.. 1 // ......1.1 0 // ......11. 0 // ......111 1 // .....1... 0 // ....1.... 0 // ....1...1 1 // ....1..1. 1 // ....1..11 0 // ....1.1.. 1 // ....1.1.1 0 // ....1.11. 0 // ....1.111 1 // ....11... 1 // ...1..... 0 // ...1....1 1 // ...1...1. 1 // ...1...11 0 // ...1..1.. 1 // ...1..1.1 0 // ...1..11. 0 // ...1..111 1 // ...1.1... 1 // ...11.... 0 // ...11...1 1 // ...11..1. 1 // // The sequence tr is the fixed point // of the morphism 0 |--> 011010010, 1 |--> 011010011. // Also fixed point of 0 |--> 011, 1 |--> 010, because // 0 |--> 011 |--> 011010010 // 1 |--> 010 |--> 011010011 // See OEIS sequence A156595. // // Also fixed point of morphism (identify + with 0 and - with 1) // F |--> F+F-F-F+F-F+F+F-F, + |--> +, - |--> - // // Also fixed point of morphism // F |--> G+G-G, G |--> F-F+F, + |--> +, - |--> - // ========== HEADER FILE src/bits/bit-dragon3.h: ========== static inline bool bit_dragon3_turn(ulong &x); // Increment the radix-3 word x and return (tr) // whether the number of ones in x is decreased. // tr determines whether to turn left or right (by 120 degrees) // with the terdragon fractal. // // Starting with x==0: // x (binary) tr x (ternary) // ........ 0 0 0 0 // .......1 0 0 0 1 // ......1. 1 0 0 2 // .....1.. 0 0 1 0 // .....1.1 0 0 1 1 // .....11. 1 0 1 2 // ....1... 1 0 2 0 // ....1..1 0 0 2 1 // ....1.1. 1 0 2 2 // ...1.... 0 1 0 0 // The sequence tr (for x>=1) is entry A080846 in the OEIS, // the fixed point of the morphism 0 |--> 010, 1 |--> 011. // See also A060236 (== 1,2,1,1,2,2,1,2,1,1,2,1,1,2,2,1,2,2,1,2, ...). // Also fixed point of morphism (for k>0, identify + with 0 and - with 1) // F |--> F+F-F, + |--> +, - |--> - // ========== HEADER FILE src/bits/bit-isolate.h: ========== // Extraction of ones, zeros, or blocks near transitions. // Here we assume that the outside bits are all zero. // Therefore we have // interior_values(v) != ( interior_ones(v) | interior_ones(~v) ) // Functions ignoring outside values have names ending in _xi static inline ulong single_ones(ulong x); // Return word with only the isolated ones of x set. // Assume outside values are 0. static inline ulong single_ones_xi(ulong x); // Return word with only the isolated ones of x set. // Ignore outside values. static inline ulong single_zeros(ulong x); // Return word with only the isolated zeros of x set. // Assume outside values are 0. static inline ulong single_zeros_xi(ulong x); // Return word with only the isolated zeros of x set. // Ignore outside values. static inline ulong single_values(ulong x); // Return word where only the isolated ones and zeros of x are set. // Assume outside values are 0. static inline ulong single_values_xi(ulong x); // Return word where only the isolated ones and zeros of x are set. // Ignore outside values. static inline ulong border_ones(ulong x); // Return word where only those ones of x are set that lie next to a zero. static inline ulong border_values(ulong x); // Return word where those bits of x are set that lie on a transition. // Assume outside values are 0. static inline ulong high_border_ones(ulong x); // Return word where only those ones of x are set // that lie right to (i.e. in the next lower bin of) a zero. static inline ulong low_border_ones(ulong x); // Return word where only those ones of x are set // that lie left to (i.e. in the next higher bin of) a zero. static inline ulong block_border_ones(ulong x); // Return word where only those ones of x are set // that are at the border of a block of at least 2 ones. static inline ulong low_block_border_ones(ulong x); // Return word where only those ones of x are set // that are at left of a border of a block of at least 2 ones. static inline ulong high_block_border_ones(ulong x); // Return word where only those ones of x are set // that are at right of a border of a block of at least 2 ones. static inline ulong block_ones(ulong x); // Return word where only those ones of x are set // that are part of a block of at least 2 ones. static inline ulong block_values(ulong x); // Return word where only those bits of x are set // that do not lie next to an opposite value. static inline ulong interior_ones(ulong x); // Return word where only those ones of x are set // that do not have a zero to their left or right. static inline ulong interior_values(ulong x); // Return word where only those values of x are set // that do have a transitions on both sides. // ========== HEADER FILE src/bits/bit-necklace.h: ========== class bit_necklace; // Binary necklaces as binary words. // The cyclic maximal words are produced. // Must have 0=1) is entry A014577 of the OEIS. // Also: for k>=1, the dragon curve turns left if seq(k)=1, else right. // Also fixed point of morphism (for k>0, identify + with 1 and - with 0) // L |--> L+R+L-R, R |--> L+R-L-R, + |--> +, - |--> - // Also fixed point of morphism (for k>0) // L |--> L+R, R |--> L-R, + |--> +, - |--> - static inline ulong bit_dragon_rot(ulong k); // Return total rotation (as multiple of the right angle) // after k steps in the dragon curve corresponding to // the paper-folding sequence. // k= 0, 1, 2, 3, 4, 5, ... // seq(k)= 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 2, ... // move = + ^ - ^ - v - ^ - v + v - v - ... // (+==right, -==left, ^==up, v==down). // Sequence is entry A005811 of the OEIS. // We take result modulo 4 to ignore multiples of 360 degree. // Algorithm: count the ones in gray_code(k). static inline bool bit_paper_fold_alt(ulong k); // Return element number k of the alternate paper-folding sequence: // k= 0, 1, 2, 3, 4, 5, ... // seq(k)= 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, ... // Sequence (for k>=1) is entry A106665 of the OEIS. // Also: the corresponding curve turns left if seq(k)=1, else right. // Also fixed point of morphism (for k>0, identify + with 1 and - with 0) // L |--> R+L+R-L, R |--> R+L-R-L, + |--> +, - |--> - static inline ulong bit_paper_fold_alt_rot(ulong k); // Return total rotation (as multiple of the right angle) // after k steps in the alternate paper-folding curve. // k= 0, 1, 2, 3, 4, 5, ... // seq(k)= 0, 1, 0, 3, 0, 1, 2, 1, 0, 1, 0, 3, 2, 3, 0, ... // move = + ^ + v + ^ - ^ + ^ + v - v + // (+==right, -==left, ^==up, v==down). // Algorithm: count the ones in (w ^ gray_code(k)). static inline bool bit_paper_fold_general(ulong k, ulong w); // Return element number k of the general paper-folding sequence: // bit number x of the words w determines whether // a left or right fold is made at the step x. // With w==0 the result is ! bit_paper_fold(k). // With w==~0 the result is bit_paper_fold(k). // The result with ~w is the complement of the result with w. static inline ulong bit_paper_fold_general_rot(ulong k, ulong w); // Return total rotation (as multiple of the right angle) // after k steps in the general paper-folding curve. // Algorithm: count the ones in (w ^ gray_code(k)). // With w==~0 the result is bit_dragon_rot(k). // ========== HEADER FILE src/bits/bit-rll2.h: ========== class bit_rll2; // Run length limited (RLL) words and Fibonacci words. // The RLL words are in lexicographic order, // the Fibonacci words are in a minimal change order (Gray code). // ========== HEADER FILE src/bits/bit-sl-gray.h: ========== class bit_sl_gray; // Binary words in a minimal-change order // related so subset-lex order ("SL-Gray" order). // Successive transitions are mostly adjacent (one-close), // and otherwise have distance 3 (three-close). // Loopless algorithm. // ========== HEADER FILE src/bits/bit2adic.h: ========== static inline ulong inv2adic(ulong x); // Return inverse modulo 2**BITS_PER_LONG // x must be odd // The number of correct bits is doubled with each step // ==> loop is executed prop. log_2(BITS_PER_LONG) times // precision is 3, 6, 12, 24, 48, 96, ... bits (or better) static inline ulong invsqrt2adic(ulong d); // Return inverse square root modulo 2**BITS_PER_LONG // Must have: d==1 mod 8 // The number of correct bits is doubled with each step // ==> loop is executed prop. log_2(BITS_PER_LONG) times // precision is 4, 8, 16, 32, 64, ... bits (or better) static inline ulong sqrt2adic(ulong d); // Return square root modulo 2**BITS_PER_LONG // Must have: d==1 mod 8 or d==4 mod 32, d==16 mod 128 // ... d==4**k mod 4**(k+3) // Result undefined if condition does not hold // ========== HEADER FILE src/bits/bit2pow.h: ========== static inline ulong ld(ulong x); // Return floor(log2(x)), // i.e. return k so that 2^k <= x < 2^(k+1) // If x==0, then 0 is returned (!) static inline bool is_pow_of_2(ulong x); // Return whether x == 0(!) or x == 2**k static inline bool one_bit_q(ulong x); // Return whether x \in {1,2,4,8,16,...} static inline ulong next_pow_of_2(ulong x); // Return x if x=2**k // else return 2**ceil(log_2(x)) // Exception: returns 0 for x==0 static inline ulong next_exp_of_2(ulong x); // Return k if x=2**k else return k+1. // Exception: returns 0 for x==0. // ========== HEADER FILE src/bits/bitasm-amd64.h: ========== static inline ulong asm_bit_count(ulong x); static inline ulong asm_bsf(ulong x); // Bit Scan Forward static inline ulong asm_bsr(ulong x); // Bit Scan Reverse static inline ulong asm_bswap(ulong x); // Byte swap static inline ulong asm_rol(ulong x, ulong r); // Rotate Left static inline ulong asm_ror(ulong x, ulong r); // Rotate Right static inline ulong asm_parity(ulong x); // Return the parity of x (which is the // _complement_ of AMD64's parity flag). // As parity is for the low byte only, // therefore we need to prepend // x ^= (x>>32); x ^= (x>>16); x ^= (x>>8); // in the code static inline ulong asm_bt(const ulong *f, ulong i); // Bit Test static inline ulong asm_bts(ulong *f, ulong i); // Bit Test and Set static inline void asm_b_s(ulong *f, ulong i); // Bit Set static inline ulong asm_btr(ulong *f, ulong i); // Bit Test and Reset static inline void asm_b_r(ulong *f, ulong i); // Bit Reset static inline ulong asm_btc(ulong *f, ulong i); // Bit Test and Complement static inline void asm_b_c(ulong *f, ulong i); // Bit Complement // ========== HEADER FILE src/bits/bitasm-i386.h: ========== static inline ulong asm_bsf(ulong x); // Bit Scan Forward: return index of lowest one. static inline ulong asm_bsr(ulong x); // Bit Scan Reverse: return index of highest one. static inline ulong asm_bswap(ulong x); // Byte swap static inline ulong asm_rol(ulong x, ulong r); // Rotate Left static inline ulong asm_ror(ulong x, ulong r); // Rotate Right static inline ulong asm_parity(ulong x); // Return the parity of x (which is the // _complement_ of x86's parity flag). // As parity is for the low byte only, // therefore we need to prepend // x ^= (x>>16); x ^= (x>>8); // in the code static inline ulong asm_bt(const ulong *f, ulong i); // Bit Test static inline ulong asm_bts(ulong *f, ulong i); // Bit Test and Set static inline void asm_b_s(ulong *f, ulong i); // Bit Set static inline ulong asm_btr(ulong *f, ulong i); // Bit Test and Reset static inline void asm_b_r(ulong *f, ulong i); // Bit Reset static inline ulong asm_btc(ulong *f, ulong i); // Bit Test and Complement static inline void asm_b_c(ulong *f, ulong i); // Bit Complement // ========== HEADER FILE src/bits/bitasm-sse.h: ========== static inline ulong sse_byte_zip(ulong x); // Return word with lower half bytes in even indices // and upper half bits in odd indices. //. // Slower than the butterfly_8/16() based version! // This is apparently not what SSE was made for. // ========== HEADER FILE src/bits/bitasm.h: ========== // ========== HEADER FILE src/bits/bitblock.h: ========== static inline ulong bit_block(ulong p, ulong n); // Return word with length-n bit block starting at bit p set. // Both p and n are effectively taken modulo BITS_PER_LONG. static inline ulong cyclic_bit_block(ulong p, ulong n); // Return word with length-n bit block starting at bit p set. // The result is possibly wrapped around the word boundary. // Both p and n are effectively taken modulo BITS_PER_LONG. // ========== HEADER FILE src/bits/bitbutterfly.h: ========== // The butterfly_*() functions are used in bit_zip() and bit_unzip() static inline ulong butterfly_16(ulong x); // Swap the two central blocks of 16 bits. static inline ulong butterfly_8(ulong x); // Swap in each block of 32 bits the two central blocks of 8 bits. static inline ulong butterfly_4(ulong x); // Swap in each block of 16 bits the two central blocks of 4 bits. static inline ulong butterfly_2(ulong x); // Swap in each block of 8 bits the two central blocks of 2 bits. static inline ulong butterfly_1(ulong x); // Swap in each block of 4 bits the two central bits. // ========== HEADER FILE src/bits/bitcombcolex.h: ========== static inline ulong first_comb(ulong k); // Return the first combination of (i.e. smallest word with) k bits, // i.e. 00..001111..1 (k low bits set) // Must have: 0 <= k <= BITS_PER_LONG static inline ulong last_comb(ulong k, ulong n=BITS_PER_LONG); // Return the last combination of (biggest n-bit word with) k bits // i.e. 1111..100..00 (k high bits set) // Must have: 0 <= k <= n <= BITS_PER_LONG static inline ulong next_colex_comb(ulong x); // Return smallest integer greater than x with the same number of bits set. // // colex order (5 over 3): // set word set reversed (sorted!) // 0 1 2 ..111 2 1 0 // 0 1 3 .1.11 3 1 0 // 0 2 3 .11.1 3 2 0 // 1 2 3 .111. 3 2 1 // 0 1 4 1..11 4 1 0 // 0 2 4 1.1.1 4 2 0 // 1 2 4 1.11. 4 2 1 // 0 3 4 11..1 4 3 0 // 1 3 4 11.1. 4 3 1 // 2 3 4 111.. 4 3 2 // // Examples: // 000001 -> 000010 -> 000100 -> 001000 -> 010000 -> 100000 // 000011 -> 000101 -> 000110 -> 001001 -> 001010 -> 001100 -> 010001 -> ... // 000111 -> 001011 -> 001101 -> 001110 -> 010011 -> 010101 -> 010110 -> ... // // Special cases: // 0 -> 0 // all bits on the high side (i.e. last combination) -> 0 //. // based on code by Doug Moore / Glenn Rhoads // note: might want to use bitscan near end static inline ulong next_colex_comb(ulong x); // Return smallest integer greater than x with the same number of bits set. // // Example: (the bits marked by '.' remain fixed) // x = ....01111100000000 // z = 000000000100000000 (the lowest set bit) // v=x+z = ....10000000000000 (first zero beyond burst of ones) // v^x = 000011111100000000 // v^x/z = 000000000000111111 // v^x/z>>2 = 000000000000001111 // next = ....10000000001111 //. // Code based on code taken from Torsten Sillke's bitmani.h: // http://www.mathematik.uni-bielefeld.de/~sillke/ALGORITHMS/ // The algorithm can be found in hakmem, shortcut by me. static inline ulong prev_colex_comb(ulong x); // Inverse of next_colex_comb() // ========== HEADER FILE src/bits/bitcombminchange.h: ========== static inline ulong igc_next_minchange_comb(ulong x); // Return the inverse Gray code of the next combination in minimal-change order. // Input must be the inverse Gray code of the current combination. //. // Original code by by Doug Moore. // Only cosmetical changes by me. static inline ulong igc_next_minchange_comb(ulong x); // Alternative version, faster. // Constant amortized time (CAT). static inline ulong igc_next_minchange_comb(ulong x, ulong k); // Alternative version, uses the fact that the difference // of two successive x is the smallest possible power of 2. // Should be fast if the CPU has a bitcount instruction. // k must be the bit-count of x // Constant amortized time (CAT). // Note: this version has 2 arguments. static inline ulong igc_prev_minchange_comb(ulong x, ulong k); // Return the inverse Gray code of the previous combination in minimal-change order. // Input must be the inverse Gray code of the current combination. // Constant amortized time (CAT). // With input==first the output is the last for n=BITS_PER_LONG static inline ulong igc_last_comb(ulong k, ulong n); // Return the (inverse Gray code of the) last combination // as in igc_next_minchange_comb(). // // Example (n=6) c:=first_comb(n) == 111111 // // k: f=first_seq(k) c^(f>>1) == return // 0: ...... 111111 (!) special case: return 0==...... // 1: .....1 111111 // 2: ....1. 11111. // 3: ...1.1 1111.1 // 4: ..1.1. 111.1. // 5: .1.1.1 11.1.1 // 6: 1.1.1. 1.1.1. static inline ulong next_minchange_comb(ulong x, ulong last); // Not efficient, just to explain the usage of igc_next_minchange_comb() // Must have: last==igc_last_comb(k, n) // // Example with k==3, n==5: // x inverse_gray_code(x) // ..111 ..1.1 == first_sequency(k) // .11.1 .1..1 // .111. .1.11 // .1.11 .11.1 // 11..1 1...1 // 11.1. 1..11 // 111.. 1.111 // 1.1.1 11..1 // 1.11. 11.11 // 1..11 111.1 == igc_last_comb(k, n) // ========== HEADER FILE src/bits/bitcombshifts.h: ========== class bit_comb_shifts; // Bit combinations in shifts-order. // ========== HEADER FILE src/bits/bitcopy.h: ========== static inline ulong copy_bit(ulong a, ulong isrc, ulong idst); // Copy bit at [isrc] to position [idst]. // Return the modified word. static inline ulong mask_copy_bit(ulong a, ulong msrc, ulong mdst); // Copy bit according at src-mask (msrc) // to the bit according to the dest-mask (mdst). // Both msrc and mdst must have exactly one bit set. // Return the modified word. static inline ulong mask_or_bit(ulong a, ulong msrc, ulong mdst); // Or bit according to src-mask (msrc) // to the bit according to the dest-mask (mdst). // Both msrc and mdst must have exactly one bit set. // If the mdst-position is known to be zero this function // is equivalent to mask_copy_bit(). // Return the modified word. // ========== HEADER FILE src/bits/bitcount.h: ========== static inline ulong bit_count(ulong x); // Return number of set bits. // The sequence of values returned for x = 0, 1, 2, 3, ... is // 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, ... // (OEIS sequence A000120). static inline ulong bit_count_15(ulong x); // Return number of set bits, must have at most 15 set bits. static inline ulong bit_count_3(ulong x); // Return number of set bits, must have at most 3 set bits. static inline int bit_count_cmp(const ulong &a, const ulong &b); // Compare bit counts of a and b. static inline ulong bit_count_sparse(ulong x); // Return number of bits set. static inline ulong bit_count_dense(ulong x); // Return number of bits set. // The loop (of bit_count_sparse()) will execute once for // each unset bit (i.e. zero) of x. static inline ulong bit_block_count(ulong x); // Return number of bit blocks. // E.g.: // ..1..11111...111. -> 3 // ...1..11111...111 -> 3 // ......1.....1.1.. -> 3 // .........111.1111 -> 2 static inline ulong bit_block_ge2_count(ulong x); // Return number of bit blocks with at least 2 bits. // E.g.: // ..1..11111...111. -> 2 // ...1..11111...111 -> 2 // ......1.....1.1.. -> 0 // .........111.1111 -> 2 static inline ulong bit_count_01(ulong x); // Return number of bits in a word // for words of the special form 00...0001...11 // ----- SRCFILE=src/bits/bitcount-v.cc: ----- ulong bit_count_v(const ulong *x, ulong n); // Return sum(j=0, n-1, bit_count(x[j]) ) // ========== HEADER FILE src/bits/bitcyclic-dist.h: ========== static inline ulong bit_cyclic_dist(ulong a, ulong b); // Return minimal bitcount of (t ^ b) // where t runs through the cyclic rotations of a. static inline ulong bit_cyclic_dist(ulong a, ulong b, ulong n); // Return minimal bitcount of (t ^ b) // where t runs through the cyclic rotations of a. // Using n-bit words. // ========== HEADER FILE src/bits/bitcyclic-match.h: ========== static inline ulong bit_cyclic_match(ulong x, ulong y); // Return r if x==rotate_right(y, r) else return ~0UL. // In other words: return // how often the right arg must be rotated right (to match the left) // or, equivalently: // how often the left arg must be rotated left (to match the right) static inline ulong bit_cyclic_match(ulong x, ulong y, ulong n); // Return r if x==rotate_right(y, r, n) else return ~0UL // (using n-bit words) static inline ulong bit_cyclic_dist1_match(ulong x, ulong y); // Return the minimal r so that // c = (x ^ rotate_right(y, r, n)) is a one-bit word. // Return ~0UL if there is no such r. static inline ulong bit_cyclic_dist1_match(ulong x, ulong y, ulong n); // Return the minimal r so that // c = (x ^ rotate_right(y, r, n)) is a one-bit word. // Return ~0UL if there is no such r. // (using n-bit words) // ========== HEADER FILE src/bits/bitcyclic-minmax.h: ========== static inline ulong bit_cyclic_min(ulong x); // Return minimum of all rotations of x static inline ulong bit_cyclic_min(ulong x, ulong n); // Return minimum of all rotations of x using n-bit words static inline ulong bit_cyclic_max(ulong x); // Return maximum of all rotations of x static inline ulong bit_cyclic_max(ulong x, ulong n); // Return maximum of all rotations of x using n-bit words static inline bool is_bit_cyclic_min(ulong x); // Return whether x is the minimum of all rotations of x static inline bool is_bit_cyclic_min(ulong x, ulong n); // Return whether x is the minimum of all rotations of x as n-bit word static inline bool is_bit_cyclic_max(ulong x); // Return whether x is the maximum of all rotations of x static inline bool is_bit_cyclic_max(ulong x, ulong n); // Return whether x is the maximum of all rotations of x as n-bit word // ========== HEADER FILE src/bits/bitcyclic-period.h: ========== static inline ulong bit_cyclic_period(ulong x); // Return minimal positive bit-rotation that transforms x into itself. // (same as bit_cyclic_period(x, BITS_PER_LONG) ) // // The returned value is a divisor of the word length, // i.e. 1,2,4,8,...,BITS_PER_LONG. static inline ulong bit_cyclic_period(ulong x, ulong n); // Return minimal positive bit-rotation that transforms x into itself. // (using n-bit words) // The returned value is a divisor of n. // // Examples for n=6: // word period // ...... 1 // .....1 6 // ....11 6 // ...1.1 6 // ...111 6 // ..1..1 3 // ..1.11 6 // ..11.1 6 // ..1111 6 // .1.1.1 2 // .1.111 6 // .11.11 3 // .11111 6 // 111111 1 // ========== HEADER FILE src/bits/bitcyclic-xor.h: ========== static inline ulong bit_cyclic_rxor(ulong x); // Similar to Gray code, but the bit shifted // out at the right is moved to the highest bit. // The returned word has an even number of bits set. static inline ulong bit_cyclic_rxor(ulong x, ulong n); // Version for n-bit words static inline ulong bit_cyclic_inv_rxor(ulong x); // Return v so that bit_cyclic_rxor(v) == x. // The same relation holds for ~v. // x must have an even number of bits. // Lowest bit of result is zero for valid inputs. // Also the inverse of bit_cyclic_rxor(x,n) for any n. static inline ulong bit_cyclic_lxor(ulong x); // Similar to reversed Gray code, but the bit shifted // out at the left is moved to the lowest bit. // The returned word has an even number of bits set. static inline ulong bit_cyclic_lxor(ulong x, ulong n); // Version for n-bit words static inline ulong bit_cyclic_inv_lxor(ulong x); // Return v so that bit_cyclic_lxor(v) == x. // The same relation holds for ~v. // x must have an even number of bits. // Highest bit of result is zero for valid inputs. // Also the inverse of bit_cyclic_lxor(x,n) for any n. // ========== HEADER FILE src/bits/bitfibgray.h: ========== class bit_fibgray; // Fibonacci Gray code with binary words. // ========== HEADER FILE src/bits/bitgather.h: ========== static inline ulong bit_gather(ulong w, ulong m); // Return word with bits of w collected as indicated by m: // Example: // w = ABCDEFGH // m = 00101100 // ==> 00000CEF // This is the inverse of bit_scatter() static inline ulong bit_scatter(ulong w, ulong m); // Return word with bits of w distributed as indicated by m: // Example: // w = 00000ABC // m = 00101100 // ==> 00A0BC00 // This is the inverse of bit_gather() // ========== HEADER FILE src/bits/bitgraypermute.h: ========== static inline ulong left_swap_16(ulong x); // Return 64-bit word with two leftmost quarters swapped. static inline ulong left_swap_8(ulong x); // Return word with two leftmost quarters of each 32-bit block swapped. static inline ulong left_swap_4(ulong x); // Return word with two leftmost quarters of each 16-bit block swapped. static inline ulong left_swap_2(ulong x); // Return word with two leftmost quarters of each 8-bit block swapped. static inline ulong left_swap_1(ulong x); // Return word with two leftmost bits of each 4-bit block swapped. static inline ulong bit_gray_permute(ulong x); // Return word with gray-permuted bits. static inline ulong bit_inverse_gray_permute(ulong x); // Inverse of bit_gray_permute() // ========== HEADER FILE src/bits/bithigh-edge.h: ========== static inline ulong highest_one_01edge(ulong x); // Return word where all bits from (including) the // highest set bit to bit 0 are set. // Return 0 if no bit is set. // // Feed the result into bit_count() to get // the index of the highest bit set. static inline ulong highest_one_10edge(ulong x); // Return word where all bits from (including) the // highest set bit to most significant bit are set. // Return 0 if no bit is set. // ========== HEADER FILE src/bits/bithigh.h: ========== static inline ulong highest_one(ulong x); // Return word where only the highest bit in x is set. // Return 0 if no bit is set. static inline ulong highest_zero(ulong x); // Return word where only the highest unset bit in x is set. // Return 0 if all bits are set. static inline ulong set_highest_zero(ulong x); // Return word where the highest unset bit in x is set. // Return ~0 for input == ~0. static inline ulong highest_one_idx(ulong x); // Return index of highest bit set. // Return 0 if no bit is set. static inline ulong highest_zero_idx(ulong x); static inline ulong high_zeros(ulong x); // Return word where all the (high end) zeros are set. // e.g.: 00011001 --> 11100000 // Return 0 if highest bit is set: // 11011001 --> 00000000 static inline ulong high_ones(ulong x); // Return word where all the (high end) ones are set. // e.g. 11001011 --> 11000000 // Return 0 if highest bit is zero: // 01110110 --> 00000000 // ========== HEADER FILE src/bits/bitldeq.h: ========== static inline bool ld_eq(ulong x, ulong y); // Return whether floor(log2(x))==floor(log2(y)). // For arguments 0 and 1 (either order) // ld_eq(x,y) correctly returns false // whereas ld(x) == ld(y) gives true // (because ld(x) returns 0 for both x==1 and x==0). static inline bool ld_neq(ulong x, ulong y); // Return whether floor(log2(x))!=floor(log2(y)) // ========== HEADER FILE src/bits/bitlex.h: ========== static inline ulong next_lexrev(ulong x); // Return next word in subset-lexrev order. // Start with a one-bit word at position n-1 to // generate 2**n subsets of length n. // E.g., for n==4 the subsets are // word subset of {0,1,2,3} // 1... {0} // 11.. {0, 1} // 111. {0, 1, 2} // 1111 {0, 1, 2, 3} // 11.1 {0, 1, 3} // 1.1. {0, 2} // 1.11 {0, 2, 3} // 1..1 {0, 3} // .1.. {1} // .11. {1, 2} // .111 {1, 2, 3} // .1.1 {1, 3} // ..1. {2} // ..11 {2, 3} // ...1 {3} // .... {} // Note (1): the first element of the subset corresponds // to the highest set bit. When interpreting the binary // words via "bit(n)==element n" (as usual), the order // would be: // 1... { 3 } // 11.. { 2, 3 } // 111. { 1, 2, 3 } // 1111 { 0, 1, 2, 3 } // 11.1 { 0, 2, 3 } // 1.1. { 1, 3 } // 1.11 { 0, 1, 3 } // 1..1 { 0, 3 } // .1.. { 2 } // .11. { 1, 2 } // .111 { 0, 1, 2 } // .1.1 { 0, 2 } // ..1. { 1 } // ..11 { 0, 1 } // ...1 { 0 } // Note (2): the lex order for the delta sets would simply // be the counting order (of the words or reversed words // depending on the interpretation as explained above). static inline ulong prev_lexrev(ulong x); // Return previous word in subset-lexrev order. // Start with zero and use 2**n calls // generate 2**n subsets of length n. // E.g., for n==4: // .... = 0 // ...1 = 1 // ..11 = 3 // ..1. = 2 // .1.1 = 5 // .111 = 7 // .11. = 6 // .1.. = 4 // 1..1 = 9 // 1.11 = 11 // 1.1. = 10 // 11.1 = 13 // 1111 = 15 // 111. = 14 // 11.. = 12 // 1... = 8 // static inline ulong negidx2lexrev(ulong k); // // k: negidx2lexrev(k) // 0: ..... // 1: ....1 // 2: ...11 // 3: ...1. // 4: ..1.1 // 5: ..111 // 6: ..11. // 7: ..1.. // 8: .1..1 // 9: .1.11 // 10: .1.1. // 11: .11.1 // 12: .1111 // 13: .111. // 14: .11.. // 15: .1... // 16: 1...1 // static inline ulong lexrev2negidx(ulong x); // inverse of negidx2lexrev() static inline bool is_lexrev_fixed_point(ulong x); // Return whether x is a fixed point in the prev_lexrev() - sequence // ========== HEADER FILE src/bits/bitlow-edge.h: ========== static inline ulong lowest_one_10edge(ulong x); // Return word where all bits from (including) the // lowest set bit to most significant bit are set. // Return 0 if no bit is set. // Example: 00110100 --> 11111100 static inline ulong lowest_one_01edge(ulong x); // Return word where all bits from (including) the // lowest set bit to the least significant bit are set. // Return 0 if no bit is set. // Example: 00110100 --> 00000111 // ========== HEADER FILE src/bits/bitlow.h: ========== static inline ulong lowest_one_idx(ulong x); // Return index of lowest bit set. // Bit index ranges from zero to BITS_PER_LONG-1. // Examples: // ***1 --> 0 // **10 --> 1 // *100 --> 2 // Return 0 (also) if no bit is set. static inline ulong lowest_one_idx_parity(ulong x); // Return the parity of the index of the lowest set bit. // Return zero with x=0. // Sequence for x>=0 (OEIS sequence A096268): // 0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,... static inline ulong lowest_one(ulong x); // Return word where only the lowest set bit in x is set. // Return 0 if no bit is set. static inline ulong lowest_zero(ulong x); // Return word where only the lowest unset bit in x is set. // Return 0 if all bits are set. static inline ulong lowest_block(ulong x); // Isolate lowest block of ones. static inline ulong clear_lowest_one(ulong x); // Return word where the lowest bit set in x is cleared. // Return 0 for input == 0. static inline ulong set_lowest_zero(ulong x); // Return word where the lowest unset bit in x is set. // Return ~0 for input == ~0. static inline ulong low_ones(ulong x); // Return word where all the (low end) ones are set. // Example: 01011011 --> 00000011 // Return 0 if lowest bit is zero: // 10110110 --> 0 static inline ulong low_zeros(ulong x); // Return word where all the (low end) zeros are set. // Example: 01011000 --> 00000111 // Return 0 if all bits are set. static inline ulong low_match(ulong x, ulong y); // Return word that contains all bits at the low end where x and y match. // If x = *0W and y = *1W, then 00W is returned. // ========== HEADER FILE src/bits/bitperiodic.h: ========== static inline ulong bit_copy_periodic(ulong a, ulong p); // Return word that consists of the lowest p bits of a repeated. // E.g.: if p==3 and a=*****xyz (8-bit), the return yzxyzxyz. // Must have p>0. static inline ulong bit_copy_periodic(ulong a, ulong p, ulong ldn); // Return word that consists of the lowest p bits of a repeated // in the lowest ldn bits (upper bits are zero). // E.g.: if p==3, ldn=7 and a=*****xyz (8-bit), the return 0zxyzxyz. // Must have p>0 and ldn>0. // ========== HEADER FILE src/bits/bitrotate.h: ========== static inline ulong bit_rotate_left(ulong x, ulong r); // Return word rotated r bits to the left // (i.e. toward the most significant bit) //. // GCC optimizes the function to asm 'roll %cl,%ebx' static inline ulong bit_rotate_right(ulong x, ulong r); // Return word rotated r bits to the right // (i.e. toward the least significant bit) //. // GCC optimizes the function to asm 'rorl %cl,%ebx' static inline ulong bit_rotate_sgn(ulong x, long r); // Positive r --> shift away from element zero static inline ulong bit_rotate_left(ulong x, ulong r, ulong n); // Return n-bit word rotated r bits to the left // (i.e. toward the most significant bit) // Must have 0 <= r <= n static inline ulong bit_rotate_right(ulong x, ulong r, ulong n); // Return n-bit word rotated r bits to the right // (i.e. toward the least significant bit) // Must have 0 <= r <= n static inline ulong bit_rotate_sgn(ulong x, long r, ulong n); // Positive r --> shift away from element zero // ========== HEADER FILE src/bits/bitseparate.h: ========== static inline ulong bit_separate(ulong w, ulong m, ulong s=BITS_PER_LONG/2); // Return word with bits of w separated as indicated by m. // Bits at positions where m is 0/1 are moved to the low/high end. // Examples: // w = ABCDEFGH // m = 00111100 // ==> CDEFABGH // // w = ABCDEFGH // m = 01010101 // ==> BDFHACEG // // s must contain the number of ones set in m. // For the default s exactly half of the bits must be set in m static inline ulong bit_separate_subwords(ulong w, ulong m, ulong s); // Bit-separate all length-s subwords of w. // s>=2 must divide BITS_PER_LONG. // The mask must be such that exactly half of the bits // in each subword are set. // Examples: // s = 4 // w = ABCD EFGH // m = 0011 1010 // ==> CDAB EGFH // // s = 2 // w = AB CD EF GH // m = 01 10 01 10 // ==> BA CD FE GH // // For s==BITS_PER_LONG the result is as with bit_separate(w, m) // if half of the bits of m are set. // ========== HEADER FILE src/bits/bitsequency.h: ========== static inline ulong bit_sequency(ulong x); // Return the number of zero-one (or one-zero) // transitions (sequency) of x. static inline ulong first_sequency(ulong k); // Return the first (i.e. smallest) word with sequency k, // e.g. 00..00010101010 (seq 8) // e.g. 00..00101010101 (seq 9) // Must have: 0 <= k <= BITS_PER_LONG static inline ulong last_sequency(ulong k, ulong n=BITS_PER_LONG); // Return the last (i.e. biggest) word with sequency k. static inline ulong next_sequency(ulong x); // Return next word with the same number // of zero-one transitions (sequency) as x. // The value of the lowest bit is conserved. // // Zero is returned when there is no further sequence. // // e.g.: // ...1.1.1 -> // ..11.1.1 -> // ..1..1.1 -> // ..1.11.1 -> // ..1.1..1 -> // ..1.1.11 -> // .111.1.1 -> // .11..1.1 -> // .11.11.1 -> // .11.1..1 -> // .11.1.11 -> ... // static inline ulong prev_sequency(ulong x); static inline ulong complement_sequency(ulong x); // Return word whose sequency is BITS_PER_LONG - s // where s is the sequency of x // ========== HEADER FILE src/bits/bitset2set.h: ========== static inline ulong bitset2set(ulong b, ulong *f, ulong n, ulong off=0); // b=[1...1.11] ==> f[] = [0,1,3,7], return=4 // with off=1 ==> f[] = [1,2,4,8], return=4 static inline ulong set2bitset(const ulong *f, ulong n, ulong off=0); // f[] = [0,1,3,7] ==> return=[1...1.11] // Same return with f[] = [1,2,4,8] and off=1 static inline ulong bitset2deltaset(ulong b, ulong *f, ulong n); // b=[1...1.11] ==> f[] = [1,1,0,1,0,0,0,1], return=4 static inline ulong deltaset2bitset(const ulong *f, ulong n); // f[] = [1,1,0,1,0,0,0,1] ==> return=[1...1.11] // ========== HEADER FILE src/bits/bitsperlong.h: ========== // ========== HEADER FILE src/bits/bitsubset-gray.h: ========== class bit_subset_gray; // Generate all all subsets of bits of a given word, // in Gray code (minimal-change) order. // // E.g., for the word ('.' printed for unset bits) // ...11.1. // these words are produced by subsequent next()-calls: // ......1. // ....1.1. // ....1... // ...11... // ...11.1. // ...1..1. // ...1.... // ........ // ========== HEADER FILE src/bits/bitsubset.h: ========== class bit_subset; // Generate all all subsets of bits of a given word. // // E.g., for the word ('.' printed for unset bits) // ...11.1. // these words are produced by subsequent next()-calls: // ......1. // ....1... // ....1.1. // ...1.... // ...1..1. // ...11... // ...11.1. // ........ // // ========== HEADER FILE src/bits/bitsubsetq.h: ========== static inline bool is_subset(ulong u, ulong e); // Return whether the set bits of u are a subset of the set bits of e. // That is, as bitsets, test whether u is a subset of e. static inline bool is_proper_subset(ulong u, ulong e); // Return whether u (as bitset) is a proper subset of e. // ========== HEADER FILE src/bits/bitswap.h: ========== static inline ulong bit_swap_01(ulong a, ulong k1, ulong k2); // Return a with bits at positions [k1] and [k2] swapped. // Bits must have different values (!) // (i.e. one is zero, the other one) // k1==k2 is allowed (a is unchanged then) static inline ulong bit_swap(ulong a, ulong k1, ulong k2); // Return a with bits at positions [k1] and [k2] swapped. // k1==k2 is allowed (a is unchanged then) static inline ulong bit_swap_1(ulong x); // Return x with neighbor bits swapped. static inline ulong bit_swap_2(ulong x); // Return x with groups of 2 bits swapped. static inline ulong bit_swap_4(ulong x); // Return x with groups of 4 bits swapped. static inline ulong bit_swap_8(ulong x); // Return x with groups of 8 bits swapped. static inline ulong bit_swap_16(ulong x); // Return x with groups of 16 bits swapped. // // For 32 bit words this is identical to either of // rotate_left(x,16) or rotate_right(x,16) static inline ulong bit_swap_32(ulong x); // Return x with groups of 32 bits swapped. // ========== HEADER FILE src/bits/bittest.h: ========== static inline ulong test_bit(ulong a, ulong i); // Return zero if bit[i] is zero, // else return one-bit word with bit[i] set. static inline bool test_bit01(ulong a, ulong i); // Return whether bit[i] is set. static inline ulong set_bit(ulong a, ulong i); // Return a with bit[i] set. static inline ulong clear_bit(ulong a, ulong i); // Return a with bit[i] cleared. static inline ulong change_bit(ulong a, ulong i); // Return a with bit[i] changed. // ========== HEADER FILE src/bits/bittransforms.h: ========== static inline ulong blue_code(ulong a); // Self-inverse. // range [0..2^k-1] is mapped onto itself // work \prop log_2(BITS_PER_LONG) //. // With B:=blue, G:=gray, I:=inverse_gray // G(B(G(B(a)))) == a // G(B(G(a))) == B(a) // I(B(I(a))) == B(a) // G(B(a)) == B(I(a)) // With P:=parity // P(B(a)) == a % 2 static inline ulong yellow_code(ulong a); // Self-inverse. // work \prop log_2(BITS_PER_LONG) //. // With Y:=yellow, B:=blue, r:=revbin // B(a) == Y(r(Y(a))) // Y(a) == r(B(r(a))) // r(a) == Y(B(Y(a))) == B(Y(B(a))) // With P:=parity // P(Y(a)) == highest_one(a) == "sign(a)" static inline ulong red_code(ulong a); // work \prop log_2(BITS_PER_LONG) // =^= revbin( blue_code(a) ); static inline ulong green_code(ulong a); // work \prop log_2(BITS_PER_LONG) // =^= revbin( yellow_code(a) ); // ========== HEADER FILE src/bits/bitxtransforms.h: ========== static inline ulong blue_xcode(ulong a, ulong x); static inline ulong yellow_xcode(ulong a, ulong x); static inline ulong red_xcode(ulong a, ulong x); static inline ulong green_xcode(ulong a, ulong x); // ========== HEADER FILE src/bits/bitzip-pairs.h: ========== static inline ulong bit_zip0_pairs(ulong x); // Return word with lower half bits(-pairs) in even (pair-)indices, // i.e., indices 4k+0, 4k+1. // Upper half must be zero. // 0000abcd --> 0a0b0c0d (a,b,c,d are pairs of bits). static inline ulong bit_unzip0_pairs(ulong x); // Gather pairs bits in even positions (4k+0, 4k+1) into lower half. // Inverse of bit_zip0_pairs(). // Bit pairs at odd (pair-)positions (4k+2, 4k+3) must be zero. // 0a0b0c0d --> 0000abcd (a,b,c,d are pairs of bits). // ========== HEADER FILE src/bits/bitzip.h: ========== static inline ulong bit_zip(ulong x); // Return word with lower half bits in even indices // and upper half bits in odd indices. static inline ulong bit_unzip(ulong x); // Return word with even indexed bits in lower half // and odd indexed bits in upper half. // Inverse of bit_zip() static inline ulong bit_zip0(ulong x); // Return word with lower half bits in even indices. // upper half must be zero. // Same effect as bit_zip() but faster. // 0000abcd --> 0a0b0c0d (a,b,c,d are bits). static inline ulong bit_unzip0(ulong x); // Gather bits in even positions into lower half. // Inverse of bit_zip0(). // Bits at odd positions must be zero. // 0a0b0c0d --> 0000abcd (a,b,c,d are bits). static inline void bit_zip2(ulong x, ulong &lo, ulong &hi); // Bits of lower half word spread out into even positions of lo, // bits of upper half word spread out into even positions of hi. static inline ulong bit_unzip2(ulong lo, ulong hi); // Inverse of bit_zip2(x, lo, hi). static inline ulong bit_zip2(ulong x, ulong y); // 2-word version: // only the lower half of x and y are merged static inline void bit_unzip2(ulong t, ulong &x, ulong &y); // 2-word version: // only the lower half of x and y are filled // ========== HEADER FILE src/bits/blue-fixed-points.h: ========== static inline ulong blue_fixed_point(ulong s); // Return unique fixed point of blue_code() for each argument. //. // The first few fixed points (bfp) are: // arg = arg_2 : bfp_2 = bfp // 0 = ...... : .......... = 0 // 1 = .....1 : .........1 = 1 // 2 = ....1. : .......11. = 6 // 3 = ....11 : .......111 = 7 // 4 = ...1.. : .....1.1.. = 20 // 5 = ...1.1 : .....1..1. = 18 // 6 = ...11. : .....1.1.1 = 21 // 7 = ...111 : .....1..11 = 19 // 8 = ..1... : ...1111... = 120 // 9 = ..1..1 : ...11.11.. = 108 // 10 = ..1.1. : ...111111. = 126 // 11 = ..1.11 : ...11.1.1. = 106 // 12 = ..11.. : ...1111..1 = 121 // 13 = ..11.1 : ...11.11.1 = 109 // 14 = ..111. : ...1111111 = 127 // 15 = ..1111 : ...11.1.11 = 107 // 16 = .1.... : .1...1.... = 272 // 17 = .1...1 : .1.11.1... = 360 static inline ulong blue_fixed_point_idx(ulong f); // Inverse of blue_fixed_point() // ========== HEADER FILE src/bits/branchless.h: ========== // Some functions that avoid if-statements. // The upos_*() functions only work for a limited range // in order to have the highest bit emulate the carry flag. // The trick is to use signed shift right to get a mask // which == 0xfff... if a carry ocurred or zero else. // // With CPUs that have conditional-move instructions // the compiler should produce branch-free machine code. // GCC does that (in many situations; check to be sure). static inline ulong upos_max(ulong a, ulong b); // Return maximum(a, b) // Both a and b must not have the most significant bit set static inline ulong upos_min(ulong a, ulong b); // Return minimum(a, b) // Both a and b must not have the most significant bit set static inline ulong upos_abs_diff(ulong a, ulong b); // Return abs(a-b) // Both a and b must not have the most significant bit set static inline void upos_sort2(ulong &a, ulong &b); // Set {a, b} := {min(a, b), max(a,b)} // Both a and b must not have the most significant bit set static inline ulong upos_add_sat(ulong a, ulong b); // Return a + b // If result overflows, return 0xfff... // Both a and b must not have the most significant bit set static inline ulong upos_sub_sat(ulong a, ulong b); // Return a - b // if result underflows, return zero // Both a and b must not have the most significant bit set static inline ushort add_sat16(ushort a, ushort b); // Add two 16-bit numbers // if result overflows, return 0xffff. // Must have: sizeof(int)==4 static inline ushort sub_sat16(ushort a, ushort b); // Add two 16-bit numbers // if result underflows, return zero. // Must have: sizeof(int)==4 static inline long max0(long x); // Return max(0, x), i.e. return zero for negative input // No restriction on input range static inline long min0(long x); // Return min(0, x), i.e. return zero for positive input // No restriction on input range static inline long clip_range0(long x, long m); // Code equivalent (for m>0) to: // if ( x<0 ) x = 0; // else if ( x>m ) x = m; // return x; static inline long clip_range(long x, long mi, long ma); // Code equivalent to (for mi<=ma): // if ( xma ) x = ma; // ========== HEADER FILE src/bits/colormix-fl.h: ========== // Various operations on 32-bit integers where 3 color channels // of 8 bit are expected to be in the least significant 24 bits. // The order (e.g. 0x00RRGGBB vs. 0x00BBGGRR) does not matter. // This file contains the scaling operations with floating point // numbers. Note that the conversion float<-->int is expensive. static inline uint fl_color01(uint c, double v); // 0.0 ... +1.0 // 0 c2 static inline uint fl_ccolor11(uint c, double v); // -1.0 ... 0.0 ... +1.0 // complement(c) 0 c static inline uint fl_color_mix_11(uint c1, uint c2, double v); // -1.0 ... 0.0 ... +1.0 // c1 (c1+c2)/2 c2 static inline uint fl_color_mix_1b1(uint c1, uint c2, double v); // -1.0 ... 0.0 ... +1.0 // c1 0 c2 // ========== HEADER FILE src/bits/colormix.h: ========== // operations on 32-bit integers where 3 color channels // of 8 bit are expected to be in the least significant 24 bits. // The order (e.g. 0x00RRGGBB vs. 0x00BBGGRR) does not matter. static inline uint color01(uint c, ulong v); // Return color with each channel scaled by v // 0 <= v <= (1<<16) corresponding to 0.0 ... 1.0 static inline uint color_mix(uint c1, uint c2, ulong v); // Return channel-wise average of colors: (1.0-v)*c1 + v*c2 // 0 <= v <= (1<<16) corresponding to 0.0 ... 1.0 // c1 ... c2 static inline uint color_mix_50(uint c1, uint c2); // Return channel-wise average of colors c1 and c2 // Shortcut for the special case (50% transparency) // of color_mix(c1, c2, "0.5") // The least significant bits are ignored // (in all functions color_mix_NN() ) static inline uint color_mix_25(uint c1, uint c2); static inline uint color_mix_75(uint c1, uint c2); static inline uint color_mix_25(uint c1, uint c2, uint c3); static inline uint color_mix_50(uint c1, uint c2, uint c3); static inline uint color_mix_75(uint c1, uint c2, uint c3); static inline uint color_sum_adjust(uint s); // Set color channel to max (0xff) iff an overflow occurred // (that is, leftmost bit in channel is set) static inline uint color_sum(uint c1, uint c2); // Return channel-wise saturated sum of colors c1 and c2. // The least significant bits are ignored. static inline uint color_sum(uint c0, uint c1, uint c2); // Return channel-wise saturated sum of colors c0, c1 and c2. // The least significant bits are ignored. static inline uint color_mult(uint c1, uint c2); // Return channel-wise product of colors c1 and c2. // Corresponding to an object of color c1 // illuminated by a light of color c2 // ========== HEADER FILE src/bits/colormixp.h: ========== // Versions of some functionss from colormix.h that // do not ignore the least significant bit // (and are more expensive). // // The non-'perfect' versions should be ok for // the majority of applications. static inline uint perfect_color_mix_50(uint c1, uint c2); // Return channel-wise average of colors c1 and c2 static inline uint perfect_color_mix_75(uint c1, uint c2); static inline uint perfect_color_sum(uint c1, uint c2); static inline uint perfect_color_sum(uint c0, uint c1, uint c2); // ========== HEADER FILE src/bits/crc32.h: ========== class crc32; // 32-bit CRC (cyclic redundancy check) // ========== HEADER FILE src/bits/crc64.h: ========== class crc64; // 64-bit CRC (cyclic redundancy check) // ========== HEADER FILE src/bits/cswap.h: ========== static inline void cswap_lt(ulong &a, ulong &b); // Branchless equivalent to: // if ( ab ) { ulong t=a; a=b; b=t; } // swap if a > b // ========== HEADER FILE src/bits/evenodd.h: ========== // ========== HEADER FILE src/bits/fibrep-subset-lexrev.h: ========== static inline ulong next_subset_lexrev_fib(ulong x); // Return next Fibonacci word in subset-lex order. // Start with a one-bit word at position n-1 to // generate all Fibonacci words of length n // E.g., for n==6 the words (and subsets) are // word subset of {0,1,2,3,4,5} // 1: 1..... = { 0 } // 2: 1.1... = { 0, 2 } // 3: 1.1.1. = { 0, 2, 4 } // 4: 1.1..1 = { 0, 2, 5 } // 5: 1..1.. = { 0, 3 } // 6: 1..1.1 = { 0, 3, 5 } // 7: 1...1. = { 0, 4 } // 8: 1....1 = { 0, 5 } // 9: .1.... = { 1 } // 10: .1.1.. = { 1, 3 } // 11: .1.1.1 = { 1, 3, 5 } // 12: .1..1. = { 1, 4 } // 13: .1...1 = { 1, 5 } // 14: ..1... = { 2 } // 15: ..1.1. = { 2, 4 } // 16: ..1..1 = { 2, 5 } // 17: ...1.. = { 3 } // 18: ...1.1 = { 3, 5 } // 19: ....1. = { 4 } // 20: .....1 = { 5 } // 21: ...... = { } // // Note (1): the first element of the subset corresponds // to the highest set bit. // Note (2): the lex order for the delta sets would simply // be the counting order. static inline ulong prev_subset_lexrev_fib(ulong x); // Return previous Fibonacci word in subset-lex order. // Start with zero to generate all words of length n. // E.g., for n==6: // word subset of {0,1,2,3,4,5} // 0: ...... = { } // 1: .....1 = { 5 } // 2: ....1. = { 4 } // 3: ...1.1 = { 3, 5 } // 4: ...1.. = { 3 } // 5: ..1..1 = { 2, 5 } // 6: ..1.1. = { 2, 4 } // 7: ..1... = { 2 } // 8: .1...1 = { 1, 5 } // 9: .1..1. = { 1, 4 } // 10: .1.1.1 = { 1, 3, 5 } // 11: .1.1.. = { 1, 3 } // 12: .1.... = { 1 } // 13: 1....1 = { 0, 5 } // 14: 1...1. = { 0, 4 } // 15: 1..1.1 = { 0, 3, 5 } // 16: 1..1.. = { 0, 3 } // 17: 1.1..1 = { 0, 2, 5 } // 18: 1.1.1. = { 0, 2, 4 } // 19: 1.1... = { 0, 2 } // 20: 1..... = { 0 } // // ========== HEADER FILE src/bits/fibrep.h: ========== static inline ulong bin2fibrep(ulong b); // Return Fibonacci representation of b // Limitation: the first Fibonacci number greater // than b must be representable as ulong. // 32 bit: b < 2971215073=F(47) [F(48)=4807526976 > 2^32] // 64 bit: b < 12200160415121876738=F(93) [F(94) > 2^64] static inline ulong fibrep2bin(ulong f); // Return binary representation of f // Inverse of bin2fibrep(). static inline ulong next_fibrep(ulong x); // With x the Fibonacci representation of n // return Fibonacci representation of n+1. static inline ulong prev_fibrep(ulong x); // With x the Fibonacci representation of n // return Fibonacci representation of n-1. static inline bool is_fibrep(ulong f); // Return whether f is a valid Fibonacci representation, // that is, whether it does not contain two adjacent ones. // ========== HEADER FILE src/bits/graycode.h: ========== static inline ulong gray_code(ulong x); // Return the Gray code of x // ('bit-wise derivative modulo 2') static inline ulong inverse_gray_code(ulong x); // inverse of gray_code() // note: the returned value contains at each bit position // the parity of all bits of the input left from it (incl. itself) // static inline ulong byte_gray_code(ulong x); // Return the Gray code of bytes in parallel static inline ulong byte_inverse_gray_code(ulong x); // Return the inverse Gray code of bytes in parallel // ========== HEADER FILE src/bits/graypower.h: ========== static inline ulong gray_pow(ulong x, ulong e); // Return (gray_code**e)(x) // gray_pow(x, 1) == gray_code(x) // gray_pow(x, BITS_PER_LONG-1) == inverse_gray_code(x) static inline ulong inverse_gray_pow(ulong x, ulong e); // Return (inverse_gray_code**(e))(x) // == (gray_code**(-e))(x) // inverse_gray_pow(x, 1) == inverse_gray_code(x) // inverse_gray_pow(x, BITS_PER_LONG-1) == gray_code(x) static inline ulong rev_gray_pow(ulong x, ulong e); // Return (rev_gray_code**e)(x) // rev_gray_pow(x, 1) == rev_gray_code(x) // rev_gray_pow(x, BITS_PER_LONG-1) == inverse_rev_gray_code(x) static inline ulong inverse_rev_gray_pow(ulong x, ulong e); // Return (inverse_rev_gray_code**(e))(x) // == (rev_gray_code**(-e))(x) // inverse_rev_gray_pow(x, 1) == inverse_rev_gray_code(x) // inverse_rev_gray_pow(x, BITS_PER_LONG-1) == rev_gray_code(x) // ========== HEADER FILE src/bits/grsnegative.h: ========== static inline ulong grs_negative_q(ulong x); // Return whether the Golay-Rudin-Shapiro sequence // (OEIS sequence A020985) is negative for index x // Return 1 for x = // 3,6,11,12,13,15,19,22,24,25,26,30,35,38,43,44,45,47,48,49, // 50,52,53,55,59,60,61,63,67,70,75,76,77,79,83,86,88,89,90,94, // 96,97,98,100,101,103,104,105,106,110,115,118,120,121,122, // 126,131,134,139,140, ... // // Algorithm: count bit pairs modulo 2 // static inline ulong grs_next(ulong k, ulong g); // With g == grs_negative_q(k), compute grs_negative_q(k+1). // ========== HEADER FILE src/bits/hilbert.h: ========== // ----- SRCFILE=src/bits/lin2hilbert.cc: ----- void lin2hilbert(ulong t, ulong &x, ulong &y); // Transform linear coordinate t to Hilbert x and y ulong hilbert2lin(ulong x, ulong y); // Transform Hilbert x and y to linear coordinate t ulong hilbert_gray_code(ulong t); // A Gray code based on the function lin2hilbert(). // Equivalent to the following sequence of statements: // { lin2hilbert(t, x, y); // x=gray_code(x); y=gray_code(y); // return bitzip2(x, y); } ulong inverse_hilbert_gray_code(ulong g); // Inverse of hilbert_gray_code() static inline ulong hilbert_p(ulong t); // Let (dx,dy) be the (horizontal,vertical) move // with step t of the Hilbert curve. // Return zero if (dx+dy)==-1, else one (then: (dx+dy)==+1). // Used in hilbert_dir() // Algorithm: count number of threes in radix 4 expansion of t. static inline ulong hilbert_m(ulong t); // Let (dx,dy) be the (horizontal,vertical) move // with step t of the Hilbert curve. // Return zero if (dx-dy)==-1, else one (then: (dx-dy)==+1). // Used in hilbert_dir() static inline ulong hilbert_dir(ulong t); // Return encoding of the the next move with the Hilbert curve. // // d \in {0,1,2,3} as follows: // d : direction // 0 : right (+x: dx=+1, dy= 0) // 1 : down (-y: dx= 0, dy=-1) // 2 : up (+y: dx= 0, dy=+1) // 3 : left (-x: dx=-1, dy= 0) // // To print symbollically: cout << (">v^<")[ d ]; // // dx+dy: ++-+++-+++----++++-+++-+++----++++-+++-+++----+---+---+---++++- // dx-dy: +----+++-+++-+++-++++---+---+----++++---+---+----++++---+---+-- // dir: >^<^^>v>^>vv>^>v>>^<^>^<v>>^<^>^<vv<^^< static inline int hilbert_turn(ulong t); // Return the turn (left or right) with the steps // t and t-1 of the Hilbert curve. // Returned value is // 0 for no turn // +1 for right turn // -1 for left turn // // To print symbollically: cout << ("-0+")[ u ]; // dir: >^<^^>v>^>vv>^>v>>^<^>^<v>>^<^>^<vv<^^< // turn: 0--+0++--++0+--0-++-0--++--0-++00++-0--++--0-++-0--+0++--++0+-- // ========== HEADER FILE src/bits/ith-one-idx.h: ========== static inline ulong ith_one_idx(ulong x, ulong i); // Return index of the i-th set bit of x // where 0 <= i < bit_count(x). // ========== HEADER FILE src/bits/kolakoski-seq.h: ========== class kolakoski_seq; // Generator for the Oldenburger-Kolakoski sequence. // See OEIS sequence A000002. // Cf. https://en.wikipedia.org/wiki/Kolakoski_sequence // Algorithm by David Eppstein, see // https://11011110.github.io/blog/2016/10/14/kolakoski-sequence-via.html // ========== HEADER FILE src/bits/negbin.h: ========== // Conversion to and from radix(-2). static inline ulong bin2neg(ulong x); // binary --> radix(-2) //. // HAKMEM, item 128 static inline ulong neg2bin(ulong x); // radix(-2) --> binary // inverse of bin2neg() static inline ulong negbin_fixed_point(ulong k); // Return the k-th fixed point of bin2neg() // With k=000000ABCDEF (binary) the returned value is 0A0B0C0D0E0F. static inline ulong next_negbin(ulong x); // With x the radix(-2) representation of n // return radix(-2) representation of n+1. static inline ulong prev_negbin(ulong x); // With x the radix(-2) representation of n // return radix(-2) representation of n-1. static inline ulong negbin_add(ulong a, ulong b); // Addition of two numbers in radix(-2) representation. // ========== HEADER FILE src/bits/nextgray.h: ========== static inline ulong next_gray2(ulong x); // With input x==gray_code(2*k) the return is gray_code(2*k+2). // Let x1 be the word x shifted right once // and i1 its inverse Gray code. // Let r1 be the return r shifted right once. // Then r1 = gray_code(i1+1). // That is, we have a Gray code counter. // The argument must have an even number of bits. // // k: g(k) g(2*k) g(k) p // 0: ....... ....... ...... . ...... . // 1: ......1 .....11 .....1 1 .....+ 1 // 2: .....11 ....11. ....11 . ....+1 . // 3: .....1. ....1.1 ....1. 1 ....1- 1 // 4: ....11. ...11.. ...11. . ...+1. . // 5: ....111 ...1111 ...111 1 ...11+ 1 // 6: ....1.1 ...1.1. ...1.1 . ...1-1 . // 7: ....1.. ...1..1 ...1.. 1 ...1.- 1 // 8: ...11.. ..11... ..11.. . ..+1.. . // 9: ...11.1 ..11.11 ..11.1 1 ..11.+ 1 // 10: ...1111 ..1111. ..1111 . ..11+1 . // 11: ...111. ..111.1 ..111. 1 ..111- 1 // 12: ...1.1. ..1.1.. ..1.1. . ..1-1. . // 13: ...1.11 ..1.111 ..1.11 1 ..1.1+ 1 // 14: ...1..1 ..1..1. ..1..1 . ..1.-1 . // 15: ...1... ..1...1 ..1... 1 ..1..- 1 // 16: ..11... .11.... .11... . .+1... . // 17: ..11..1 .11..11 .11..1 1 .11..+ 1 // // Note that the changes with increment always // happen one position left of the rightmost bit. // // Convert an arbitrary (Gray code) word g to // x = (g<<1) ^ parity(g) // in order to use this routine. // ========== HEADER FILE src/bits/parenwords.h: ========== static inline bool is_parenword(ulong x); // Return whether x is a valid paren word. // // Binary words < 16, those that are valid // 'paren words' are marked with 'P': // .... P [empty string] // ...1 P () // ..1. // ..11 P (()) // .1.. // .1.1 P ()() // .11. // .111 P ((())) // 1... // 1..1 // 1.1. // 1.11 P (()()) // 11.. // 11.1 P ()(()) // 111. // 1111 P (((()))) static inline void parenword2str(ulong x, char *str); // Fill paren string corresponding to x into str. // // Binary words < 32 that are valid // 'paren words' together with paren-string: // ..... [empty string] // ....1 () // ...11 (()) // ..1.1 ()() // ..111 ((())) // .1.11 (()()) // .11.1 ()(()) // .1111 (((()))) // 1..11 (())() // 1.1.1 ()()() // 1.111 ((()())) // 11.11 (()(())) // 111.1 ()((())) // 11111 ((((())))) // Note 1: lower bits in word (right end) correspond // to the begin of string (left end). // Note 2: Word is extended with zeros (to the left) when necessary, // so the length of str must be >= 1 + 2*(number of set bits) static inline ulong first_parenword(ulong n); // Return least binary word corresponding to n pairs of parens. // Example, n=5: .....11111 ((((())))) static inline ulong last_parenword(ulong n); // Return biggest binary word corresponding to n pairs of parens. // Must have: 1 <= n <= BITS_PER_LONG/2. // Example, n=5: .1.1.1.1.1 ()()()()() static inline ulong next_parenword(ulong x); // Next (colex order) binary word that is a paren word. // With n=4 and starting with first_parenword(n) // one gets the following sequence: // .....1111 (((()))) // ....1.111 ((()())) // ....11.11 (()(())) // ....111.1 ()((())) // ...1..111 ((())()) // ...1.1.11 (()()()) // ...1.11.1 ()(()()) // ...11..11 (())(()) // ...11.1.1 ()()(()) // ..1...111 ((()))() // ..1..1.11 (()())() // ..1..11.1 ()(())() // ..1.1..11 (())()() // ..1.1.1.1 ()()()() // ......... [zero] // ========== HEADER FILE src/bits/parity.h: ========== static inline ulong byte_parity(ulong x); // Return the parities of bytes in parallel static inline ulong parity(ulong x); // Return 0 if the number of set bits is even, else 1 // ========== HEADER FILE src/bits/pcrc64.h: ========== class pcrc64; // Parallel computation of 64-bit CRCs for each bit of the input words. // Primitive polynomial used is x^64 + x^4 + x^3 + x^2 + 1 // ========== HEADER FILE src/bits/print-bin.h: ========== // ----- SRCFILE=src/bits/print-bin.cc: ----- void print_bin(const char *bla, unsigned long long x, ulong pd/*=0*/, const char *c01/*=nullptr*/); // Print x to radix-2. // pd: how many bits to print. void print_bin_vec(const char *bla, unsigned long long x, ulong pd/*=0*/, const char *c01/*=nullptr*/); // Print x to radix-2, least significant bits first (as Vector). // pd: how many bits to print. void print_idx_seq(const char *bla, unsigned long long x, ulong off/*=0*/); // Print x as index sequence: // x=....1..11 ==> [0, 1, 4] // With offsets off!=0 start index with off instead of zero. // ----- SRCFILE=src/bits/print-bindiff.cc: ----- void print_bin_diff(const char*bla, unsigned long long x1, unsigned long long x2, ulong pd/*=0*/, const char *c01pm/*=".1+-"*/); // Binary print difference between two values x1 and x2: // Bits that agree between x1 and x2 are printed as // c01pm[0]=='.' for zero and c01pm[1]='1' for one // Bits that differ between x1 and x2 are printed as // c01pm[2]=='+' if set in x2 (i.e. bit was added) // c01pm[3]=='-' if set in x1 (i.e. bit was removed) // Example: // x1==1..11.111 // x2==1.111...1 // eq==11.111..1 // output = "1.+11.--1" void print_bin_vec_diff(const char*bla, unsigned long long x1, unsigned long long x2, ulong pd/*=0*/, const char *c01pm/*=".1+-"*/); // ----- SRCFILE=src/bits/print-bitset.cc: ----- void print_bit_set(const char *bla, ulong x, ulong rq/*=0*/); // Print delta set given as word x as set. // Example: x=[0,0,1,0,1,1] ==> { 0, 1, 3 } // if rq!=0 then print set for rq-bit reversed binary word: // Example: rq=6, x=[0,0,1,0,1,1] ==> { 3, 1, 0 } // ========== HEADER FILE src/bits/radix-2i.h: ========== // Conversion to and from radix(2*i), "quater-imaginary base". // The radix(2*i) representation for complex integers needs // one digit (i.e., two bits) after the point. static inline ulong bin_real_to_rad2i(ulong x); // binary --> radix(2*i) static inline ulong bin_imag_to_rad2i(ulong x); // binary * i --> radix(2*i) static inline ulong bin_to_rad2i(ulong re, ulong im); // binary ( re + i * im ) --> radix(2*i) static inline ulong rad2i_to_bin_real(ulong x); // radix(2*i) (must be purely real) --> binary static inline ulong rad2i_to_bin_imag(ulong x); // radix(2*) (must be purely imaginary) --> binary static inline void rad2i_to_bin(ulong z, ulong &re, ulong &im); // radix(2*i) --> binary ( re + i * im ) static inline bool rad2i_is_real(ulong z); // Return whether z is purely real. static inline bool rad2i_is_imag(ulong z); // Return whether z is purely imaginary. // ========== HEADER FILE src/bits/radix-m1pi.h: ========== // Conversion to and from (complex) radix(-1+i). static inline ulong bin_real_to_radm1pi(ulong x); // binary --> radix(-1+i) static inline ulong bin_imag_to_radm1pi(ulong x); // binary * i --> radix(-1+i) static inline ulong add_radm1pi(ulong x, ulong y); // Add radix(-1+i) representations x and y. // Note that x + (x<<1) == x + (-1+i)*x == i*x static inline ulong bin_to_radm1pi(ulong re, ulong im); // binary ( re + i * im ) --> radix(-1+I) static inline ulong radm1pi_to_bin_real(ulong x); // convert radix(-1+i) number (which must be purely real) to binary. static inline ulong radm1pi_to_bin_imag(ulong x); // convert radix(-1+i) number (which must be purely imaginary) to binary. static inline void radm1pi_to_bin(ulong z, ulong &re, ulong &im); // radix(-1+i) --> binary ( re + i * im ) static inline bool radm1pi_is_real(ulong z); // Return whether z is purely real. static inline bool radm1pi_is_imag(ulong z); // Return whether z is purely imaginary. // ========== HEADER FILE src/bits/radix-m4.h: ========== // Conversion to and from radix(-4). static inline ulong bin_to_radm4(ulong x); // binary --> radix(-4) static inline ulong radm4_to_bin(ulong x); // radix(-4) --> binary // inverse of bin_to_radm4() static inline ulong next_radm4(ulong x); // With x the radix(-4) representation of n // return radix(-4) representation of n+1. static inline ulong prev_radm4(ulong x); // With x the radix(-4) representation of n // return radix(-4) representation of n-1. static inline ulong radm4_add(ulong a, ulong b); // Addition of two numbers in radix(-4) representation. // ========== HEADER FILE src/bits/revbin-upd.h: ========== static inline ulong revbin_upd(ulong r, ulong h); // Let n=2**ldn and h=n/2. // Then, with r == revbin(x, ldn) at entry, return revbin(x+1, ldn) // NOTE: routine will hang if called with r the all-ones word static inline void make_revbin_upd_tab(ulong h); // Initialize lookup table used by revbin_tupd() static inline ulong revbin_tupd(ulong r, ulong k); // Let r==revbin(k, ldn) then // return revbin(k+1, ldn). // NOTE 1: need to call make_revbin_upd_tab(ldn) before usage // where ldn=log_2(n) // NOTE 2: different argument structure than revbin_upd() // ========== HEADER FILE src/bits/revbin.h: ========== static inline ulong bswap(ulong x); // Return word with reversed byte order. static inline ulong revbin(ulong x); // Return x with reversed bit order. static inline ulong revbin_t(ulong x); // Return x with reversed bit order. // Table based version. static inline ulong revbin_t_le32(ulong x); // Return x with reversed bit order. // Table based version for lengths less or equal 32 bits. static inline ulong revbin_t_le16(ulong x); // Return x with reversed bit order. // Table based version for lengths less or equal 16 bits. static inline ulong xrevbin(ulong a, ulong x); // Symbolic power of revbin. static inline ulong revbin(ulong x, ulong ldn); // Return word with the ldn least significant bits // (i.e. bit_0 ... bit_{ldn-1}) of x reversed, // the other bits are set to zero. // ========== HEADER FILE src/bits/revgraycode.h: ========== static inline ulong rev_gray_code(ulong x); // Return the reversed Gray code of x. // ('bit-wise derivative modulo 2 towards high bits'). // Also: multiplication by x+1 as binary polynomial. // Also: return x^2+x in binary normal basis. // rev_gray_code(x) == revbin( gray_code( revbin(x) ) ) static inline ulong inverse_rev_gray_code(ulong x); // Inverse of rev_gray_code() // Note: the returned value contains at each bit position the parity // of all bits of the input right from it (incl. itself). // Also: division by x+1 as powers series over GF(2) // Also: return solution of z = x^2+x in binary normal basis. // Note: the statements can be reordered at will. // inverse_rev_gray_code(x) == revbin( inverse_gray_code( revbin(x) ) ) // ========== HEADER FILE src/bits/tcrc64.h: ========== class tcrc64; // 64-bit CRC (cyclic redundancy check) with lookup table // ========== HEADER FILE src/bits/thue-morse.h: ========== class thue_morse; // Thue-Morse sequence // ========== HEADER FILE src/bits/tinyfactors.h: ========== static inline bool is_tiny_prime(ulong n); // For n < BITS_PER_LONG (!) // return whether n is prime static inline bool is_tiny_factor(ulong x, ulong d); // For x,d < BITS_PER_LONG (!) // return whether d divides x (1 and x included as divisors) // No need to check whether d==0 // // ========== HEADER FILE src/bits/zerobyte.h: ========== static inline ulong contains_zero_byte(ulong x); // Determine if any sub-byte of x is zero: // Return zero when x contains no zero-byte and nonzero when it does. // // To scan for other values than zero (e.g. 0xa5) use: // contains_zero_byte( x ^ 0xa5a5a5a5UL ) // ========== HEADER FILE src/bits/zorder.h: ========== // Z-order (or Morton order), a non self-intersecting space filling curve. static inline void zorder_next(ulong &x, ulong &y); static inline void zorder_prev(ulong &x, ulong &y); static inline void zorder3d_next(ulong &x, ulong &y, ulong &z); static inline void zorder3d_prev(ulong &x, ulong &y, ulong &z);