Bits, Bytes and Integers - Part 1
Everything is bits
Each bit is 0 or 1
By encoding/interpreting sets of bits in various ways
- Computers determine what to do (instructions)
- … and represent and manipulate numbers, sets, strings, etc…
Why bits? Electronic Implementation
- Easy to store with bistable elements
- Reliably transmitted on noisy and inaccurate wires
Encoding Byte Values
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
Boolean Algebra
And
A&B = 1 when both A=1 and B=1
Or
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
Example: Representing & Manipulating Sets
Representation
- Width w bit vector represents subsets of {0, …, w–1}
- a j = 1 if j ∈ A
-
& Intersection 01000001 { 0, 6 }
-
| Union 01111101 { 0, 2, 3, 4, 5, 6 }
-
^ Symmetric difference 00111100 { 2, 3, 4, 5 }
-
~ Complement 10101010 { 1, 3, 5, 7 }
Shift Operations
- Left Shift: x << y
- Shift bit-vector x left y positions
– Throw away extra bits on left
Fill with 0 ’s on rightShift bit-vector x left y positions
- Shift bit-vector x left y positions
- Right Shift: x >> y
- Shift bit-vector x right y positions
- Logical shift Fill with 0 ’s on left
- Arithmetic shift Replicate most significant bit on left
近期评论