tailieunhanh - Algorithms and Data Structures in C part 2

The one’s complement of a number, A, denoted by shown that To see this note that , is defined asFrom Eq. it can be and This yields Inserting Eq. into Eq. yields | which can be written as where is defined as the unary complement The one s complement of a number A denoted by is defined asFrom Eq. it can be shown that To see this note that and This yields Inserting Eq. into Eq. yields which gives By noting one obtains which is -A. So whether A is positive or negative the two s complement of A is equivalent to -A. Note that in this case it is a simpler way to generate the representation of -1. Otherwise you would have to note that Similarly However it is useful to know the representation in terms of the weighted bits. For instance -5 can be generated from the representation of -1 by eliminating the contribution of 4 in -1 Similarly -21 can be realized from -5 by eliminating the positive contribution of 16 from its representation. The operations can be done in hex as well as binary. For 8-bit 2 s complement one has with all the operations performed in hex. After a little familiarity hex numbers are generally easier to manipulate. To take the one s complement one handles each hex digit at a time. If w is a hex digit then the 1 s complement of w is given as The range of numbers in an n-bit 2 s complement notation is The range is not symmetric but the number zero is uniquely represented. The representation in 2 s complement arithmetic is similar to an odometer in a car. If the car odometer is reading zero and the car is driven one mile in reverse -1 then the odometer reads 999999. This is illustrated in Table . Table 2 s Complement Odometer Analogy 8-Bit 2 s Complement Binary Value Odometer 11111110 -2 999998 11111111 -1 999999 00000000 0 000000 00000001 00000010 1 000001 2 000002 Typically 2 s complement representations are used in the C programming language with the following declarations char 8 bits short 16 bits int 16 32 or 64 bits long 32 bits The number of bits for each type can be compiler dependent. An 8-bit example of the three basic integer representations is shown in Table . Table 8-Bit .