Arndt - Algorithms for Programmers (523138), страница 29
Текст из файла (страница 29)
SOME BIT WIZARDRY// return smallest integer greater than x with the same number//// colex order: (5,3);// 0 1 2..111// 0 1 3.1.11// 0 2 3.11.1// 1 2 3.111.// 0 1 41..11// 0 2 41.1.1// 1 2 41.11.// 0 3 411..1// 1 3 411.1.// 2 3 4111..//// Examples://000001 -> 000010 -> 000100 -> 001000 -> 010000 -> 100000//000011 -> 000101 -> 000110 -> 001001 -> 001010 -> 001100//000111 -> 001011 -> 001101 -> 001110 -> 010011 -> 010101//// Special cases://0 -> 0//all bits on the high side (i.e.
last combination) -> 0//{ulong r = x & -x; // lowest set bitx += r;// replace lowest block by a one left toif ( 0==l ) return 0; // input was last combulong l = x & -x; // first zero beyond low blockl -= r;// low blockwhile ( 0==(l&1) ) { l >>= 1; } // move block to low endreturn x | (l>>1); // need one bit less of low block}168of bits set.-> 010001 -> ...-> 010110 -> ...itof wordOne might consider replacing the while-loop by a bit scan and shift combination.Moving backwards goes likestatic inline ulong prev_colex_comb(ulong x)// inverse of next_colex_comb(){x = next_colex_comb( ~x);if ( 0!=x ) x = ~x;return x;}The relation to lex order enumeration isstatic inline ulong next_lex_comb(ulong x)//// let the zeros move to the lower end in the same manner// as the ones go to the higher end in next_colex_comb()//// lex order: (5, 3):// 0 1 2..111// 0 1 3.1.11// 0 1 41..11// 0 2 3.11.1// 0 2 41.1.1// 0 3 411..1// 1 2 3.111.// 1 2 41.11.// 1 3 411.1.// 2 3 4111..//// start and end combo are the same as for next_colex_comb()//{x = revbin(~x);x = next_colex_comb(x);if ( 0!=x ) x = revbin(~x);return x;}(the bit-reversal routine revbin is shown in section 8.7) andCHAPTER 8.
SOME BIT WIZARDRY169static inline ulong prev_lex_comb(ulong x)// inverse of next_lex_comb(){x = revbin(x);x = next_colex_comb(x);x = revbin(x);return x;}Note that the ones in lex-order(k, n) behave like the zeros in reversed colex-order(n-k, n):Lex( n = 5, k = 3 )forward order:[ 0 1 2 ] ..111[ 0 1 3 ] .1.11[ 0 1 4 ] 1..11[ 0 2 3 ] .11.1[ 0 2 4 ] 1.1.1[ 0 3 4 ] 11..1[ 1 2 3 ] .111.[ 1 2 4 ] 1.11.[ 1 3 4 ] 11.1.[ 2 3 4 ] 111..reverse order:[ 2 3 4 ] 111..[ 1 3 4 ] 11.1.[ 1 2 4 ] 1.11.[ 1 2 3 ] .111.[ 0 3 4 ] 11..1[ 0 2 4 ] 1.1.1[ 0 2 3 ] .11.1[ 0 1 4 ] 1..11[ 0 1 3 ] .1.11[ 0 1 2 ] ..111##########0123456789##########9876543210Colex( n = 5, k = 2reverse order:[ 3 4 ] 11...
#[ 2 4 ] 1.1.. #[ 1 4 ] 1..1. #[ 0 4 ] 1...1 #[ 2 3 ] .11.. #[ 1 3 ] .1.1. #[ 0 3 ] .1..1 #[ 1 2 ] ..11. #[ 0 2 ] ..1.1 #[ 0 1 ] ...11 #forward order:[ 0 1 ] ...11 #[ 0 2 ] ..1.1 #[ 1 2 ] ..11. #[ 0 3 ] .1..1 #[ 1 3 ] .1.1. #[ 2 3 ] .11.. #[ 0 4 ] 1...1 #[ 1 4 ] 1..1. #[ 2 4 ] 1.1.. #[ 3 4 ] 11...
#)98765432100123456789The first and last combination for both colex- and lex order arestatic 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{return ~0UL >> ( BITS_PER_LONG - k );}andstatic 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{return first_comb(k) << (n - k);}Note that the colex-combinations in reversed order are identical to the bit-reversed lex-combinations,thereby:static inline ulong first_rev_comb(ulong k, ulong n=BITS_PER_LONG){return last_comb(k, n);}static inline ulong last_rev_comb(ulong k){return first_comb(k);}static inline ulong next_lexrev_comb(ulong x)// Return next bit-reversed lex-order combination.{return prev_colex_comb(x);}static inline ulong prev_lexrev_comb(ulong x)CHAPTER 8.
SOME BIT WIZARDRY170// Return previous bit-reversed lex-order combination.{return next_colex_comb( x );}These are often the functions of choice when fast generation of bit-combinations is required as they allowto restrict the pattern to a certain length without any overhead.A variant of the presented (colex-) algorithm appears in hakmem [53]. The variant used here avoids thedivision of the hakmem-version and is given at http://www.caam.rice.edu/~dougm/ by Doug Moore andGlenn Rhoads http://remus.rutgers.edu/~rhoads/ (cited in the code is ”Constructive Combinatorics”by Stanton and White).8.9Generating bit subsetsThe sparse counting idea shown on page 164 is used inclass 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.//........//{public:ulong u_, v_;public:bit_subset(ulong vv) : u_(0), v_(vv) { ; }~bit_subset() { ; }ulong current() const { return u_; }ulong next(){ u_ = (u_ - v_) & v_; return u_; }ulong previous() { u_ = (u_ - 1 ) & v_; return u_; }};which can be found in [FXT: file auxbit/bitsubset.h]TBD: sparse count in Gray code order8.10Binary words in lexicographic orderThe (bit-reversed) binary words in lexicographic order are generated by successive calls to the followingfunction:static inline ulong next_lexrev(ulong x)// Return next word in (reversed) lex order.{ulong x0 = x & -x;if ( 1==x0 ){x ^= x0;x0 = x & -x;x0 ^= (x0>>1);}else x0 >>= 1;x ^= x0;return x;}CHAPTER 8.
SOME BIT WIZARDRY171The bit-reversed representation was chosen because the isolation of the lowest bit is often cheaper thanthe same operation on the highest bit. The routine was derived from the code in section 11.10. Startingwith a one-bit word at position n − 1 one generates the 2n bit-subsets of length n:n==4:1...11..111.111111.11.1.1.111..1.1...11..111.1.1..1...11...1A similar function allows to go backward:static inline ulong prev_lexrev(ulong x)// Return previous word in (reversed) lex order.{ulong x0 = x & -x;if ( x & (x0<<1) ) x ^= x0;else{x0 ^= (x0<<1);x ^= x0;x |= 1;}return x;}Starting with zero one gets a sequence of words that just before the 2n -th call has visited every word oflength ≤ n.n==4:0: ....1: ...12: ..113: ..1.4: .1.15: .1116: .11.7: .1..8: 1..19: 1.1110: 1.1.11: 11.112: 111113: 111.14: 11..15: 1...================0132576491110131514128****The ‘*’ mark fixed points of the sequence.Find the described functions in [FXT: file auxbit/bitlex.h].The sequence of fixed pointsThe fixed points of the generated sequence are 0, 1, 6, 10, 18, 34, 60, 66, 92, 108, 116, 130, 156, 172,180, 204, 212, 228, 258, 284, 300, 308, 332, 340, 356, 396, 404, 420, 452, 514, 540, 556, .
. . .Their values as bit patterns:0:1:6:10:18:34:60:66:92:108:116:130:156:172:.....................1........11........1.1.......1..1......1...1......1111......1....1.....1.111......11.11......111.1.....1.....1....1..111.....1.1.11..CHAPTER 8. SOME BIT WIZARDRY172180: ...1.11.1..204: ...11..11..212: ...11.1.1..228: ...111..1..258: ..1......1.284: ..1...111..300: ..1..1.11..308: ..1..11.1..332: ..1.1..11..340: ..1.1.1.1..356: ..1.11..1..396: ..11...11..404: ..11..1.1..420: ..11.1..1..452: ..111...1..514: .1.......1.540: .1....111..556: .1...1.11..[-snip-]1556: ..11....1.1..1572: ..11...1..1..1604: ..11..1...1..1668: ..11.1....1..1796: ..111.....1..2040: ..11111111...2050: .1.........1.2076: .1......111..2092: .1.....1.11..2100: .1.....11.1..2124: .1....1..11..2132: .1....1.1.1..2148: .1....11..1..[-snip-]4644: .1..1...1..1..4676: .1..1..1...1..4740: .1..1.1....1..4868: .1..11.....1..5112: .1..1111111...5132: .1.1......11..5140: .1.1.....1.1..5156: .1.1....1..1..5188: .1.1...1...1..5252: .1.1..1....1..5380: .1.1.1.....1..5624: .1.1.111111...5636: .1.11......1..5880: .1.11.11111...6008: .1.111.1111...6072: .1.1111.111...6104: .1.11111.11...6120: .1.111111.1...6156: .11.......11..6164: .11......1.1..6180: .11.....1..1..Whether x is a fixed point of the sequence is detected by [FXT: is lexrev fixed point inauxbit/bitlex.h]:static inline bool is_lexrev_fixed_point(ulong x)// Return whether x is a fixed point in the prev_lexrev() - sequence{if ( x & 1 ){if ( 1==x ) return true;elsereturn false;}else{ulong w = bit_count(x);if ( w != (w & -w) ) return false;if ( 0==x ) return true;return 0 != ( (x & -x) & w );}}A little contemplation on the structure of the binary words in lex-order leeds to the routineinline ulong negidx2lexrev(ulong k)////k: idx2revlex(k)//0: .....//1: ....1//2: ...11//3: ...1.//4: ..1.1//5: ..111//6: ..11.//7: ..1..//8: .1..1CHAPTER 8.
SOME BIT WIZARDRY//////////////////{}9:10:11:12:13:14:15:16:173.1.11.1.1..11.1.1111.111..11...1...1...1ulong z = 0;ulong h = highest_bit(k);while ( k ){while ( 0==(h&k) ) h >>= 1;z ^= h;++k;k &= h - 1;}return z;8.11Bit set lookupThere is a nice trick to determine whether some input is contained in a tiny set, e.g. lets determinewhether x is a tiny primeulong m = (1UL<<2) | (1UL<<3) | (1UL<<5) | ...
| (1UL<<31);static inline ulong is_tiny_prime(ulong x){return m & (1UL << x);}// precomputedA function using this idea isstatic 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//{return ( 0 != ( (tiny_factors_tab[x]>>d) & 1 ) );}from [FXT: file auxbit/tinyfactors.h] that uses the precomputedextern const ulong tiny_factors_tab[] ={0x0, // x = 0:( bits:0x2, // x = 1: 1( bits:0x6, // x = 2: 1 2( bits:0xa, // x = 3: 1 3( bits:0x16, // x = 4: 1 2 4( bits:0x22, // x = 5: 1 5( bits:0x4e, // x = 6: 1 2 3 6 ( bits:0x82, // x = 7: 1 7( bits:0x116, // x = 8: 1 2 4 80x20a, // x = 9: 1 3 9...0x20000002, // x = 29: 1 290x4000846e, // x = 30: 1 2 3 5 6 10 150x80000002, // x = 31: 1 31#if ( BITS_PER_LONG > 32 )0x100010116, // x = 32: 1 2 4 8 16 320x20000080a, // x = 33: 1 3 11 33...0x2000000000000002, // x = 61: 1 610x4000000080000006, // x = 62: 1 2 31 620x800000000020028a// x = 63: 1 3 7 9 21 63#endif // ( BITS_PER_LONG > 32 )};........)......1.).....11.)....1.1.)...1.11.)..1...1.).1..111.)1.....1.)30CHAPTER 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
