Bits, Bytes, And Integers
Download Bits, Bytes, And Integers
Preview text
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
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
Categories
You my also like
Group Theory Notes
826.1 KB27.7K12.8KIrreversible Bit Erasures in Binary Multipliers
334 KB44.5K10.2KPreventing bit stuffing in CAN
272.2 KB60.6K18.2KBasic Assembly Language I (Data Size)
214.9 KB42.9K14.6KChapter 2 Numeric Representation
116.4 KB30.2K12.7KnVidia Hardware Documentation
1.5 MB6.8K3.4KBits, bytes, binary numbers, and the representation of
109.6 KB94.3K46.2KDEFLATE Compressed Data Format Specification version 1
55.3 KB6K1.8KMemory Addressing, Binary, and Hexadecimal Review
140.4 KB30.2K13.6K