-
Notifications
You must be signed in to change notification settings - Fork 16
/
integers.theory.txt
79 lines (72 loc) · 6.45 KB
/
integers.theory.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
INTEGERS
REPRESENTATIONS ==> # - binary:
# - as is
# - most common
# - BCD (Binary-coded decimal):
# - make each byte === 1 digit, by padding 0s
# - pros: more human readable
# - cons: takes more space. Not efficient. Not often used.
# - "packed" version removes any nibble 0000
# - some x86 instructions are reserved to BCD: AAA, AAX, etc.
# - example for "1934":
# - Unpacked BCD : 00000001 00010001 00000011 00000100
# - Packed BCD : 0001 00010001 00110100
# - binary normal : 100 11010010
# - string of ASCII digits
VARIABLE LENGTH ==> #Can either:
# - be length-prefixed
# - use sentinel value (see doc for strings)
#Also available for floats
#Called "bigint" or "bignum"
#Variable-length quantity (VLQ):
# - use a repeating sentinel value:
# - MSB of each byte is 1 if there is a next byte
# - first byte is most significant
# - i.e. 128 bits per byte, encoding only unsigned integers
# - signed variants:
# - sign bit on first byte's second bit
# - sign bit on last byte's last bit ("zigzag encoding")
SIGNEDNESS ==> #Can be unsigned or signed, depending on whether it can be negative.
#Signedness can be represented using:
# - sign bit:
# - most significant bit is 0 for +, 1 for -
# - problem: discontinuity between 00000000 and 10000000
# - 1's complement:
# - like sign bit, but also bits are inverted if negative number
# - problems:
# - +0 and -0 have separate representations (00000000 et 11111111)
# - adding two opposite numbers result in -0 (11111111) not +0 (00000000)
# - 2's complement:
# - like 1's complement, but 1 is added to negative numbers
# - most commonly used
# - offset binary:
# - like 2's complement, but with most significant bit flipped
# - goal: 00000000 is minimum value, 11111111 is maximum
#
# +--------------+---------------+---------------+---------------+---------------+---------------+
# | NUMBER | UNSIGNEDNESS | SIGN BIT | 1's COMPLEMENT| 2's COMPLEMENT| OFFSET BINARY |
# +--------------+---------------+---------------+---------------+---------------+---------------+
# | 255 | 11111111 ff | | | | |
# | ... | ... | | | | |
# | 129 | 10000001 81 | | | | |
# | 128 | 10000000 80 | | | | |
# | 127 | 01111111 7f | 01111111 7f | 01111111 7f | 01111111 7f | 11111111 ff |
# | ... | ... | ... | ... | ... | ... |
# | 1 | 00000001 01 | 00000001 01 | 00000001 01 | 00000001 01 | 10000001 81 |
# | +0 | 00000000 00 | 00000000 00 | 00000000 00 | 00000000 00 | 10000000 80 |
# | -0 | | 10000000 80 | 11111111 ff | | |
# | -1 | | 10000001 81 | 11111110 fe | 11111111 ff | 01111111 7f |
# | -2 | | 10000010 82 | 11111101 fd | 11111110 fe | 01111110 7e |
# | ... | | ... | ... | ... | ... |
# | -127 | | 11111111 ff | 10000000 80 | 10000001 81 | 00000001 01 |
# | -128 | | | | 10000000 80 | 00000000 00 |
# +--------------+---------------+---------------+---------------+---------------+---------------+
MAX SIZE ==> #Often used:
# - 4 bits: semioctet, -8-7, 0-15
# - 8 bits: byte/char, -128-127, 0-255
# - 16 bits: short, -32768-32767, 0-65535
# - 32 bits: long, -2e9-2e9, 0-4e9
# - 64 bits: long long, quad, -9e18-9e18, 0-1e19
# - 128 bits: octaword, -1e38-1e38, 0-3e38