CSCI-UA.201-11.pdf

Bits, bytes and ints 2 Bits At the lowest level of abstraction, each code is actually a sequence of BITS Computers are just binary machines If we were in EE course, we could talk about low (0) and high(~3.5 to 5 V) voltages but we need to abstract them as 0 and...

Bits, bytes and ints 2 Bits At the lowest level of abstraction, each code is actually a sequence of BITS Computers are just binary machines If we were in EE course, we could talk about low (0) and high(~3.5 to 5 V) voltages but we need to abstract them as 0 and 1 3 Bits Voltage vs time graph of the binary number…… 1 2 3 4 5 6 7 8 4 Ideal vs Realistic Sine Wave 1 2 3 4 5 6 7 8 4 Everything is a bit Everything on a computer is encoded as sets of bits: ○ programs: all instructions of a program stored on disk and running are represented using binary sequences ○ data: the data that programs are manipulating are represented using binary sequences (numbers, strings, characters, images, audio,...) Why bits? Why binary system and not base 3, or base 4, or base 10? ○ Electronic Implementation ○ Easy to store with bi-stable elements ○ Reliably transmitted on noisy and inaccurate wires 6  Remember that… to calculate the numeric value of a ordinary (base 10, i.e., decimal) number, the right most digit is multiplied by 10! = 1, the next digit to the left by 10" = 1, the next digit by 10# = 100 , etc. E.g. 7895 = 7 ∗ 10$ + 8 ∗ 10% + 9 ∗ 10& + 5 ∗ 10' The same idea for the binary numbers: 11001 = 1 ∗ 2! + 1 ∗ 2" + 0 ∗ 2# + 0 ∗ 2$ + 1 ∗ 2% = 25 The problem is, decimal numbers are convenient but how to represent them by using electrical signals? Meanwhile, binary numbers are long… When we write a binary number we precede it with 0b 7 A bit vector What is 100010011111010101011111011110112 It is a bit vector. In order to know what it represents we need to know the type of the information that it is storing and the encoding that is used. The actual answer is going to be different if this is an int, a float a char or a program instruction. The bit vector itself does not have any meaning associated with it. 8 Intro to Hexadecimal Base 16 We need 16 symbols, 0..9 + A,B,C,D,E,F Shorthand notation for binary (easier to write one symbol than four) used by humans Write FA1D37B16 in C as ○ 0xFA1D37B ○ 0xfa1d37b When we write a hexadecimal number we precede it with 0x. 0X1234 = 1 ∗ 16$ + 2 ∗ 16# + 3 ∗ 16" + 4 ∗ 16! 9 Advantage of Hexadecimal You convert a base-16 to/from binary, one hexadecimal digit (4 bits) at a time. 1011000100101111 = 1011 0001 0010 1111 = B 1 2 F = 0xB12F 10 Bytes 1 byte = 8 bits Range of representable values: binary: 000000002 to 111111112 decimal: 010 to 25510 hexadecimal: 0016 to FF16 11  Data Sizes Confusion due to binary and decimal uses of Kilo-, Mega-, Giga- prefixes. In this course, we will be using them in binary sense. 12 Conversions Binary to decimal is straightforward. Remember slide 7. For binary numbers with n digits 𝑑&'$ … 𝑑" 𝑑# 𝑑$ 𝑑% , the decimal number is equal to the sum of binary digits times their power of 2. Decimal to binary? Divide the number by 2. Get the integer quotient for the next iteration. Get the remainder for the binary digit. Repeat the steps until the quotient is equal to 0. e.g. 13!" = 1101# Divide by 2 Quotient Remainder Bit no 13/2 6 1 0 6/2 3 0 1 3/2 1 1 2 1/2 0 1 3 13 Conversions Decimal to hex? e.g. 7562!" = 1D8A!$ ○ Divide the number by 16. ○ Get the integer quotient for the next iteration. ○ Get the remainder for the hex digit. ○ Repeat the steps until the quotient is equal to 0. Divide by 16 Quotient Remainder Remainder Digit no (decimal) (hex) 7562/16 472 10 A 0 472/16 29 8 8 1 29/16 1 13 D 2 1/16 0 1 1 3 14 Conversions This time, hex to decimal? e.g. 1D8A!$ = 7562!" Multiply each digit of the hex number with its corresponding power of 16 and sum (1D8A)₁₆ = (1 × 16³) + (13 × 16²) + (8 × 16¹) + (10 × 16⁰) = (7562)₁₀ 15 Conversions Binary to hex? Hex to binary? e.g. 11001101# = CD!$ ○ Convert every 4 binary digits to hex digit or vice versa: ○ 11001101 ○ = 1100 1101 ○ =CD ○ = CD 16 Quickcheck 17$% = xxxx# 157$% = xxxx# 245$% = xxxx# 10010# = xxxx$% 1100010110# = xxxx$% 100100111011# = xxxx$4 3𝐴9$4 = xxxx# Quickcheck Convert the following numbers to the other two representations Binary: 101101010, 10001110010, 10101011010001, 100001 Decimal: 255, 64, 100, 1025 Hexadecimal: 0xab, 0x123, 0xff, 0xf0 19 Practice 20 Practice write this code and enter jB4K Find the ASCII decimal codes of j, B, 4, K convert them to hex and now compare what you see 21 Practice 22 Playing with bits 24 Boolean Algebra Truth Tables Developed by George Boole in 19th century for logical operations. Claude E. Shannon adapted this concept to electrical switches and relays; this eventually lead to our computers "speaking" binary. AND OR & 0 1 | 0 1 0 0 0 0 0 1 1 0 1 1 1 1 NOT (complement) XOR ~ ^ 0 1 0 1 0 0 1 1 0 1 1 0 25 LOGIC CIRCUITS A Logic Gates is an electronic circuit which performs the particular logic operation. They are the building blocks of the digital electronics circuits. They are built up by various integrated circuits for input and output. OR GATE Has two or more than two inputs and one output signal. It is called an OR gate because the output signal will be high only if any or all input signals are high. OR GATE SWITCHING CIRCUIT EXAMPLE The switching circuit of the gate operation: AND GATE Has two or more input signals same as that of the OR, and the output is single. The gate has a high output only when all the input signals are high otherwise the output signal is low. AND GATE SWITCHING CIRCUIT EXAMPLE The switching circuit of the gate operation: NOT GATE Single input single output NOT GATE SWITCHING CIRCUIT EXAMPLE EXOR GATE EXOR gate is used extensively in digital data processing circuits and is known as Exclusive-OR-gate. The EXOR gate has a high output only when an odd number of inputs are high. For the two input EXOR gates, the output will be high when the set of input is either 01 or 10. EXOR GATE SWITCHING CIRCUIT EXAMPLE Representational Differences Bit-vector operations using Boolean operators in C Example: ~ 0110 = 1001 1010 & 0110 = 0010 1110 | 1000 = 1110 0110 ^ 1010 = 1100 These operators in C are called bitwise operators Bitwise operators (&, |, ~, ^) ARE NOT logical operators (&&, ||, !) 36 Bitwise Shift Operators The bitwise shift operators move the bit values of a binary object. The left operand specifies the value to be shifted. The right operand specifies the number of positions that the bits in the value are to be shifted. Left Shift: x > y Shift bit-vector x left by y Shift bit-vector x right by y positions positions Throw away extra bits on left Throw away extra bits on right Fill with 0’s on right Logical shift: fill with 0’s on left Arithmetic shift: replicate most significant bit on left 37 Arithmetic vs Logical Shift Operators Left Logical Shift — Each bit is shifted towards left, MSB is discarded and LSB becomes 0 Left Arithmetic Shift — Each bit is shifted towards left, MSB is discarded and LSB becomes 0, hence similar to logical shift Right Logical Shift — Each bit is shifted towards right, LSB is discarded and MSB becomes 0 Right Arithmetic Shift — Each bit is shifted towards right, LSB is discarded and MSB becomes 1 right arithmetic shift: keep sign (0 or 1) at left Left Shift: x > y Shift bit-vector x left by y Shift bit-vector x right by y positions positions Throw away extra bits on left Throw away extra bits on right Fill with 0’s on right Logical shift: fill with 0’s on left Arithmetic shift: replicate most 38 significant bit on left Left Logical Shift MSB LSB 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 39 Right Logical Shift MSB LSB 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 40 Left Arithmetic Shift MSB LSB 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 41 Right Arithmetic Shift MSB LSB 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 42 Bit-vector operations using shift operators Example 1: x is 01100010 (logical) x >> 2 is 00011000 (arithmetic) x >> 2 is 00011000 Example 2: x is 10100010 (logical) x >> 2 is 00101000 (arithmetic) x >> 2 is 11101000 Warning: shifting the a value by a negative number or by a number greater than the number of bytes in the given type is undefined in C. 43 Where to use this knowledge??? Modern computing has extracted the complexities away This is okay for most uses where your code is executed on powerful computers, but you’ll run into major problems while working on limited resource devices Understanding bitwise operators will bring you a step closer to optimization Where to use this knowledge??? Examples of uses of bitwise operations: encryption compression graphics communications over ports/sockets embedded systems programming and finite state machines. Where to use this knowledge??? The bitwise operations are found to be much faster and are sometimes used to improve the efficiency of a program. E.g.: To check if a number is even or odd. HOW? Swapping values of variables without a temp We normally need a temp storage for swapping values of two variables Using the bitwise exclusive or operator we can actually do this using only the storage of the two bit-vectors. HOW, ANY IDEA?? Try it for 17 and 178. 47 Integer Encoding 49 Encoding of Integers - Unsigned Assume we have a short - 16 bits, then if all these bits are 1s, we have the value of??? 2"% + 2"& + 2"$ + ⋯ + 2! = 65535 50 Encoding of Integers – Signed – 2’s complement Example: assume w = 6, what is the value of the following bit vectors interpreted as unsigned and as signed? 011010 100110 51 Encoding of Integers Unsigned: Two's Complement (Signed): Example: C short is 2 bytes long Sign bit - for 2's complement notation it is the most significant bit (leftmost) 0 indicates non-negative number 1 indicates negative number ToDo: try these formulas for w=5 just for practice. What is the integer encoded by 01011, 10010 using both unsigned and two's complement encodings? 52 Numerical Ranges Unsigned: Two's Complement: Umin = 0 Tmin = -2w-1 Umax = 2w - 1 Tmax = 2w-1 - 1 Assume w = 5: Assume w = 5: smallest unsigned: smallest 2's comp: 000002= 010 100002 = -1610 largest unsigned: largest 2's comp: 111112 = 3110 011112 = 1510 53 Umax, Tmin, Tmax for standard word sizes Notice: In C: the range of 2's complement values To access the values of is not symmetric largest/smallest values use #include |Tmin| = |Tmax|+1 The constants are named ○ UINT_MAX for a given value of w ○ INT_MAX ○ INT_MIN Umax = 2 * Tmax + 1 (these numbers are system specific) 54 Comparison of Unsigned and Two's Comp. Equivalence: Same encodings for nonnegative values +/- 16 (in general 2^w) for negative 2's comp and positive unsigned Uniqueness: Every bit pattern represents unique integer value Each representable integer has unique bit encoding 55  Conversion Between Signed and Unsigned Values -not always a good idea 56 Signed and Unsigned in C Constants By default, signed integers Unsigned with “U” as suffix: 0U, 4294967259U Casting Explicit casting between signed & unsigned ○ int tx, ty; ○ unsigned ux, uy; ○ tx = (int) ux; ○ uy = (unsigned) ty; Implicit casting also occurs via assignments and function calls ○ tx = ux; ○ uy = ty; 57 Casting Surprises If there is a mix of unsigned and signed in single expression, signed values implicitly cast to unsigned, including expressions with logical comparison operators , ==, =. What will the following code print? -1 < 0 is true -1 < 0u is false see casting_surprises.c 58 Expanding, truncating 60 Sign Extension TASK: Given a w-bit signed integer X, convert it to (w+k)-bit integer X' with the same value. Solution: make k copies of the sign bit X = xw-1 xw-2...x1x0 X' = xw-1...xw-1xw-1 xw-2...x1x0 ← k times → 61 Sign Extension C automatically performs sign extension when converting from "smaller" to "larger" data type. 62 Truncating Example: from int to short (i.e. from 32-bit to 16-bit) High-order bits are truncated Value is altered and must be reinterpreted This (non-intuitive) behavior can lead to buggy code! Example: int i = 1572539; short si = (short) i; printf(" i = %i\nsi = %i\n\n ", i, si ); prints i = 1572539 si = -325 see truncated.c 63  Arithmetic Operations: Negation, Addition, Multiplication, (Multiplication using Shifting) 64 Negation Task: given a bit-vector X compute -X Solution: -X = ~X + 1 (negating a value can be done by computing its complement and adding 1) Example: X = 0110012 = 2510 ~X = 1001102 = -2610 ~X+1 = 1001112 = -2510 Notice that for any signed integer X, we have ~X + X = 111...112 = -110 65 Addition for unsigned numbers Standard addition function ignores carry bits and implements modular arithmetic: To try: UAdd(u , v) = (u + v) mod 2w Show the results of adding the following unsigned bit vectors. 100102 = 1810 Assume w = 5. + 110112 = 2710 1011012 = 4510 111112 + 111112 001012 + 100102 011012 = 1310 = 4510 % 25 101012 + 011112 66 Addition of signed numbers True sum requires w+1 bits, addition ignores the carry bit. If TAddw(u,v) >= 2w–1, then sum becomes negative (positive overflow) If TAddw(u,v) < –2w–1, then sum becomes positive (negative overflow) To try: 100102 = -1410 Show the results of adding the + 110112 = -510 following signed bit vectors. 1011012 = -1910 Assume w = 5. 111112 + 111112 011012 = 1310 001012 + 100102 67 101012 + 011112 Multiplication Task: Computing Exact Product of w-bit numbers x, y (either signed or unsigned) Ranges of results: Unsigned multiplication requires up to 2w bits to store result: 0 ≤ x * y ≤ (2w – 1)2 = 22w – 2w+1 + 1 Two’s complement smallest possible value requires up to 2w-1 bits: x * y ≥ (–2w–1)*(2w–1–1)= –22w–2 + 2w–1 Two’s complement largest possible value requires up to 2w bits (in one case): x * y ≤ (–2w–1)2 = 22w–2 Maintaining exact results would need to keep expanding word size with each product computed. 68 Multiplication signed/unsigned Multiplication results for signed and unsigned bit vectors ignore the high order bits. To try: - Show the results of multiplying the following signed bit vectors. Assume w = 5. 111112 * 111112 001012 * 100102 101012 * 011112 69 Multiplication by power of 2 (left shift) Multiplication by a power of two is equivalent to the left shift operation: u * 2k is the same as u