程序员实用算法手册：从低级到高级

需积分: 9 24 浏览量更新于2024-08-02 收藏 4.95MB PDF 举报

"Matters Computational"是一本针对程序员的专业书籍草案，作者是Jörg Arndt，主要探讨一系列精选的算法，特别是那些对编程实践有实际帮助并注重代码实现和优化的部分。该书的目标读者是对所处理算法感兴趣的程序员，他们希望理解并能够创建出高效且经过合理优化的代码。书中首先介绍了一些基础的低级别算法技巧，如操作单个比特、低位或字节块、提取特定位模式（如1s、0s或接近转换点的块）。计算单个set位的索引、处理高位或字节块的操作也有所涉及。此外，作者还涵盖了与二进制对数相关的函数，以及如何计数一个字节中的比特和块。在源代码优化方面，作者讲解了如何避免不必要的分支结构，通过位操作实现字节旋转、二进制项链和位反序等技术。书中还讨论了位级压缩（Bit-wise zip）的概念，以及灰度码、奇偶校验等概念在数据表示中的应用。关于位序列的处理，包括灰码的幂运算以及可逆变换对字节操作的重要性也被深入剖析。对于空间效率，章节标题提到的"Space-fill"可能是指一种填充算法或者是在数据存储中优化空间利用的方法，但具体内容在这部分摘要中并未明确提及，需要查阅原文才能获取详细信息。整体上，这本书不仅提供了算法的核心原理，还强调了在实际编程中如何将这些理论转化为高效、易于理解和维护的代码。对于想要提升算法设计和编码能力的程序员来说，这是一本非常实用的参考资源。随着后续版本的更新和在线软件的配套提供，读者可以持续获取最新的内容和支持。

4 Chapter 1: Bit wizardry

1.1.2 Size of pointer is size of long

On sane architectures a pointer ﬁts into a type long integer. If programming for a 32-bit architecture

(where the size of int and long coincide), casting pointers to integers (and back) will work. The same

code will fail on 64-bit machines. If you have to cast pointers to an integer type, cast them to long. For

portable code better avoid casting pointers to integer types.

1.1.3 Shifts and division

With two’s complement arithmetic division and multiplication by power of 2 is right and left shift,

respectively. This is true for unsigned types and for multiplication (left shift) with signed types. Division

with signed types rounds toward zero, as one would expect, but right shift is a division (by a power of 2)

that rounds to −∞:

int a = -1;

int c = a >> 1; // c == -1

int d = a / 2; // d == 0

The compiler still uses a shift instruction for the division, but with a ‘ﬁx’ for negative values:

9:test.cc @ int foo(int a)

10:test.cc @ {

285 0003 8B442410 movl 16(%esp),%eax // move argument to %eax

11:test.cc @ int s = a >> 1;

289 0007 89C1 movl %eax,%ecx

290 0009 D1F9 sarl $1,%ecx

12:test.cc @ int d = a / 2;

293 000b 89C2 movl %eax,%edx

294 000d C1EA1F shrl $31,%edx // fix: %edx=(%edx<0?1:0)

295 0010 01D0 addl %edx,%eax // fix: add one if a<0

296 0012 D1F8 sarl $1,%eax

For unsigned types the shift would suﬃce. One more reason to use unsigned types whenever possible.

The assembler listing was generated from C code via the following commands:

# create assembler code:

c++ -S -fverbose-asm -g -O2 test.cc -o test.s

# create asm interlaced with source lines:

as -alhnd test.s > test.lst

There are two types of right shifts: a logical and an arithmetical shift. The logical version (shrl in the

above fragment) always ﬁlls the higher bits with zeros, corresponding to division of unsigned types. The

arithmetical shift (sarl in the above fragment) ﬁlls in ones or zeros, according to the most signiﬁcant bit

of the original word.

Computing remainders modulo a power of 2 with unsigned types is equivalent to a bit-and:

ulong a = b % 32; // == b & (32-1)

All of the above is done by the compiler’s optimization wherever possible.

Division by (compile time) constants can be replaced by multiplications and shifts. The compiler does it

for you. A division by the constant 10 is compiled to:

5:test.cc @ ulong foo(ulong a)

6:test.cc @ {

7:test.cc @ ulong b = a / 10;

290 0000 8B442404 movl 4(%esp),%eax

291 0004 F7250000 mull .LC33 // value == 0xcccccccd

292 000a 89D0 movl %edx,%eax

293 000c C1E803 shrl $3,%eax

Thereby it is sometimes reasonable to have separate code branches with explicit special values. Similar

optimizations can be used for the modulo operation if the modulus is a compile time constant. For

example, using modulus 10,000:

8:test.cc @ ulong foo(ulong a)

9:test.cc @ {

53 0000 8B4C2404 movl 4(%esp),%ecx

10:test.cc @ ulong b = a % 10000;

[fxtbook draft of 2009-April-28]

1.1: Trivia 5

57 0004 89C8 movl %ecx,%eax

58 0006 F7250000 mull .LC0 // value == 0xd1b71759

59 000c 89D0 movl %edx,%eax

60 000e C1E80D shrl $13,%eax

61 0011 69C01027 imull $10000,%eax,%eax

62 0017 29C1 subl %eax,%ecx

63 0019 89C8 movl %ecx,%eax

Algorithms to replace divisions by a constant with multiplications and shifts are given in [150], see

also [313].

Note that the C standard leaves the behavior of a right shift of a signed integer as ‘implementation-

deﬁned’. The described behavior (that a negative value remains negative after right shift) is the de facto

standard of all modern C compilers.

1.1.4 A pitfall (two’s complement)

c=................ -c=................ c= 0 -c= 0 <--=

c=...............1 -c=1111111111111111 c= 1 -c= -1

c=..............1. -c=111111111111111. c= 2 -c= -2

c=..............11 -c=11111111111111.1 c= 3 -c= -3

c=.............1.. -c=11111111111111.. c= 4 -c= -4

c=.............1.1 -c=1111111111111.11 c= 5 -c= -5

c=.............11. -c=1111111111111.1. c= 6 -c= -6

[--snip--]

c=.1111111111111.1 -c=1.............11 c= 32765 -c=-32765

c=.11111111111111. -c=1.............1. c= 32766 -c=-32766

c=.111111111111111 -c=1..............1 c= 32767 -c=-32767

c=1............... -c=1............... c=-32768 -c=-32768 <--=

c=1..............1 -c=.111111111111111 c=-32767 -c= 32767

c=1.............1. -c=.11111111111111. c=-32766 -c= 32766

c=1.............11 -c=.1111111111111.1 c=-32765 -c= 32765

c=1............1.. -c=.1111111111111.. c=-32764 -c= 32764

c=1............1.1 -c=.111111111111.11 c=-32763 -c= 32763

c=1............11. -c=.111111111111.1. c=-32762 -c= 32762

[--snip--]

c=1111111111111..1 -c=.............111 c= -7 -c= 7

c=1111111111111.1. -c=.............11. c= -6 -c= 6

c=1111111111111.11 -c=.............1.1 c= -5 -c= 5

c=11111111111111.. -c=.............1.. c= -4 -c= 4

c=11111111111111.1 -c=..............11 c= -3 -c= 3

c=111111111111111. -c=..............1. c= -2 -c= 2

c=1111111111111111 -c=...............1 c= -1 -c= 1

Figure 1.1-A: With two’s complement there is one nonzero value that is its own negative.

In two’s complement zero is not the only number that is equal to its negative. The value with just

the highest bit set (the most negative value) also has this property. Figure 1.1-A (the output of [FXT:

bits/gotcha-demo.cc]) shows the situation for words of 16 bits. This is why innocent looking code like

the following can simply fail:

if ( x<0 ) x = -x;

// assume x positive here (WRONG!)

1.1.5 Another pitfall (shifts in the C-language)

A shift by more than BITS_PER_LONG−1 is undeﬁned by the C-standard. Therefore the following function

can fail if k is zero:

1 inline ulong first_comb(ulong k)

2 // Return the first combination of (i.e. smallest word with) k bits,

3 // i.e. 00..001111..1 (k low bits set)

4 {

5 ulong t = ~0UL >> ( BITS_PER_LONG - k );

6 return t;

7 }

Compilers usually emit just a shift instruction which on certain CPUs does not give zero if the shift is

equal to or greater than BITS_PER_LONG. This is why the line

if ( k==0 ) t = 0; // shift with BITS_PER_LONG is undefined

has to be inserted just before the return statement.

[fxtbook draft of 2009-April-28]

1.1: Trivia 7

1.1.9 Integer versus ﬂoat multiplication

The ﬂoating point multiplier gives the highest bits of the product. Integer multiplication gives the result

modulo 2

where b is the number of bits of the integer type used. As an example we square the number

1010101 using a 32-bit integer type and ﬂoating point types with 24-bit and 53-bit mantissa:

a = 111111111

a*a = 12345678987654321 // true result

a*a = 1653732529 // result with 32-bit integer multiplication

(a*a)%(2**32) = 1653732529 // ... which is modulo (2**bits_per_int)

a*a = 1.2345679481405440e+16 // result with float multiplication (24 bit mantissa)

a*a = 1.2345678987654320e+16 // result with float multiplication (53 bit mantissa)

1.1.10 Double precision ﬂoat to signed integer conversion

Conversion of double precision ﬂoats that have a 53-bit mantissa to signed integers via [12, p.52-53]

1 #define DOUBLE2INT(i, d) { double t = ((d) + 6755399441055744.0); i = *((int *)(&t)); }

2 double x = 123.0;

3 int i;

4 DOUBLE2INT(i, x);

can be a faster alternative to

1 double x = 123.0;

2 int i = x;

The constant used is 6755399441055744 = 2

+ 2

. The method is machine dependent as it relies on the

binary representation of the ﬂoating point mantissa. Here it is assumed that, the ﬂoating point number

has a 53-bit mantissa with the most signiﬁcant bit (that is always one with normalized numbers) omitted,

and that the address of the number points to the mantissa.

1.1.11 Optimization considerations

Never assume that some code is the ‘fastest possible’. There is always another trick that can still improve

performance. Many factors can have an inﬂuence on performance, like the 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 variables without using a temporary is pretty much out of fashion today:

// a=0, b=0 a=0, b=1 a=1, b=0 a=1, b=1

a ^= b; // 0 0 1 1 1 0 0 1

b ^= a; // 0 0 1 0 1 1 0 1

a ^= b; // 0 0 1 0 0 1 1 1

equivalent to:

tmp = a; a = b; b = tmp;

However, under some conditions (like extreme register pressure) it may be the way to go.

The only way to ﬁnd out which version of a function is faster is to actually do proﬁling (timing). The

performance does depend on the stream of instructions before the machine code, assuming that all of

these low-level functions get inlined. Studying the generated CPU instructions helps to understand what

happens, but can never replace proﬁling.

The code surrounding a function can have a massive impact on performance. This means that benchmarks

for just the isolated routine can at best give a rough indication. Proﬁle your application and also test

whether the second best (when isolated) routine is the fastest.

Never ever delete the unoptimized version of some code fragment when introducing a streamlined one.

Keep the original in the source. If something nasty happens (think of low level software failures when

porting to a diﬀerent platform), you will be very grateful for the chance to temporarily resort to the slow

but correct version.

[fxtbook draft of 2009-April-28]

8 Chapter 1: Bit wizardry

Study the optimization recommendations for your CPU (like [12] for the AMD64, see also [130]). You

can also learn a lot from the documentation for other architectures.

Proper documentation is an absolute must for optimized code. Always assume that nobody will under-

stand the code without comments. You may not be able to understand uncommented code written by

yourself after enough time has passed.

1.2 Operations on individual bits

1.2.1 Testing, setting, and deleting bits

The following functions should be self-explanatory. Following the spirit of the C language there is no check

whether the indices used are out of bounds. That is, if any index is greater or equal to BITS_PER_LONG,

the result is undeﬁned [FXT: bits/bittest.h]:

1 inline ulong test_bit(ulong a, ulong i)

2 // Return zero if bit[i] is zero,

3 // else return one-bit word with bit[i] set.

4 {

5 return (a & (1UL << i));

6 }

The following version returns either zero or one:

1 static inline bool test_bit01(ulong a, ulong i)

2 // Return whether bit[i] is set.

3 {

4 return ( 0 != test_bit(a, i) );

5 }

Functions for setting, clearing, and changing a bit are:

1 inline ulong set_bit(ulong a, ulong i)

2 // Return a with bit[i] set.

3 {

4 return (a | (1UL << i));

5 }

1 inline ulong delete_bit(ulong a, ulong i)

2 // Return a with bit[i] cleared.

3 {

4 return (a & ~(1UL << i));

5 }

1 inline ulong change_bit(ulong a, ulong i)

2 // Return a with bit[i] changed.

3 {

4 return (a ^ (1UL << i));

5 }

1.2.2 Copying a bit

To copy a bit from one position to another, we generate a one if the bits at the two positions diﬀer. Then

an XOR changes the target bit if needed [FXT: bits/bitcopy.h]:

1 inline ulong copy_bit(ulong a, ulong isrc, ulong idst)

2 // Copy bit at [isrc] to position [idst].

3 // Return the modified word.

4 {

5 ulong x = ((a>>isrc) ^ (a>>idst)) & 1; // one if bits differ

6 a ^= (x<<idst); // change if bits differ

7 }

The situation is more tricky if the bit positions are given as (one bit) masks:

1 inline ulong mask_copy_bit(ulong a, ulong msrc, ulong mdst)

2 // Copy bit according at src-mask (msrc)

3 // to the bit according to the dest-mask (mdst).

[fxtbook draft of 2009-April-28]

剩余995页未读，继续阅读

imA

粉丝: 273
资源: 48

程序员实用算法手册：从低级到高级

Matters Computational

计算问题：思想，算法，源代码Matters Computational: Ideas, Algorithms, Source Code

Matters Computational ideas, algorithms, source code

Matters Computational-ideas, algorithms, source code

《Matters Computational》：算法与源代码探索

吉他谱_Nothing Else Matters - Metallica.pdf

matters

Pseudo-Mask Matters in Weakly-Supervised Semantic.pdf

writhing matters

time-matters

最新资源