位操作与计算：低级算法探析

需积分: 6 152 浏览量更新于2024-08-02 收藏 5.02MB PDF 举报

"Matters Computational: ideas, algorithms, source code" 本书《Matters Computational》由Jörg Arndt编写，是一本关于计算理论和技术的工作进展文档。作者在书中分享了他在算法和源代码方面的深入见解。书中强调这是一部未完成的作品，并提示读者查阅文档开头的“重要备注”。当前版本为2009年8月5日的初稿，但作者提供了最新的版本和配套软件的在线链接。书的内容涵盖了低级算法，特别是位操作相关的技巧。位操作是计算机科学的基础，对于优化程序性能和理解计算机底层工作原理至关重要。书中详细介绍了以下几个方面的内容： 1. 位琐事：涵盖了一些基础的位操作知识。 2. 单位位操作：讨论如何对单个二进制位进行操作。 3. 低位或字块操作：处理二进制数的最低位或一组位。 4. 近转换位的位提取：找到接近翻转状态的位或位块。 5. 单个置位位的索引：计算一个设置为1的位的索引位置。 6. 高位或字块操作：处理二进制数的最高位或一组位。 7. 基于2的对数相关函数：与二进制对数有关的操作。 8. 计算位和字块的数量：统计二进制数中1或0的个数。 9. 位集表示法：将词（word）用作位集合的用途。 10. i-th置位位的索引：快速查找第i个设置为1的位。 11. 分支避免技术：提高代码效率，减少分支指令的使用。 12. 位旋转：二进制数的位向左或向右移动。 13. 二进制项链：一种用于表示和操作二进制序列的概念。 14. 位反转：如何倒序二进制数的位。 15. 位压缩：将多个位打包到一个较小的位空间中。 16. 灰度码和奇偶校验：一种位编码方式，用于无中断的顺序变化。 17. 位序列：特定的位模式和它们的性质。 18. 灰度码的幂：灰度码的乘幂运算。 19. 可逆的单词变换：允许位操作后恢复原位序列的方法。这些章节详细探讨了位操作的各种方面，不仅包括基本操作，还包括更高级的主题，如位压缩、位序列和可逆变换。对于那些想要深入理解计算机内部运作机制，或者希望优化低级代码性能的开发者来说，这本书是一个宝贵的资源。

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 it is better to avoid casting pointers to integer types.

1.1.3 Shifts and division

With two’s complement arithmetic division and multiplication by a power of 2 is a 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

Therefore 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-August-05]

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 [152], see

also [321].

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 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.

[fxtbook draft of 2009-August-05]

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

111111111 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 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 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-August-05]

8 Chapter 1: Bit wizardry

Study the optimization recommendations for your CPU (like [12] for the AMD64, see also [131]). 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 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:

[fxtbook draft of 2009-August-05]

剩余1003页未读，继续阅读

lyfeng301

粉丝: 0
资源: 4

位操作与计算：低级算法探析

Matters Computational(pdf)

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

Matters Computational ideas, algorithms, source code

Matters Computational-ideas, algorithms, source code

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

Why Explainability in Models Matters: 4 Methods to Achieve Interpretable AI

藏区特产销售平台--论文.zip

caribou-devel-0.4.21-1.el7.x86_64.rpm.zip

avahi-qt3-0.6.31-20.el7.x86_64.rpm.zip

ant-javamail-1.9.4-2.el7.noarch.rpm.zip

最新资源