Arndt - Algorithms for Programmers (523138), страница 30
Текст из файла (страница 30)
SOME BIT WIZARDRY8.12174The Gray code of a wordCan easily be computed bystatic inline ulong gray_code(ulong x)// Return the Gray code of x// (’bitwise derivative modulo 2’){return x ^ (x>>1);}The inverse is slightly more expensive. The straight forward idea is to usestatic inline ulong inverse_gray_code(ulong x)// inverse of gray_code(){// VERSION 1 (integration modulo 2):ulong h=1, r=0;do{if ( x & 1 ) r^=h;x >>= 1;h = (h<<1)+1;}while ( x!=0 );return r;}which can be improved to// VERSION 2 (apply graycode BITS_PER_LONG-1 times):ulong r = BITS_PER_LONG;while ( --r ) x ^= x>>1;return x;while the best way to do it is// VERSION 3 (use: gray ** BITSPERLONG == id):x ^= x>>1; // gray ** 1x ^= x>>2; // gray ** 2x ^= x>>4; // gray ** 4x ^= x>>8; // gray ** 8x ^= x>>16; // gray ** 16// here: x = gray**31(input)// note: the statements can be reordered at will#if BITS_PER_LONG >= 64x ^= x>>32; // for 64bit words#endifreturn x;Related to the inverse Gray code is the parity of a word (that is: bit-count modulo two).
The inverseGray code of a word contains at each bit position the parity of all bits of the input left from it (includingitself).static inline ulong parity(ulong x)// return 1 if the number of set bits is even, else 0{return inverse_gray_code(x) & 1;}Be warned that the parity bit of many CPUs is the complement of the above. With the x86-architecturethe parity bit also takes in account only the lowest byte, therefore:static inline ulong asm_parity(ulong x){x ^= (x>>16);x ^= (x>>8);asm ("addl $0, %0 \n""setnp %%al\n"CHAPTER 8. SOME BIT WIZARDRY}"movzx %%al, %0": "=r" (x) : "0" (x) : "eax");return x;Cf. [FXT: file auxbit/bitasm.h]The functionstatic inline ulong grs_negative_q(ulong x)// Return whether the Golay-Rudin-Shapiro sequence// (A020985) is negative for index x// returns 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//{return parity( x & (x>>1) );}proves to be useful in specialized versions of the fast Fourier- and Walsh transform.A byte-wise Gray code can be computed usingstatic inline ulong byte_gray_code(ulong x)// Return the Gray code of bytes in parallel{return x ^ ((x & 0xfefefefe)>>1);}Its inverse isstatic inline ulong byte_inverse_gray_code(ulong x)// Return the inverse Gray code of bytes in parallel{x ^= ((x & 0xfefefefe)>>1);x ^= ((x & 0xfcfcfcfc)>>2);x ^= ((x & 0xf0f0f0f0)>>4);return x;}Therebystatic inline ulong byte_parity(ulong x)// Return the parities of bytes in parallel{return byte_inverse_gray_code(x) & 0x01010101;}The Gray code related functions can be found in [FXT: file auxbit/graycode.h].Similar to the Gray code and its inverse is thestatic inline ulong green_code(ulong x)// Return the green code of x// (’bitwise derivative modulo 2 towards high bits’)//// green_code(x) == revbin(gray_code(revbin(x))){return x ^ (x<<1);}andstatic inline ulong inverse_green_code(ulong x)// inverse of green_code()175CHAPTER 8.
SOME BIT WIZARDRY176// note: the returned value contains at each bit position// the parity of all bits of the input right from it (incl. itself){// use: green ** BITSPERLONG == id:x ^= x<<1; // green ** 1x ^= x<<2; // green ** 2x ^= x<<4; // green ** 4x ^= x<<8; // green ** 8x ^= x<<16; // green ** 16// here: x = green**31(input)// note: the statements can be reordered at will#if BITS_PER_LONG >= 64x ^= x<<32; // for 64bit words#endifreturn x;}Both can be found in [FXT: file auxbit/greencode.h] The green code preserves the lowest set bit whilethe Gray code preserves the highest.Demonstration of Gray/green code and their inverses with different input words:---------------------------------------------------------111.1111....1111................
= 0xef0f0000 == word1..11...1...1...1............... = gray_code..11...1...1...1................ = green_code1.11.1.11111.1.11111111111111111 = inverse_gray_code1.1..1.1.....1.1................ = inverse_green_code---------------------------------------------------------...1....1111....1111111111111111 = 0x10f0ffff == word...11...1...1...1............... = gray_code..11...1...1...1...............1 = green_code...11111.1.11111.1.1.1.1.1.1.1.1 = inverse_gray_code1111.....1.1.....1.1.1.1.1.1.1.1 = inverse_green_code---------------------------------------------------------......1......................... = 0x2000000 == word......11........................
= gray_code.....11......................... = green_code......11111111111111111111111111 = inverse_gray_code1111111......................... = inverse_green_code---------------------------------------------------------111111.1111111111111111111111111 = 0xfdffffff == word1.....11........................ = gray_code.....11........................1 = green_code1.1.1..1.1.1.1.1.1.1.1.1.1.1.1.1 = inverse_gray_code1.1.1.11.1.1.1.1.1.1.1.1.1.1.1.1 = inverse_green_code----------------------------------------------------------The Gray codes of consecutive values change in one bit.
The Gray codes of the Gray codes of consecutivevalues change in one or two bits. The Gray codes of values that have a difference of two changes in two bit.Gray codes of even/odd values have an even/odd number of bits set, respectively. This is demonstratedin [FXT: file demo/gray2-demo.cc]:k:0:1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:24:25:26:27:g(k).............1.....11.....1.....11.....111....1.1....1.....11.....11.1...1111...111....1.1....1.11...1..1...1.....11.....11..1..11.11..11.1...1111...11111..111.1..111....1.1....1.1.1..1.111..1.11.g(g(k)).............1.....1......11....1.1....1......111....11....1.1....1.11...1......1..1...1111...111....11.1...11....1.1....1.1.1..1.11...1.111..1...1..1......1..11..1..1...1111...11111..111....111.1g(2*k)............11....11.....1.1...11.....1111...1.1....1..1..11.....11.11..1111...111.1..1.1....1.111..1..1...1...1.11.....11..11.11.11..11.1.1.1111...111111.111.1..111..1.1.1....1.1.11.1.111..1.11.1g(2*k+1)......1.....1.....111....1.....11.1...111....1.11...1.....11..1..11.1...11111..111....1.1.1..1.11...1..11..1.....11...1.11..1..11.111.11.1...1111.1.11111..111.11.111....1.1..1.1.1.1..1.1111.1.11..CHAPTER 8.
SOME BIT WIZARDRY28:29:30:31:..1..1...1..11..1...1..1......11.11..11.1...11..1..11....1..1...1..111.1...1..1....1177.1..1.1.1..11..1...11.1.....In order two produce a random value with with even/odd many bits set, set the lowest bit of a randomnumber to zero/one and take the Gray code.8.13Generating minimal-change bit combinationsThe wonderfulstatic inline ulong igc_next_minchange_comb(ulong x)// Returns the inverse graycode of the next// combination in minchange order.// Input must be the inverse graycode of the// current combination.{ulong g = green_code(x);ulong i = 2;ulong cb; // ==candidateBits;do{ulong y = (x & ~(i-1)) + i;ulong j = lowest_bit(y) << 1;ulong h = !!(y & j);cb = ((j-h) ^ g) & (j-i);i = j;}while ( 0==cb );return x + lowest_bit(cb);}together withstatic inline ulong igc_last_comb(ulong k, ulong n)// return the (inverse graycode of the) last combination// as in igc_next_minchange_comb(){if ( 0==k ) return 0;else return ((1UL<<n) - 1) ^ (((1UL<<k) - 1) / 3);}could be used as demonstrated instatic 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://xinverse_gray_code(x)//..111..1.1 == first_sequency(k)//.11.1.1..1//.111..1.11//.1.11.11.1//11..11...1//11.1.1..11//111..1.111//1.1.111..1//1.11.11.11//1..11111.1 == igc_last_comb(k, n){x = inverse_gray_code(x);if ( x==last ) return 0;x = igc_next_minchange_comb(x);return gray_code(x);}CHAPTER 8.
SOME BIT WIZARDRY178Each combination is different from the preceding one in exactly two positions. The same run of bitcombinations could be obtained by going through the Gray codes and omitting all words where thebit-count is 6= k. The algorithm shown here, however, is much more efficient.For reasons of efficiency one may prefer code asulong last = igc_last_comb(k, n);ulong c, nc = first_sequency(k);do{c = nc;nc = igc_next_minchange_comb(c);ulong g = gray_code(c);// Here g contains the bitcombination}while ( c!=last );which avoids the repeated computation of the inverse Gray code.As Doug Moore explains [priv.comm.], the algorithm in igc next minchange comb uses the fact that thedifference of two (inverse gray codes of) successive combinations is always a power of two.
Using thisobservation one can derive a different version that checks the pattern of the change:static inline ulong igc_next_minchange_comb(ulong x)// Alternative version.// Amortized time = O(1).{ulong gx = gray_code( x );ulong y, i = 2;do{y = x + i;ulong gy = gray_code( y );ulong r = gx ^ gy;// Check that change consists of exactly one bit// of the new and one bit of the old pattern:if ( is_pow_of_2( r & gy ) && is_pow_of_2( r & gx ) ) break;// is_pow_of_2(x):=((x & -x) == x) returns 1 also for x==0.// But this cannot happen for both tests at the same timei <<= 1;}while ( 1 );return y;}Still another version which needs k, the number of set bits, as a second parameter: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.// Amortized time = O(1).{ulong y, i = 2;do{y = x + i;i <<= 1;}while ( bit_count( gray_code(y) ) != k );return y;}The necessary modification for the generation of the previous combination is minimal:static inline ulong igc_prev_minchange_comb(ulong x, ulong k)// Returns the inverse graycode of the previous combination in minchange order.// Input must be the inverse graycode of the current combination.// Amortized time = O(1).// With input==first the output is the last for n=BITS_PER_LONG{CHAPTER 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
