低级算法与计算思维：源代码解析

需积分: 10 183 浏览量更新于2024-08-01 收藏 5.1MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"Matters Computational ideas, algorithms, source code" 本书《Matters Computational ideas, algorithms, source code》是一本面向计算主义者的书籍，无论是职业程序员还是对计算方法感兴趣的读者都能从中受益。作者假设读者能够理解书中的源代码，这部分代码被视为文本的一部分。书中主要使用C++编程语言来编写低级别的算法，但只使用了C++超越基本特性的一小部分，如类和模板。在技术细节可能掩盖基本思想的地方，作者使用伪代码或对于算术算法使用GP语言。书中包含大量实例计算，通常与算法一起给出，并且这些通常是通过提及的演示程序完成的。书中大多数列表和图形都是用这些程序生成的。一个贯穿全书的主题是实现的实际效率，讨论了多种优化技术，并指出了许多给定实现的实际性能。随书附带的软件FXT和hfloat库是为符合POSIX标准的平台编写的，如Linux和BSD操作系统。它们遵循GNU General Public License（GPL）版本3或更高版本的许可。每一章尽可能自成一体，并在需要时提供相关材料的引用。标记` z '的段落可以作为首次阅读时跳过的内容，这些通常包含深入探讨或更高级的材料。书中的参考文献条目后都列出了引用页码。对于可免费下载的论文，给出了相应的URL。电子版图书可以免费匿名下载，与印刷版完全相同。书末附录A提供了关于许可的更多信息。考虑到涵盖的大量材料，书中难免存在错误，作者欢迎纠正和改进建议，首选的沟通方式是电子邮件。在线提供了错误列表。许多人为此书的改进做出了贡献，作者特别感谢Igal Aharonovich、Marcus Blackburn、Nathan Bullock等多位人士的帮助。特别感谢Edith Parzefall和Michael Somos独立校对了全文，Neil Sloane创建了Online Encyclopedia of Integer Sequences。书中的章节内容涵盖了基础算法，例如位操作、位旋转、Gray码、二进制项链、扫描、位序列等。这些章节详细介绍了各种算法和技巧，旨在让读者深入理解计算的本质并提高编程效率。

资源详情

资源推荐

4 Chapter 1: Bit wizardry

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 default

behavior of many commonly used 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 static 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.

1.1.6 Shortcuts

Test whether at least one of a and b equals zero with

if ( !(a && b) )

This works for both signed and unsigned integers. Check whether both are zero with

if ( (a|b)==0 )

This obviously generalizes for several variables as

if ( (a|b|c|..|z)==0 )

Test whether exactly one of two variables is zero using

[fxtbook draft of 2010-June-01]

1.1: Trivia 5

if ( (!a) ^ (!b) )

1.1.7 Average without overﬂow

A routine for the computation of the average (x+y)/2 of two arguments x and y is [FXT: bits/average.h]

1 static inline ulong average(ulong x, ulong y)

2 // Return floor( (x+y)/2 )

3 // Use: x+y == ((x&y)<<1) + (x^y)

4 // that is: sum == carries + sum_without_carries

5 {

6 return (x & y) + ((x ^ y) >> 1);

7 }

The function gives the correct value even if (x + y) does not ﬁt into a machine word. If it is known

that x ≥ y, then we can use the simpler statement return y+(x-y)/2. The following version rounds to

inﬁnity:

1 static inline ulong ceil_average(ulong x, ulong y)

2 // Use: x+y == ((x|y)<<1) - (x^y)

3 // ceil_average(x,y) == average(x,y) + ((x^y)&1))

4 {

5 return (x | y) - ((x ^ y) >> 1);

6 }

1.1.8 Toggling between values

To toggle an integer x between two values a and b, use:

pre-calculate: t = a ^ b;

toggle: x ^= t; // a <--> b

The equivalent trick for ﬂoating-point types is

pre-calculate: t = a + b;

toggle: x = t - x;

Here an overﬂow could occur with a and b in the allowed range if both are close to overﬂow.

1.1.9 Next or previous even or odd value

Compute the next or previous even or odd value via [FXT: bits/evenodd.h]:

1 static inline ulong next_even(ulong x) { return x+2-(x&1); }

2 static inline ulong prev_even(ulong x) { return x-2+(x&1); }

4 static inline ulong next_odd(ulong x) { return x+1+(x&1); }

5 static inline ulong prev_odd(ulong x) { return x-1-(x&1); }

The following functions return the unmodiﬁed argument if it has the required property, else the nearest

such value:

1 static inline ulong next0_even(ulong x) { return x+(x&1); }

2 static inline ulong prev0_even(ulong x) { return x-(x&1); }

4 static inline ulong next0_odd(ulong x) { return x+1-(x&1); }

5 static inline ulong prev0_odd(ulong x) { return x-1+(x&1); }

Pedro Gimeno gives [priv.comm.] the following optimized versions:

1 static inline ulong next_even(ulong x) { return (x|1)+1; }

2 static inline ulong prev_even(ulong x) { return (x-1)&~1; }

4 static inline ulong next_odd(ulong x) { return (x+1)|1; }

5 static inline ulong prev_odd(ulong x) { return (x&~1)-1; }

1 static inline ulong next0_even(ulong x) { return (x+1)&~1; }

2 static inline ulong prev0_even(ulong x) { return x&~1; }

4 static inline ulong next0_odd(ulong x) { return x|1; }

5 static inline ulong prev0_odd(ulong x) { return (x-1)|1; }

[fxtbook draft of 2010-June-01]

6 Chapter 1: Bit wizardry

1.1.10 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 111111111 using a 32-bit integer type and ﬂoating-point types with 24-bit and 53-bit mantissa

(signiﬁcand):

a = 111111111 // assignment

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.11 Double precision ﬂoat to signed integer conversion

Conversion of double precision ﬂoats that have a 53-bit mantissa to signed integers via [11, 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.12 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. Note that if

both operands are identical (memory locations) then the result is zero.

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

performance does depend on the sequence of instructions surrounding 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 benchmarking. This means that benchmarks for just the isolated

routine can at best give a rough indication. Test your application using diﬀerent versions of the routine

in question.

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.

Study the optimization recommendations for your CPU (like [11] and [12] for the AMD64, see also [140]).

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

[fxtbook draft of 2010-June-01]

1.2: Operations on individual bits 7

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 than or equal to

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

1 static 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 static inline ulong set_bit(ulong a, ulong i)

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

3 {

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

5 }

1 static inline ulong clear_bit(ulong a, ulong i)

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

3 {

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

5 }

1 static 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 static 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 return a;

8 }

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

1 static 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).

4 // Both msrc and mdst must have exactly one bit set.

5 {

6 ulong x = mdst;

7 if ( msrc & a ) x = 0; // zero if source bit set

8 x ^= mdst; // ==mdst if source bit set, else zero

9 a &= ~mdst; // clear dest bit

[fxtbook draft of 2010-June-01]

8 Chapter 1: Bit wizardry

10 a |= x;

11 return a;

12 }

The compiler generates branch-free code as the conditional assignment is compiled to a cmov (conditional

move) assembler instruction. If one or both masks have several bits set, the routine will set all bits of

mdst if any of the bits in msrc is one, or else clear all bits of mdst.

1.2.3 Swapping two bits

A function to swap two bits of a word is [FXT: bits/bitswap.h]:

1 static inline ulong bit_swap(ulong a, ulong k1, ulong k2)

2 // Return a with bits at positions [k1] and [k2] swapped.

3 // k1==k2 is allowed (a is unchanged then)

4 {

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

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

7 a ^= (x<<k1); // change if bits differ

8 return a;

9 }

If it is known that the bits do have diﬀerent values, the following routine should be used:

1 static inline ulong bit_swap_01(ulong a, ulong k1, ulong k2)

2 // Return a with bits at positions [k1] and [k2] swapped.

3 // Bits must have different values (!)

4 // (i.e. one is zero, the other one)

5 // k1==k2 is allowed (a is unchanged then)

6 {

7 return a ^ ( (1UL<<k1) ^ (1UL<<k2) );

8 }

1.3 Operations on low bits or blocks of a word

The underlying idea of functions operating on the lowest set bit is that addition and subtraction of 1 always

changes a burst of bits at the lower end of the word. The functions are given in [FXT: bits/bitlow.h].

1.3.1 Isolating, setting, and deleting the lowest one

The lowest one (set bit) is isolated via

1 static inline ulong lowest_one(ulong x)

2 // Return word where only the lowest set bit in x is set.

3 // Return 0 if no bit is set.

4 {

5 return x & -x; // use: -x == ~x + 1

6 }

The lowest zero (unset bit) is isolated using the equivalent of lowest_one( ~x ):

1 static inline ulong lowest_zero(ulong x)

2 // Return word where only the lowest unset bit in x is set.

3 // Return 0 if all bits are set.

4 {

5 x = ~x;

6 return x & -x;

7 }

Alternatively, we can use either of

return (x ^ (x+1)) & ~x;

return ((x ^ (x+1)) >> 1 ) + 1;

[fxtbook draft of 2010-June-01]

剩余975页未读，继续阅读

wind.liao

粉丝: 81
资源: 24

低级算法与计算思维：源代码解析

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

Matters Computational-ideas, algorithms, source code

Matters Computational

Algorithms for programmers ideas and source code

Transparency,liquidity,and valuation:International evidence on when transparency matters most

School-Based Curriculum Development: Is It Coming Back into Fashion? [J]. Curriculum Matters

AttributeError: module 'torch.nn' has no attribute 'RelU'

KerasClassifier is deprecated, use Sci-Keras

番茄助手头文件注释说明

What is the principle of least privilege? Why does this principle matter?

写一个蓝色调好看的 Android登录xml

用python写一个tensor形式的以决定系数为指标的损失函数

Unable to connect to the database: security

查询不是IS，CS系的男生名单，要求名字中包含%且三个字，用SQL语言写出

itertools.product

帮我找一下可以写再javaweb毕设里的英文参考文献

写一个简短的摇滚乐歌词

glcm python

最新资源