Computer Organization:
A Programmer's Perspective
Bits, Bytes, Nibbles,
Words and Strings
Gal A. Kaminka
[email protected]
Topics
Why bits? Why 0/1?
Basic terms: Bits, Bytes, Nibbles, Words
Representing information as bits
Binary/Hexadecimal
Byte representations
numbers
characters and strings
Instructions
Bit-level manipulations
Boolean algebra
Expressing in C
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 2
Why Computers Use Base 2?
Base 10 Number Representation:
Culturally natural, easily “human-readable”
Even carries through in scientific notation
1.5213 X 104
Implementing electronically is difficult
Hard to store
ENIAC (first electronic computer) used 10 vacuum tubes / digit
Hard to transmit
Need high precision to encode 10 signal levels on single wire
Messy to implement digital logic functions
Addition, multiplication, etc.
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 3
Binary (base 2) Representations
Base 2 Number Representation
Represent 1521310 as 111011011011012
Represent 1.5213 X 104 as 1.11011011011012 X 213
Easy electronic Implementation
Easy to store with bistable elements
Reliably transmitted on noisy and inaccurate wires
Straightforward implementation of arithmetic functions
0 1 0
3.3V
2.8V
0.5V
0.0V
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 4
Terms
Bit: Single binary digit, 0 or 1
Byte: 8 bits.
Smallest unit of memory used in modern computers
Nibble (English: small bite): 4 bits
2 nibbles = 1 byte
Used to be useful, isn't anymore
Word: 8-64 bits (1 to 8 bytes)
Depends on machine!
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 5
Byte-Oriented Memory Organization
Programs Refer to Virtual Addresses
Conceptually very large array of bytes
Actually implemented with hierarchy of different memory types
SRAM, DRAM, disk
In Unix and Windows NT, address space private to “process”
Program can clobber its own data, but not that of others
You will see this again, in much more detail
Compiler + Run-Time System Control Allocation
Where different program objects should be stored
Multiple mechanisms: static, stack, and heap
In any case, all allocation within single virtual address space
You will see this again, in much more detail
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 6
Encoding Byte Values
Byte = 8 bits al y
x ci m ar
n
Binary 000000002 to 111111112 He De Bi
0 0 0000
Decimal: 010 to 25510 1 1 0001
2 2 0010
Hexadecimal 0016 to FF16 3 3 0011
Base 16 number representation 4 4 0100
5 5 0101
Use characters ‘0’ to ‘9’ and ‘A’ to ‘F’ 6 6 0110
Write FA1D37B16 in C as 0xFA1D37B 7 7 0111
8 8 1000
» Or 0xfa1d37b 9 9 1001
Octal: 08 to 3778 A 10 1010
B 11 1011
Base 8 C 12 1100
D 13 1101
Not often used E 14 1110
Written in C as '0256' (0 is zero) F 15 1111
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 7
Machines have Words
Nominal size of integer-valued data
Including addresses
Most current machines are 32 bits (4 bytes)
Limits addresses to 4GB
Becoming too small for memory-intensive applications
High-end systems are 64 bits (8 bytes)
Potentially address ≈ 1.8 X 1019 bytes
Low-end (and old machines) use 8- or 16-bit words
Machines support multiple data formats
Fractions or multiples of word size
Always integral number of bytes
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 8
Word-Oriented Memory
Organization 32-bit 64-bit
Bytes Addr.
Words Words
0000
Addr
0001
Addresses Specify Byte =
??
0000 0002
Locations Addr
= 0003
Address of first byte in word ??
0000 0004
Addr
Addresses of successive = 0005
words differ by 4 (32-bit) or ??
0004 0006
8 (64-bit) 0007
0008
Addr
= 0009
??
0008 0010
Addr
= 0011
??
0008 0012
Addr
= 0013
??
0012 0014
0015
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 9
Data Representations
Sizes of C Objects (in Bytes)
C Data Type: Compaq Alpha Typical 32-bit Intel IA32
int 4 4 4
long int 8 4 4
char 1 1 1
short 2 2 2
float 4 4 4
double 8 8 8
long double 8 8 10/12
char*/void * 8 4 4
Or any other pointer
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 10
Byte Ordering
How should bytes within multi-byte word be ordered in
memory?
Conventions
Sun’s, Mac’s are “Big Endian” machines
Least significant byte has highest address
Alphas, PC’s are “Little Endian” machines
Least significant byte has lowest address
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 11
Byte Ordering Example
Big Endian
Least significant byte has highest address
Little Endian
Least significant byte has lowest address
Example
Variable x has 4-byte representation 0x01234567
Address given by &x is 0x100
Big Endian 0x100 0x101 0x102 0x103
01 23 45 67
Little Endian 0x100 0x101 0x102 0x103
67 45 23 01
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 12
Reading Byte-Reversed Listings
Disassembly
Text representation of binary machine code
Generated by program that reads the machine code
Example Fragment
Address Instruction Code Assembly Rendition
8048365: 5b pop %ebx
8048366: 81 c3 ab 12 00 00 add $0x12ab,%ebx
804836c: 83 bb 28 00 00 00 00 cmpl $0x0,0x28(%ebx)
Deciphering Numbers
Value: 0x12ab
Pad to 4 bytes: 0x000012ab
Split into bytes: 00 00 12 ab
Reverse: ab 12 00 00
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 13
Examining Data Representations
Code to Print Byte Representation of Data
Casting pointer to unsigned char * creates byte array
typedef unsigned char *pointer;
void show_bytes(pointer start, int len)
{
int i;
for (i = 0; i < len; i++)
printf("0x%p\t0x%.2x\n",
start+i, start[i]);
printf("\n");
}
Printf directives:
%p: Print pointer
%x: Print Hexadecimal
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 14
show_bytes Execution Example
int a = 15213;
printf("int a = 15213;\n");
show_bytes((pointer) &a, sizeof(int));
Result (Linux):
int a = 15213;
0x11ffffcb8 0x6d
0x11ffffcb9 0x3b
0x11ffffcba 0x00
0x11ffffcbb 0x00
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 15
Representing Integers
Decimal: 15213
int A = 15213;
int B = -15213; Binary: 0011 1011 0110 1101
long int C = 15213; Hex: 3 B 6 D
Alpha A Sun A ia32 C Alpha C Sun C
6D 00 6D 6D 00
3B 00 3B 3B 00
00 3B 00 00 3B
00 6D 00 00 6D
00
Alpha B Sun B 00
00
93 FF
00
C4 FF
FF C4
FF 93 Two’s complement representation
(Covered next lecture)
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 16
Representing Pointers
int B = -15213;
int *P = &B;
Alpha P
Alpha Address
A0
Hex: ... 0 1 F F F F F C A 0
FC
Binary: 0000 0001 1111 1111 1111 1111 1111 1100 1010 0000 FF
FF
Sun Address 01
00
Hex: E F F F F B 2 C
Sun P Binary: 1110 1111 1111 1111 1111 1011 0010 1100 00
00
EF
FF Linux Address
Hex: B F F F F 8 D 4 Linux P
FB
2C Binary: 1011 1111 1111 1111 1111 1000 1101 0100
D4
F8
Different compilers & machines assign different locations to objects FF
BF
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 17
Representing Floats
Float F = 15213.0;
Alpha F Sun F
00 46
B4 6D
6D B4
46 00
IEEE Single Precision Floating Point Representation
Hex: 4 6 6 D B 4 0 0
Binary: 0100 0110 0110 1101 1011 0100 0000 0000
15213: 1110 1101 1011 01
Not same as integer representation, but consistent across machines
Can see some relation to integer representation, but not obvious
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 18
Representing Floats
Float F = 15213.0;
Alpha F Sun F
00 46
B4 6D
6D B4
46 00
IEEE Single Precision Floating Point Representation
Hex: 4 6 6 D B 4 0 0
Binary: 0100 0110 0110 1101 1011 0100 0000 0000
15213: 1110 1101 1011 01
Not same as integer representation, but consistent across machines
Can see some relation to integer representation, but not obvious
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 19
Representing Strings (in C)
Represented by array of 1-byte characters
Each character encoded in ASCII format char S[6] = "15213";
Standard 7-bit encoding of character set
Alpha S Sun S
Character “0” has code 0x30
31 31
» Digit i has code 0x30+i
35 35
Other encodings exist (e.g., for Hebrew) 32 32
String are null-terminated 31 31
Final character = 0x00 33 33
Array length must be strlen()+1. 00 00
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 20
Representing Strings (in C)
Represented by array of 1-byte characters
Each character encoded in ASCII format char S[6] = "15213";
Standard 7-bit encoding of character set
Alpha S Sun S
Character “0” has code 0x30
31 31
» Digit i has code 0x30+i
35 35
Other encodings exist (e.g., for Hebrew) 32 32
String are null-terminated 31 31
Final character = 0x00 33 33
Array length must be strlen()+1. 00 00
Compatibility
Byte ordering not an issue (data is given byte-by-byte anyways)
Text files generally platform independent
But: Different conventions of line termination character(s)!
But: Different default encodings (depend on locale)
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 21
Representing Strings (Cont'd)
Strings in Pascal (a.k.a P-Strings)
Represented by array of characters+1
First cell holds length, no need for null-termination p-String
Length known in O(1)!
5
Think about strcat(), strlen(), strcpy(), ... 31
Size of string limited by size of array cell value 35
32
31
33
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 22
Representing Strings (Cont'd)
Strings in Pascal (a.k.a P-Strings)
Represented by array of characters+1
First cell holds length, no need for null-termination p-String
Length known in O(1)!
5
Think about strcat(), strlen(), strcpy(), ... 31
Size of string limited by size of array cell value 35
32
31
Advanced character encodings (wide char) 33
Many int'l encodings use all 8 bits (ISO-8859-x)
UTF-16 uses 2-4 bytes (16-32 bits)
UTF-32 uses four bytes (32 bits) (see unicode on web)
c-strings and p-strings used, but:
big/little endian now matters (each cell multiple bytes)
No longer built-in to language, instead platform/library specific
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 23
Machine-Level Code Representation
Encode Program as Sequence of Instructions
Each simple operation
Arithmetic operation
Read or write memory
Conditional branch
Instructions encoded as bytes
Alpha’s, Sun’s, Mac’s use 4 byte instructions
» Reduced Instruction Set Computer (RISC)
PC’s use variable length instructions
» Complex Instruction Set Computer (CISC)
Different instruction types and encodings for different machines
Most code not binary compatible
Programs are Byte Sequences Too!
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 24
Representing Instructions
int sum(int x, int y)
{ Alpha sum Sun sum PC sum
return x+y;
00 81 55
}
00 C3 89
30 E0 E5
For this example, Alpha & Sun use
two 4-byte instructions 42 08 8B
Use differing numbers of instructions 01 90 45
in other cases 80 02 0C
PC uses 7 instructions with lengths FA 00 03
1, 2, and 3 bytes 6B 09 45
Same for NT and for Linux 08
NT / Linux not fully binary
89
compatible
EC
5D
C3
Different machines use totally different instructions and encodings
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 25
Math behind binary representation
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 26
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
Exclusive-Or (Xor)
~A = 1 when A=0
A^B = 1 when either A=1 or B=1,
but not both
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 27
Application of Boolean Algebra
Applied to Digital Systems by Claude Shannon
1937 MIT Master’s Thesis
Reason about networks of relay switches
Encode closed switch as 1, open switch as 0
A&~B
Connection when
A ~B
A&~B | ~A&B
~A B
~A&B = A^B
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 28
Integer Algebra
Integer Arithmetic
<Z, +, *, –, 0, 1>〉 forms a “ring”
Addition is “sum” operation
Multiplication is “product” operation
– is additive inverse
0 is identity for sum
1 is identity for product
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 29
Boolean Algebra
Boolean Algebra
<{0,1}, |, &, ~, 0, 1> forms a “Boolean algebra”
Or is “sum” operation
And is “product” operation
~ is “complement” operation (not additive inverse)
0 is identity for sum
1 is identity for product
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 30
Boolean Algebra ≈ Integer Ring
Commutativity
A|B = B|A A+B = B+A
A&B = B&A A*B = B*A
Associativity
(A | B) | C = A | (B | C) (A + B) + C = A + (B + C)
(A & B) & C = A & (B & C) (A * B) * C = A * (B * C)
Product distributes over sum
A & (B | C) = (A & B) | (A & C) A * (B + C) = A * B + B * C
Sum and product identities
A|0 = A A+0 = A
A&1 = A A*1 =A
Zero is product annihilator
A&0 = 0 A*0 = 0
Cancellation of negation
~ (~ A) = A – (– A) = A
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 31
Boolean Algebra ≠ Integer Ring
Boolean: Sum distributes over product
A | (B & C) = (A | B) & (A | C) A + (B * C) ≠ (A + B) * (B + C)
Boolean: Idempotency
A|A = A A +A≠A
“A is true” or “A is true” = “A is true”
A&A = A A *A≠A
Boolean: Absorption
A | (A & B) = A A + (A * B) ≠ A
“A is true” or “A is true and B is true” = “A is true”
A & (A | B) = A A * (A + B) ≠ A
Boolean: Laws of Complements
A | ~A = 1 A + –A ≠ 1
“A is true” or “A is false”
Ring: Every element has additive inverse
A | ~A ≠ 0 A + –A = 0
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 32
Properties of & and ^
Boolean Ring
<{0,1}, ^, &, Ι, 0, 1>
Identical to integers mod 2
Ι is identity operation: Ι (A) = A
Properties of Boolean Ring
Commutative sum A^B = B^A
Commutative product A&B = B&A
Associative sum (A ^ B) ^ C = A ^ (B ^ C)
Associative product (A & B) & C = A & (B & C)
Prod. over sum A & (B ^ C) = (A & B) ^ (B & C)
0 is sum identity A^0 = A
1 is prod. identity A&1 = A
0 is product annihilator A&0=0
Additive inverse A^A = 0
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 33
Relations Between Operations
DeMorgan’s Laws
Express & in terms of |, and vice-versa
A & B = ~(~A | ~B)
» A and B are true if and only if neither A nor B is false
A | B = ~(~A & ~B)
» A or B are true if and only if A and B are not both false
Exclusive-Or using Inclusive Or
A ^ B = (~A & B) | (A & ~B)
» Exactly one of A and B is true
A ^ B = (A | B) & ~(A & B)
» Either A is true, or B is true, but not both
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 34
General Boolean Algebras
Operate on Bit Vectors
Operations applied bitwise
01101001 01101001 01101001
& 01010101 | 01010101 ^ 01010101 ~ 01010101
01000001 01111101 00111100 10101010
01000001 01111101 00111100 10101010
All of the Properties of Boolean Algebra Apply
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 35
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
01010101 { 0, 2, 4, 6 }
76543210
Operations
& 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 }
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 36
Bit-Level Operations in C
Operations &, |, ~, ^ available in C
Apply to any “integral” data type
long, int, short, char
View arguments as bit vectors
Arguments applied bit-wise
Examples (Char data type)
~0x41 --> 0xBE
~010000012 --> 101111102
~0x00 --> 0xFF
~000000002 --> 111111112
0x69 & 0x55 --> 0x41
011010012 & 010101012 --> 010000012
0x69 | 0x55 --> 0x7D
011010012 | 010101012 --> 011111012
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 37
Contrast: Logic Operations in C
Contrast to Logical Operators
&&, ||, !
View 0 as “False”
Anything nonzero as “True”
Always return 0 or 1
Early termination
Examples (char data type)
!0x41 --> 0x00
!0x00 --> 0x01
!!0x41 --> 0x01
0x69 && 0x55 --> 0x01
0x69 || 0x55 --> 0x01
p && *p (avoids null pointer access)
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 38
Shift Operations
Left Shift: x << y Argument x 01100010
Shift bit-vector x left y positions << 3 00010000
Throw away extra bits on left
Fill with 0’s on right Log. >> 2 00011000
Arith. >> 2 00011000
Right Shift: x >> y
Shift bit-vector x right y positions
Throw away extra bits on right Argument x 10100010
<< 3 00010000
Logical shift Log. >> 2 00101000
Fill with 0’s on left
Arithmetic shift Arith. >> 2 11101000
Replicate most significant bit on right
Useful with two’s complement integer representation
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 39
Cool Stuff with Xor
void funny(int *x, int *y)
Bitwise Xor is form {
of addition *x = *x ^ *y; /* #1 */
With extra property *y = *x ^ *y; /* #2 */
*x = *x ^ *y; /* #3 */
that every value is }
its own additive
inverse
A^A=0
*x *y
Begin A B
1 A^B B
2 A^B (A^B)^B = A
3 (A^B)^A = B A
End B A
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 40
Main Points
It’s All About Bits & Bytes
Numbers
Programs
Text
Different Machines Follow Different Conventions
Word size
Byte ordering
Representations
Boolean Algebra is Mathematical Basis
Basic form encodes “false” as 0, “true” as 1
General form like bit-level operations in C
Good for representing & manipulating sets
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 41
?שאלות
Computer Organization:
A Programmer's Perspective Based on class notes by Bryant and O'Hallaron 42
