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-
defined’. 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 undefined 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]