Bits, Bytes, And Integers

BITS, BYTES, AND INTEGERS
COMPUTER ARCHITECTURE AND ORGANIZATION

Today: Bits, Bytes, and Integers
 Representing information as bits  Bit-level manipulations  Integers
 Representation: unsigned and signed  Conversion, casting  Expanding, truncating  Addition, negation, multiplication, shifting
 Making ints from bytes  Summary
2

Encoding Byte Values
 Byte = 8 bits
 Binary 000000002 to 111111112  Decimal: 010 to 25510  Hexadecimal 0016 to FF16
 Base 16 number representation  Use characters ‘0’ to ‘9’ and ‘A’ to ‘F’  Write FA1D37B16 in C as
 0xFA1D37B  0xfa1d37b

0 0 0000 1 1 0001 2 2 0010 3 3 0011 4 4 0100 5 5 0101 6 6 0110 7 7 0111 8 8 1000 9 9 1001 A 10 1010 B 11 1011 C 12 1100 D 13 1101 E 14 1110 F 15 1111

3

Boolean Algebra

 Developed by George Boole in 19th Century

 Algebraic representation of logic

 Encode “True” as 1 and “False” as 0

And

Or

 A&B = 1 when both A=1 and B=1  A|B = 1 when either A=1 or B=1

Not
 ~A = 1 when A=0

Exclusive-Or (Xor)
 A^B = 1 when either A=1 or B=1, but not both

4

General Boolean Algebras

 Operate on Bit Vectors
 Operations applied bitwise
01101001 01101001 01101001 & 01010101 | 01010101 ^ 01010101
0011000000000011 0011111111110011 0000111111110000

~ 01010101 1100110011001100

 All of the Properties of Boolean Algebra Apply

5

Bit-Level Operations in C
 Operations &, |, ~, ^ Available in C
 Apply to any “integral” data type
 long, int, short, char, unsigned
 View arguments as bit vectors  Arguments applied bit-wise
 Examples (Char data type [1 byte])  In gdb, p/t 0xE prints 1110
 ~0x41 → 0xBE  ~010000012 → 101111102
 ~0x00 → 0xFF  ~000000002 → 111111112
 0x69 & 0x55 → 0x41  011010012 & 010101012 → 010000012
 0x69 | 0x55 → 0x7D  011010012 | 010101012 → 011111012
6

Representing & Manipulating Sets

 Representation
 Width w bit vector represents subsets of {0, …, w–1}  aj = 1 if j ∈ A

 01101001

{ 0, 3, 5, 6 }

 76543210

 MSB Least significant bit (LSB)

 01010101

{ 0, 2, 4, 6 }

 76543210

 Operations

 & Intersection

01000001

 | Union

01111101

 ^ Symmetric difference 00111100

 ~ Complement

10101010

{ 0, 6 } { 0, 2, 3, 4, 5, 6 } { 2, 3, 4, 5 } { 1, 3, 5, 7 }

7

Contrast: Logic Operations in C
 Contrast to Logical Operators
 &&, ||, !
 View 0 as “False”  Anything nonzero as “True”  Always return 0 or 1  Short circuit
 Examples (char data type)
 !0x41 → 0x00  !0x00 → 0x01  !!0x41 → 0x01
 0x69 && 0x55 → 0x01  0x69 || 0x55 → 0x01
 p && *p (avoids null pointer access)
8

Shift Operations

 Left Shift: x << y
 Shift bit-vector x left y positions
 Throw away extra bits on left
 Fill with 0’s on right
 Right Shift: x >> y
 Shift bit-vector x right y positions
 Throw away extra bits on right
 Logical shift
 Fill with 0’s on left
 Arithmetic shift
 Replicate most significant bit on left
 Undefined Behavior
 Shift amount < 0 or ≥ word size

Argument x 01100010 << 3 00010000
Log. >> 2 00011000 Arith. >> 2 00011000
Argument x 10100010 << 3 00010000
Log. >> 2 00101000 Arith. >> 2 11101000

9

Today: Bits, Bytes, and Integers
 Representing information as bits  Bit-level manipulations  Integers
 Representation: unsigned and signed  Conversion, casting  Expanding, truncating  Addition, negation, multiplication, shifting
 Making ints from bytes  Summary
10