preface

C language is now one of the most important and the most popular programming language, relative to other programming language, C language more underlying structural design, to provide more precise control of hardware, but also require users to pay more attention to a pointer and a byte level programming, based on the C language as the carrier, byte level information storage and related features, Discusses the encoding and associated pitfalls of strings, integers, and floating point numbers. Please advise if you are not right

1. Bit + context

It is well known that modern computers store and process information in binary signals, 0s and 1s. Computers store information in 0 – and 1-bit strings, and the only way to tell one from the other is based on the context in which the 0 – and 1-bit strings are parsed.

First, let’s think about the question: Given a string 0110 0001, what does it mean?

Without any context, we intuitively guess that this is a number and convert binary to hexadecimal to 0x61 and decimal to 97. If it is further assumed that the computer is reading string 0110 0001 in the context of parsing ASCII, string 0110 0001 is interpreted by the computer as the character A in ASCII. However, if the context in which the computer reads the string 0110 0001 is an unsigned char mask, then 0110 0001 does not mean anything. If the context in which the computer reads the string is a reference to an 8-bit pointer, then 0110 0001 means address 97.

A single bit string does not make sense. Information is carried in a bit + context, and the same bit string is interpreted as different information in different contexts.

2. Represent a string

Strings in C are encoded as null-terminated character arrays, and each character of the string is usually encoded in an ASCII character code.

//"123" is stored as 0x31 0x32 0x33 0x00
// Binary: 0011 0001 0011 0010 0011 0011 0000 0000
char *str1 = "123";
//" ABC "is stored as 0x61 0x62 0x63 0x00
// Binary: 0110 0001 0110 0010 0110 0011 0000 0000
char *str2 = "abc";
Copy the code

Strings are stored in a way that is independent of byte order and word length, so they are most portable.

Three, represents the integer

C language number coding system is an approximate representation of the real world number system, there are some differences in some characteristics.

For example, C uses a char variable to store 256 integers [-128,127], using the following expression:

/ * 1 * /
char x = - 128.;
char y = -x;// In the real world, y should be 128, but in C, y is -128!

/ * 2 * /
char x = 100,y=30;
char sum = x+y;// In the real world, y should be 130, but in C, y
是- 126.!Copy the code

If you do not understand the C language number coding system, it is easy to cause the program appears extremely hidden bugs. Below we focus on how the C language represents integers and floating point numbers.

(1) unsigned

1. An overview of the

The C language provides two encoding methods for integers: unsigned and signed.

First, let’s look at the decimal representation of positive integers and think about how we might interpret the number 123. It should be 123=3∗100+2∗101+1∗102123=3*10^0+2*10^1+1*10^2123=3∗100+2∗101+1∗102.

Analogies to the unsigned 8bit binary 0110 0001 have:

If you use 16bit space to store 97, what should the bit string be?

Considering the bit string of WWW bit, it is formulated as (Formula 1) :

Xwx_ {w}xw is the value of the WWW bit.

In the basic C data type, the storage size is usually 1 byte, 2 bytes, 4 bytes, and 8 bytes, and the corresponding WWW value is 8, 16, 32, and 64

2. Value range

An interesting phenomenon is that if you use 8bit for unsigned storage, the maximum value is XMax8=28−1=255XMax_8=2^8-1=255XMax8=28−1=255.

In fact, in the given 8 bits, the binary representation ranges from 0000 0000 to 1111 1111. The maximum value is that the bit of all the storage space is 1, that is, 1111 1111. The value is 1 0000 0000-1, and it is easy to know from formula 1 that 1 0000 0000 is 2^8.

You would be wise to guess that a given bit string of WWW length stores unsigned integers, with the maximum value being an odd number, of XMaxw=2w−1XMax_w=2^w-1XMaxw=2w−1.

The minimum unsigned value is 0 for all bits, so no matter how many bits in the bit string, XMinw=0XMin_w=0XMinw=0

C Data type	The minimum value	The maximum
unsigned char(8bit)	0	255
unsigned short(16bit)	0	65535
unsigned int(32bit)	0	4294967295

Other unsigned data types can be determined by the number of bits in the storage space.

(2) there is a sign

1. An overview of the

Compared with the intuitiveness of unsigned numbers, signed numbers are more obscure. Because signed numbers introduce complement, subtraction, asymmetry.

1.1 the original code

First of all, let’s look at negative decimal integers like -123, let’s just put a minus sign in front of 123 to indicate a negative integer, can we also have the computer write -0110, 0001 in binary form for -97?

Remember, our computer can only store 0’s and 1’s, it can’t store minus signs, so it’s not a simple way to do it, you have to find a way to encode binary to represent negative integers.

It should be easy to know, so I’ll use the highest bit of the 0,1bit string as the sign bit (this code is called the source code), where the highest bit is 0 for a positive number and the highest bit is 1 for a negative number. Let’s look at this code:

This form of coding was intuitive, but it was soon discovered that the source code was not suitable for computer coding.

Why is that? Because the computer CPU is not that intelligent, to simplify the complexity of hardware design, CPU only adder, no subtracter! This means that the CPU converts all subtraction into addition. We try to calculate 2-1: \ using source code encoding in CPU Angle

1. Code 2 as0000, 0010,;
2. And since we can only add, we’re going to2-1As a2 + (1),- 1Encoded as1000, 0001,;
3. operation2 + (1)The result is:1000, 0011,, namely – 3! Clearly wrong.

Therefore, using the source code as a signed number coding is not conducive to CPU simplification and hardware design.

A second encoding, inverse coding, is proposed, which converts the weight of the highest bit in unsigned encoding from 2W −12^{w-1} 2W −1 to − (2W −1−1) – (2^{w-1}-1) − (2W −1−1). In char type, WWW has a value of 8, – 1-1 – (2 w) = – 127 – (2 ^ {1} w – 1) = 127 – (2 w – 1-1) = – 127. Such as:

This coding method has a characteristic: between positive and negative numbers on the bitlevel is exactly the opposite

At the same time, the inverse code can just make up for the lack of the original code in the CPU operation, still take 2-1 as an example:

1. Code 2 as0000, 0010,;
2. And since we can only add, we’re going to2-1As a2 + (1), encode 1 as0000, 0001,, then take the reverse- 1Encoded as1111, 1110,;
3. operation2 + (1)The result is:0000 0010+ 1111 1110 =1 0000 0000;
4. According to the inverse code calculation rules, if there is a carry, it is sent back to the lowest order to add (circular carry), the final result is0000, 0001,, that is, to1.

Through the operation of the inverse code, it can be concluded that the CPU can quickly calculate the final subtraction result with the simple bit level inverse and shift operation under the condition of only the adder. This coding rule can be adapted to the underlying hardware design, but you should soon realize that the inverse value has a strange property. There are two ways to encode the number 0, namely:

That is, the inverse code interprets the code 00000000 as +0, and the code 11111111 as -0. There is a difference between this interpretation and real events, since the real world does not distinguish between positive and negative zeros.

In order to improve this shortcoming, modern computers use a form of coding called complement, which reduces the negative space by one more, making the code 1111 1111 ~ 1000 0000 drop from -0 ~ -127 to -1 ~ -128.

Modern computers basically use complement code as a signed integer code

1.2 complement

In the complementary coding method, the weight of the highest bit is regarded as − 2W −1-2^{W-1}− 2W −1. Note: The weight of the highest bit of the inverse code is − (2W −1−1) – (2^{W-1}-1) − (2W −1−1).

Drawing on formula 1 of unsigned number, it is easy to derive the coding location of the signed number of WWW bits (Formula 2) :

Note: The complement coding method also has a characteristic that the bitlevel between positive and negative numbers is exactly inverted by 1. For example, the encoding of 1 and -1 is as follows:

Let’s look at the calculation of 2-1:

1. Code 2 as0000, 0010,;
2. And since we can only add, we’re going to2-1As a2 + (1), encode 1 as0000, 0001,, then take the negative plus 1- 1Encoded as1111, 1111,;
3. operation2 + (1)The result is:00000010 + 1111 1111 =1 00000001;
4. According to the rule of complement calculation, the calculation result is pair
   $2^{w}$If I take the modulus, the final result is zero0000, 0001,, that is, to1.

2. Conversion of unsigned and signed numbers

As described in this article, information = bit + context, there is no difference in the storage of signed and unsigned numbers in C language, and there is only the absence of parsing of the same bit string.

Formula 1 compares with Formula 2:

It can be seen from the formula that if the unsigned number turns to the signed number:

If the unsigned number turns to the signed number, then:

For example, in a cast:

/* Unsigned to signed */
unsigned char x = 255;
/* The maximum bit weight is changed from 128 to -128 (a change of -256), that is, 255-256=-1*/
char y = (char)x; //y=-1;
Copy the code

/* Sign to unsigned */
char x = - 128.;
/* The maximum bit weight is changed from -128 to 128 (+256), i.e. -128+256=128*/
unsigned char y = (unsigned char)x;//x=128
Copy the code

If you are interested, you can convert an 8bit unsigned 100 to a signed number, and an 8bit signed 100 to an unsigned number.

3. Value range

An interesting fact is that asymmetry occurs when you use complement to represent signed numbers. What is the asymmetry?

We compare positive and negative binary strings of signed numbers to indicate ranges:

Positive: 0000 0001 to 0111 1111

Negative number: 1000 0000 ~ 1111 1111

See? Without looking at the highest digit, a positive number indicates that the range starts at 000 0001, while a negative number starts at 000 0000. The range of negative numbers is one greater than the range of positive numbers, and that’s the asymmetry of the range.

So the 8bit signed binary range is:

Positive: 0000 0001 to 0111 1111 => 1 to 127

Negative number: 1000 0000 ~ 1111 1111 => -128 ~ -1

0:00 00 0000

In summary, the 8bit signed value ranges from -128 to 127. The value ranges of 2, 4 and 8 bytes signed number are not listed here. The principle is the same, please deduce it by yourself.

At the end of this section, a little thought question:

char x = - 128.;
What is the value of y?
char y = -x;
Copy the code

Four, represents the floating point number

Compared to the integer encoding, the encoding of floating point numbers is more sophisticated, computer encoding of floating point numbers usually use IEEE754 standard. Consider the fixed-point representation of decimal numbers, where the negative exponential power of 10 represents the decimal place, for example, 12.341012.34_{10}12.3410:

Correspondingly, the same fixed-point notation can be used for binary, such as 1.5101.5_{10}1.510 in binary:

This representation is intuitive, but it requires considerable storage space to represent very large numbers or numbers very close to 0, such as the numbers 21002^{100}2100 or 2−1002^{-100}2−100, which requires at least 101 bits of memory space. Thus, similar to decimal notation, scientific enumeration is introduced to represent a number in the form x∗2yx*2^yx∗2y. In this notation, only the exact storage of XXX and yyy is needed to represent a number, even if the number is very large or very small. X =2x=2x=2, y=100, y=100, y=100, y=100, y=100, y=100, y=100.

Formally, the IEEE754 standard denotes a number by the form (−1)s∗M∗2E(-1)^s*M*2^E(−1)s∗M∗2E, where:

• s: sign bit, indicating positive and negative values. Refer to the original code representation of the above integer
• M: Mantissa digit, which represents a binary decimal, that is, in the above
  $y$Through thefracField calculation
• E: Order code point, which indicates the weight of binary decimal, that is, in the above
  $x$Through theexpField calculation

32-bit floating point number: sign bit 1 bit,expField 8 bits,fracField 2364-bit floating point numbers represent: sign bit 1 bit,expField 11 bits,fracField 52

The IEEE754 standard represents a number through the form (−1)s∗M∗2E(-1)^s*M*2^E(−1)s∗M∗2E, so s,M,E must be calculated in order to parse or encode a floating point number. According to different values of exp in the storage, different encoding cases are distinguished for floating point numbers, and each encoding case corresponds to different calculation methods:

By determining the total number of bits in the EXP and FRAc fields, you determine how many different numbers can be represented by a floating point number. However, you can determine the representation range and intensity of floating point numbers by adjusting the number of bits occupied by the EXP and FRAC fields. When the EXP field has more bits, the floating-point representation is wider, and when the FRAc field has more bits, the floating-point representation is denser

(1) Normalized value

When exp is not all zeros or all ones, the float is normalized. For k bit EXP and n bit FRAc, the calculation is as follows:

• Calculate E:

1. Introduce the offset valueB:

The value of 32-bit floating point B is 127, and the value of 64-bit floating point B is 1023

2. throughexpMinus the biasBIt means signedE:

For example, if the exp stored in the memory is 128, E= EXP −B=128−127=1E= EXP -B=128-127=1E= EXP −B=128−127=1

Note that the signed E is represented in the offset form rather than the complement form, mainly because the offset form means that the sizes of different floating point numbers can be directly compared by binary bits without any complement calculation.

The value ranges from -126 to 127 for a 32-bit floating point number, and from -1022 to 1023 for a 64-bit floating point number

• Calculation M:

1. willfracFields are treated as decimal places, for examplefracValues for1101, is regarded as the decimal place0.1101
2. By decimal placefracThe field is computed by adding 1M:

For example, if frac is 1101, M is 1.1101

This gives you an extra bit of precision because the first bit is treated as a 1, regardless of the fraC value

(2) nonnormalized values

When the value of exp is all zeros, the floating point number is a decormalized value, which is an encoding for a value that is zero or very close to zero. For k bit EXP and n bit FRAc, the calculation is as follows:

• Calculate E:

1. Introduce the offset valueB:

The value B of a 32-bit floating point number is -126, and the value B of a 64-bit floating point number is -1022

2. through1Minus the biasBIt means signedE:

For example, in a 32-bit floating point number, if the exp stored in the memory is 0, E=1−B=1−127=−126E=1-B=1-127=-126E=1−B=1−127=−126

Note that the method of calculating E from B is: E=1−BE = 1-be =1−B, in order to connect with the normalization, because the normalization means that the value closest to 0 is also 1−B1-B1−B

• Calculation M:

1. willfracFields are treated as decimal places, for examplefracValues for1101, is regarded as the decimal place0.1101
2. Directly through the decimal placefracField to drawM:

For example, if frac is 1101, M is 0.1101

In the normalized representation, M=frac+1M =frac+1M =frac+1. In this representation, no matter what frac value is, the first bit is treated as 1, which means that M cannot be 0 (note that FRAc is unsigned and cannot be negative). Therefore, in order to make M 0, in the nonnormalized representation, M: M=fracM =fracM = FRAc directly from the decimal frac field

Due to the exquisite design of the calculation of the nonnormalized E and M, the transition between the nonnormalized and normalized representations can be smooth, that is, the maximum nonnormalized number is only a little smaller than the normalized number

(3) specific values

Finally, when all 1s are exp, when all 0s are frac, it means infinity. When frac is not all 0s, it means NaN, which means not a number.

(4) Overflow

Floating-point numbers represent a numeric value in the form of X ∗2yx*2^ YX ∗2y, but not any numeric value can be represented in the form of x∗ 2YX *2^ YX ∗2y determined in finite space. Therefore, overflow cannot be avoided if floating point numbers are represented by IEEE 754 encoding. It is discussed in two cases:

• when
  $x$, which is discussed aboveMCannot accurately represent values:

For example, 0.1 in decimal is converted to 0.00011001100[1100] in binary. The value in brackets is an infinite loop value and cannot be expressed in the limited storage space. As a result, overflow occurs, and floating point numbers can only be approximated.

– When yyy, E discussed above, cannot represent too large or too small a value:

For example, the decimal 3.4∗10393.4*10^{39}3.4∗1039 cannot be represented as a 32-bit floating point number.

conclusion

This article focuses on the representation of computer information, and discusses the encoding of strings, unsigned integers, signed integers, and floating point numbers at the byte level.

1. Each character of the string is usually stored in ASCII encoding, which has good portability
2. Unsigned integer uses unsigned encoding, the encoding form is simple and intuitive, different storage space size determines the value range of unsigned integer
3. Signed integers are stored in complement, and this encoding form is solved+ 0and0At the same time, it meets the design requirements of hardware adder
4. Floating-point number usageIEEE 754Standard encoding, that is, the adoption of
   $x*2^y$The form represents a number and only needs to be stored
   $x$and
   $y$It can represent floating point numbers, reducing the storage space requirements for maximum numbers or values near zero, but also making the storage form more complex.

2. Why do computers use complement?