Arndt - Algorithms for Programmers (523138), страница 31
Текст из файла (страница 31)
SOME BIT WIZARDRY179ulong y, i = 2;do{y = x - i;i <<= 1;}while ( bit_count( gray_code(y) ) != k );return y;}8.14Bitwise rotation of a wordNeither C nor C++ have a statement for bitwise rotation3 . The operations can be ‘emulated’ like thisstatic inline ulong bit_rotate_left(ulong x, ulong r)// return word rotated r bits// to the left (i.e. toward the most significant bit){return (x<<r) | (x>>(BITS_PER_LONG-r));}As already mentioned, GCC emits exactly the one CPU instruction that is meant here, even with nonconstant r.
Well done, GCC folks!Of course the explicit use of the corresponding assembler instruction cannot do any harm: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 2.95.2 optimizes the function to asm ’rorl %cl,%ebx’{#if defined BITS_USE_ASM// use x86 asm codereturn asm_ror(x, r);#elsereturn (x>>r) | (x<<(BITS_PER_LONG-r));#endif}where (see [FXT: file auxbit/bitasm.h]):static inline ulong asm_ror(ulong x, ulong r){asm ("rorl%%cl, %0" : "=r" (x) : "0" (x), "c" (r));return x;}Rotations using only a part of the word length are achieved bystatic inline ulong bit_rotate_left(ulong x, ulong r, ulong ldn)// return ldn-bit word rotated r bits// to the left (i.e.
toward the most significant bit)// must have 0 <= r <= ldn{ulong m = ~0UL >> ( BITS_PER_LONG - ldn );x &= m;x = (x<<r) | (x>>(ldn-r));x &= m;return x;}andstatic inline ulong bit_rotate_right(ulong x, ulong r, ulong ldn)// return ldn-bit word rotated r bits// to the right (i.e. toward the least significant bit)// must have 0 <= r <= ldn3 whichI consider a missing feature.CHAPTER 8. SOME BIT WIZARDRY{}180ulong m = ~0UL >> ( BITS_PER_LONG - ldn );x &= m;x = (x>>r) | (x<<(ldn-r));x &= m;return x;Finally, the functionsstatic inline ulong bit_rotate_sgn(ulong x, long r, ulong ldn)// positive r --> shift away from element zero{if ( r > 0 ) return bit_rotate_left(x, (ulong)r, ldn);elsereturn bit_rotate_right(x, (ulong)-r, ldn);}andstatic inline ulong bit_rotate_sgn(ulong x, long r)// positive r --> shift away from element zero{if ( r > 0 ) return bit_rotate_left(x, (ulong)r);elsereturn bit_rotate_right(x, (ulong)-r);}are often convenient.8.15Functions related to bitwise rotationSome functions related to bitwise rotation can be found in [FXT: file auxbit/bitcyclic.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: returns, 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){ulong r = 0;do{if ( x==y ) return r;y = bit_rotate_right(y, 1);}while ( ++r < BITS_PER_LONG );return ~0UL;}static inline ulong bit_cyclic_min(ulong x)// return minimum of all rotations of x{ulong r = 1;ulong m = x;do{x = bit_rotate_right(x, 1);if ( x<m ) m = x;}while ( ++r < BITS_PER_LONG );return m;}Selecting from all n-bit words those that are equal to their cyclic minimum gives the sequence of thebinary length-n necklaces, see section 12.6.From [FXT: file auxbit/bitcyclic2.h]:CHAPTER 8.
SOME BIT WIZARDRY181static inline ulong bit_cyclic_period(ulong x, ulong ldn)// return minimal positive bit-rotation//that transforms x into itself.// (using ldn-bit words)// Returned value is a divisor of ldn.//// Examples for ldn=6:// ...... 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{ulong y = bit_rotate_right(x, 1, ldn);return bit_cyclic_match(x, y, ldn) + 1;}The version for ldn==BITS_PER_LONG can be optimized: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) )//// Returned value is a divisor of the word length,//i.e.
1,2,4,8,...,BITS_PER_LONG.{ulong r = 1;do{ulong y = bit_rotate_right(x, r);if ( x==y ) return r;r <<= 1;}while ( r < BITS_PER_LONG );return r; // == BITS_PER_LONG}An equivalent optimization is possible for arbitrary word length using the mechanism described in section8.11.inline ulong bit_cyclic_dist(ulong a, ulong b)// Return minimal bitcount of (t ^ b)// where t runs through the cyclic rotations.{ulong d = ~0UL;ulong t = a;do{ulong z = t ^ b;ulong e = bit_count( z );if ( e < d ) d = e;t = bit_rotate_right(t, 1);}while ( t!=a );return d; // not reached}and a equivalent function ulong bit_cyclic_dist(ulong a, ulong b, ulong ldn) for length-ldnwords.CHAPTER 8. SOME BIT WIZARDRY8.16182Bitwise zipThe bitwise zip operation, when straight forward implemented, isulong bit_zip(ulong a, ulong b)// put lower half bits to even indexes, higher half to odd{ulong x = 0;ulong m = 1, s = 0;for (ulong k=0; k<(BITS_PER_LONG/2); ++k){x |= (a & m) << s;++s;x |= (b & m) << s;m <<= 1;}return x;}Its inverse isvoid bit_unzip(ulong x, ulong &a, ulong &b)// put even indexed bits to lower hald, odd indexed to higher half{a = 0; b = 0;ulong m = 1, s = 0;for (ulong k=0; k<(BITS_PER_LONG/2); ++k){a |= (x & m) >> s;++s;m <<= 1;b |= (x & m) >> s;m <<= 1;}}The optimized versions (cf.
[FXT: file auxbit/bitzip.h]), using ideas similar to those in revbin andbit_count, arestatic inline ulong bit_zip(ulong x){#if BITS_PER_LONG == 64x = butterfly_16(x);#endifx = butterfly_8(x);x = butterfly_4(x);x = butterfly_2(x);x = butterfly_1(x);return x;}andstatic inline ulong bit_unzip(ulong x){x = butterfly_1(x);x = butterfly_2(x);x = butterfly_4(x);x = butterfly_8(x);#if BITS_PER_LONG == 64x = butterfly_16(x);#endifreturn x;}Both use the butterfly_*()-functions which look likestatic inline ulong butterfly_4(ulong x){ulong t, ml, mr, s;#if BITS_PER_LONG == 64ml = 0x0f000f000f000f00;CHAPTER 8.
SOME BIT WIZARDRY183#elseml = 0x0f000f00;#endifs = 4;mr = ml >> s;t = ((x & ml) >> s ) | ((x & mr) << s );x = (x & ~(ml | mr)) | t;return x;}The version given by Torsten Sillke (cf. http://www.mathematik.uni-bielefeld.de/~sillke/)static inline ulong Butterfly4(ulong x){ulong m = 0x00f000f0;return ((x & m) << 4) | ((x >> 4) & m) | (x & ~(0x11*m));}looks much nicer, but seems to use one more register (4 instead of 3) when compiled.8.17Bit sequencySome doubtful functions of questionable usefulness can be found in [FXT: file auxbit/bitsequency.h]:static inline ulong bit_sequency(ulong x)// return the number of zero-one (or one-zero)// transitions (sequency) of x.{return bit_count( gray_code(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 be: 1 <= k <= BITS_PER_LONG{return inverse_gray_code( first_comb(k) );}static inline ulong last_sequency(ulong k)// return the lasst (i.e.
biggest) word with sequency k,{return inverse_gray_code( last_comb(k) );}static inline ulong next_sequency(ulong x)// return smallest integer with highest bit at greater or equal// position than the highest bit of x that has 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 -> ...//{CHAPTER 8.
SOME BIT WIZARDRY}184x = gray_code(x);x = next_colex_comb(x);x = inverse_gray_code(x);return x;8.18Misc. . . there is always some stuff that does not fit into any conceivable category. That goes to [FXT: fileauxbit/bitmisc.h], e.g. the occasionally usefulstatic 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.{ulong x = (1UL<<n) - 1;return x << p;}andstatic 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.{ulong x = (1UL<<n) - 1;return (x<<p) | (x>>(BITS_PER_LONG-p));}Rather weird functions likestatic inline ulong single_bits(ulong x)// Return word were only the single bits from x are set{return x & ~( (x<<1) | (x>>1) );}orstatic inline ulong single_values(ulong x)// Return word were only the single bits and the// single zeros from x are set{return (x ^ (x<<1)) & (x ^ (x>>1));}orstatic inline ulong border_values(ulong x)// Return word were those bits/zeros from x are set// that lie next to a zero/bit{ulong g = x ^ (x>>1);g |= (g<<1);returng | (x & 1);}orstatic inline ulong block_bits(ulong x)// Return word were only those bits from x are set// that are part of a block of at least 2 bits{return x & ( (x<<1) | (x>>1) );}CHAPTER 8.
SOME BIT WIZARDRY185orstatic inline ulong interior_bits(ulong x)// Return word were only those bits from x are set// that do not have a zero to their left or right{return x & ( (x<<1) & (x>>1) );}might not be the most often needed functions on this planet, but if you can use them you will love them.[FXT: file auxbit/branchless.h] contains functions that avoid branches.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
