Arndt - Algorithms for Programmers (523138), страница 27
Текст из файла (страница 27)
. . 11 for positive or negative x,respectively (i.e. arithmetical shift is used). With unsigned type the same expression would be 0 or 1according to whether the leftmost bit of x is set.Computing residues modulo a power of two with unsigned types is equivalent to a bit-and using a mask:ulong a = b % 32;// == b & (32-1)All of the above is done by the compiler’s optimization wherever possible.Division by constants can be replaced by multiplications and shift.
The magic machinery inside thecompiler does it for you:5:test.cc@ ulong foo(ulong a)6:test.cc@ {7:test.cc@ulong b = a / 10;290 0000 8B442404movl 4(%esp),%eax291 0004 F7250000mull .LC33// == 0xcccccccd292 000a 89D0movl %edx,%eax293 000c C1E803shrl $3,%eaxSometimes a good reason to have separate code branches with explicit special values. Similar for modulocomputations with a constant modulus:8:test.cc@ ulong foo(ulong a)9:test.cc@ {53 0000 8B4C2404movl 4(%esp),%ecx10:test.cc@ulong b = a % 10000;57 0004 89C8movl %ecx,%eax58 0006 F7250000mull .LC0// == 0xd1b7175959 000c 89D0movl %edx,%eax60 000e C1E80Dshrl $13,%eax61 0011 69C01027imull $10000,%eax,%eax62 0017 29C1subl %eax,%ecx63 0019 89C8movl %ecx,%eaxTo test whether at least one of a and b equals zero use if ( (a+b)==a ) . This works for signedand unsigned integers. Checking whether both are zero can be done via if ( (a|b)==0 ) .
Thisobviously generalizes for several variables as if ( (a|b|c|..|z)==0 ) ). Test whether exactly one oftwo variables is zero using if ( ((a|b)!=0) && ((a+b)==a) ) .In order to toggle an integer x between two values a and b do:1 Soyou can think of it as ‘unsigned arithmetical’ shift.CHAPTER 8. SOME BIT WIZARDRYprecalculate:toggle:157t = a ^ b;x ^= t;// a <--> bthe equivalent trick for floats isprecalculate:toggle:t = a + b;x = t - x;The following functions should be self explaining. In the spirit of the C language there is no check whetherthe indices used are out of bounds.
That is, if any index is greater than BITS_PER_LONG, the result isundefined. Find these in [FXT: file auxbit/bitcopy.h].inline ulong test_bit(ulong a, ulong i)// Return whether bit[i] is set{ulong b = 1UL << i;return (a & b);}inline ulong set_bit(ulong a, ulong i)// Return a with bit[i] set{return (a | (1UL << i));}inline ulong delete_bit(ulong a, ulong i)// Return a with bit[i] set to zero{return (a & ~(1UL << i));}inline ulong change_bit(ulong a, ulong i)// Return a with bit[i] changed{return (a ^ (1UL << i));}inline ulong copy_bit(ulong a, ulong isrc, ulong idst)// copy bit at [isrc] to position [idst]{ulong v = a & (1UL << isrc);ulong b = 1UL << idst;if ( 0==v ) a &= ~b;elsea |= b;return a;}If the functioninline ulong bit_swap_01(ulong a, ulong i, ulong j)// Swap bits i and j of a// Bits must have different values (!)// (i.e.
one is zero, the other one)// i==j is allowed (a is unchanged then){return a ^ ( (1UL<<i) ^ (1UL<<j) );}appears worthless to you then considerinline ulong bit_swap(ulong a, ulong i, ulong j)// Swap bits i and j of a// i==j is allowed (a is unchanged then){#if 1 // optimized:ulong x = (a >> i) ^ (a >> j);// something to do if bit[i]!=bit[j]:CHAPTER 8.
SOME BIT WIZARDRY158if ( 0!=(x&1) ) a = bit_swap_01(a, i, j);return a;#else // non-optimized version:ulong bi = 1UL << i;ulong bj = 1UL << j;ulong m = ~0UL;m ^= bi;m ^= bj; // use xor to make it work for i==julong t = a & m; // delete bits from aif ( a & bi ) t |= bj;if ( a & bj ) t |= bi;return t;#endif}Never ever think that some code is the ‘fastest possible’, there always another trick that can still improveit. Many factors can have an influence on performance like number of CPU registers or cost of branches.Code that performs well on one machine might perform badly on another.
The old trick to swap variableswithout using a temporary//a=0, b=0a=0, b=1a ^= b; //0011b ^= a; //0010a ^= b; //0010equivalent to:tmp = a; a = b; b = tmp;a=1, b=0101101a=1, b=1010111is pretty much out of fashion today. However in some specific context (like extreme register pressure) itmay be the way to go.8.2Operations on low bits/blocks in a wordThe following functions are taken from [FXT: file auxbit/bitlow.h].The underlying idea is that addition/subtraction of 1 always changes a burst of bits at the lower end ofthe word.Isolation of the lowest set bit is achieved viastatic inline ulong lowest_bit(ulong x)// return word where only the lowest set bit in x is set// return 0 if no bit is set{return x & -x; // use: -x == ~x + 1}The lowest zero (or unset bit) of some word x is then trivially isolated using lowest_bit( ~x ). [FXT:lowest zero in auxbit/bitlow.h]Unsetting the lowest set bit in a word can be achieved viastatic inline ulong delete_lowest_bit(ulong x)// return word were the lowest bit set in x is unset// returns 0 for input == 0{return x & (x-1);}while setting the lowest unset bit is done bystatic inline ulong set_lowest_zero(ulong x)// return word were the lowest unset bit in x is set// returns ~0 for input == ~0{return x | (x+1);}CHAPTER 8.
SOME BIT WIZARDRY159Isolate the burst of low bits/zeros as follows:static inline ulong low_bits(ulong x)// return word where all the (low end) ones// are set// e.g. 01011011 --> 00000011// returns 0 if lowest bit is zero://10110110 --> 0{if ( ~0UL==x ) return ~0UL;return (((x+1)^x) >> 1);}andstatic inline ulong low_zeros(ulong x)// return word where all the (low end) zeros// are set// e.g.
01011000 --> 00000111// returns 0 if all bits are set{if ( 0==x ) return ~0UL;return (((x-1)^x) >> 1);}Isolation of the lowest block of ones (which may have zeros to the right of it) can be achieved via:static inline ulong lowest_block(ulong x)//// x= *****011100// l= 00000000100// y= *****100000// x^y = 00000111100// ret = 00000011100//{ulong l = x & -x; // lowest bitulong y = x + l;x ^= y;return x & (x>>1);}Extracting the index of the lowest bit is easy when the corresponding assembler instruction is used:static inline ulong asm_bsf(ulong x)// Bit Scan Forward{asm ("bsfl %0, %0" : "=r" (x) : "0" (x));return x;}The given example uses gcc’s wonderful feature of Assembler Instructions with C Expression Operands,see the corresponding info page.Without the assembler instruction an algorithm that uses proportional log2 (BITS PER LONG) can be used,so the resulting function may look like2static inline ulong lowest_bit_idx(ulong x)// return index of lowest bit set// return 0 if no bit is set{#if defined BITS_USE_ASMreturn asm_bsf(x);#else // BITS_USE_ASM//if ( 1>=x ) return x-1; // 0 if 1, ~0 if 0//if ( 0==x ) return 0;ulong r = 0;2 thanksgo to Nathan Bullock for emailing this improved (wrt.
non-assembler highest bit idx()) version.CHAPTER 8. SOME BIT WIZARDRYx &= -x;BITS_PER_LONG >= 64if ( x & 0xffffffff00000000if ( x & 0xffff0000ffff0000if ( x & 0xff00ff00ff00ff00if ( x & 0xf0f0f0f0f0f0f0f0if ( x & 0xccccccccccccccccif ( x & 0xaaaaaaaaaaaaaaaa#else // BITS_PER_LONG >= 64if ( x & 0xffff0000 ) r +=if ( x & 0xff00ff00 ) r +=if ( x & 0xf0f0f0f0 ) r +=if ( x & 0xcccccccc ) r +=if ( x & 0xaaaaaaaa ) r +=#endif // BITS_PER_LONG >= 64#endif // BITS_USE_ASMreturn r;}#if))))))rrrrrr+=+=+=+=+=+=16032;16;8;4;2;1;16;8;4;2;1;Occasionally one wants to set a rising or falling edge at the position of the lowest bit:static inline ulong lowest_bit_01edge(ulong x)// return word where a all bits from (including) the//lowest set bit to bit 0 are set// return 0 if no bit is set{if ( 0==x ) return 0;return x^(x-1);}static inline ulong lowest_bit_10edge(ulong x)// return word where a all bits from (including) the//lowest set bit to most significant bit are set// return 0 if no bit is set{if ( 0==x ) return 0;x ^= (x-1);// here x == lowest_bit_01edge(x);return ~(x>>1);}8.3Operations on high bits/blocks in a wordThe following functions are taken from [FXT: file auxbit/bithigh.h].For the functions operating on the highest bit there is not a way as trivial as with the equivalent taskwith the lower end of the word.
With a bit-reverse CPU-instruction available life would be significantlyeasier. However, almost no CPU seems to have it.Isolation of the highest set bit is achieved via the bit-scan instruction when it is availablestatic inline ulong asm_bsr(ulong x)// Bit Scan Reverse{asm ("bsrl %0, %0" : "=r" (x) : "0" (x));return x;}else one may usestatic inline ulong highest_bit_01edge(ulong x)// return word where a all bits from (including) the//highest set bit to bit 0 are set// returns 0 if no bit is set{x |= x>>1;x |= x>>2;x |= x>>4;x |= x>>8;CHAPTER 8. SOME BIT WIZARDRY161x |= x>>16;BITS_PER_LONG >= 64x |= x>>32;#endifreturn x;}#ifso the resulting code may look likestatic inline ulong highest_bit(ulong x)// return word where only the highest bit in x is set// return 0 if no bit is set{#if defined BITS_USE_ASMif ( 0==x ) return 0;x = asm_bsr(x);return 1UL<<x;#elsex = highest_bit_01edge(x);return x ^ (x>>1);#endif // BITS_USE_ASM}triviallystatic 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{return highest_bit( ~x );}andstatic inline ulong set_highest_zero(ulong x)// return word were the highest unset bit in x is set// returns ~0 for input == ~0{return x | highest_bit( ~x );}Finding the index of the highest set bit uses the equivalent algorithm as with the lowest set bit:static inline ulong highest_bit_idx(ulong// return index of highest bit set// return 0 if no bit is set{#if defined BITS_USE_ASMreturn asm_bsr(x);#else // BITS_USE_ASMif ( 0==x ) return 0;ulong r = 0;#if BITS_PER_LONG >= 64if ( x & (~0UL<<32) ) { x >>= 32; r#endifif ( x & 0xffff0000 ) { x >>= 16; rif ( x & 0x0000ff00 ) { x >>= 8; rif ( x & 0x000000f0 ) { x >>= 4; rif ( x & 0x0000000c ) { x >>= 2; rif ( x & 0x00000002 ) {rreturn r;#endif // BITS_USE_ASM}x)+= 32; }+= 16; }+= 8; }+= 4; }+= 2; }+= 1; }Isolation of the high zeros goes likestatic inline ulong high_zeros(ulong x)// return word where all the (high end) zeros are set// e.g.
11001000 --> 00000111// returns 0 if all bits are set{CHAPTER 8. SOME BIT WIZARDRYx |= x>>1;x |= x>>2;x |= x>>4;x |= x>>8;x |= x>>16;#if BITS_PER_LONG >= 64x |= x>>32;#endifreturn ~x;}The high bits could be isolated using arithmetical right shiftstatic inline ulong high_bits(ulong x)// return word where all the (high end) ones are set// e.g.
11001011 --> 11000000// returns 0 if highest bit is zero://01110110 --> 0{long y = (long)x;y &= y>>1;y &= y>>2;y &= y>>4;y &= y>>8;y &= y>>16;#if BITS_PER_LONG >= 64y &= y>>32;#endifreturn (ulong)y;}However, arithmetical shifts may not be cheap, so we better usestatic inline ulong high_bits(ulong x){return high_zeros( ~x );}Demonstration of selected functions with two different input words:---------------------------------------------------------................1111....1111.111 = 0xf0f7 == word................1...............
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
