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. 1.18 it can beand This yields Inserting Eq. 1.24 into Eq. 1.22 yields
Nội dung trích xuất từ tài liệu:
Algorithms and Data Structures in C part 2which can be written aswhere is defined as the unary complement:The one’s complement of a number, A, denoted by , is defined asFrom Eq. 1.18 it can beshown thatTo see this note thatandThis yieldsInserting Eq. 1.24 into Eq. 1.22 yieldswhich givesBy notingone obtainswhich 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 youwould have to note thatSimilarlyHowever, 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 itsrepresentation.The operations can be done in hex as well as binary. For 8-bit 2’s complement one haswith all the operations performed in hex. After a little familiarity, hex numbers are generallyeasier to manipulate. To take the one’s complement one handles each hex digit at a time. If w is ahex digit then the 1’s complement of w, , is given asThe range of numbers in an n-bit 2’s complement notation isThe 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 carodometer is reading zero and the car is driven one mile in reverse (-1) then the odometer reads999999. This is illustrated in Table 1.2. Table1.22’sComplementOdometerAnalogy8‐Bit 2’sComplement Binary Value Odometer 11111110 ‐2 999998 11111111 ‐1 999999 00000000 0 000000 00000001 1 000001 00000010 2 000002Typically, 2’s complement representations are used in the C++ programming language with thefollowing declarations: •char(8bits) •short(16bits) •int(16,32,or64bits) •long(32bits)The number of bits for each type can be compiler dependent. An 8-bit example of the three basicinteger representations is shown in Table 1.3. Table1.38‐BitRepresentations8‐BitRepresentations 2’s Signed Complemen Magnitude Number Unsigned t ‐128 NR† NR 10000000 ‐127 NR 11111111 10000001 ‐2 NR 10000010 11111110 ‐1 NR 10000001 11111111 0 00000000 00000000 00000000 10000000 1 00000001 00000001 00000001 127 01111111 01111111 01111111 128 10000000 NR NR 255 11111111 NRNR † .Notrepresentablein8‐bitformat. Table1.4 Rangesfor 2’s Complement and 2’sComplement Unsigned Unsigned Notations# Bits 8 ‐128≤A≤127 0≤A≤255 16 ‐32768≤A≤32767 0≤A≤65535 32 ‐2147483648≤A≤2147483647 0≤A≤4294967295 n 0≤A≤2n ...