Bits, Bytes, and Integers¶

约 419 个字预计阅读时间 2 分钟共被读过次

15-213/14-513/15-513: Introduction to Computer Systems
2^nd Lecture, Aug 29, 2024

1. Binary Representation¶

Key Concepts:¶

Binary (Base-2) System:
0 represents 0, 1 represents 1.
Each position corresponds to a power of 2 (e.g., 1011₂ = 1·2³ + 0·2² + 1·2¹ + 1·2⁰ = 11₁₀).

Examples:¶

Binary	Decimal Calculation	Decimal Value
`000`	`0·2² + 0·2¹ + 0·2⁰`	`0`
`001`	`0·2² + 0·2¹ + 1·2⁰`	`1`
`010`	`0·2² + 1·2¹ + 0·2⁰`	`2`
`011`	`0·2² + 1·2¹ + 1·2⁰`	`3`
`100`	`1·2² + 0·2¹ + 0·2⁰`	`4`

2. Hexadecimal & Octal¶

Hexadecimal (Base-16):¶

Digits: 0-9, A-F (e.g., 1A2B₁₆ = 1·16³ + 10·16² + 2·16¹ + 11·16⁰ = 6699₁₀).
C notation: 0xFA1D37B.

Octal (Base-8):¶

Less dense than hexadecimal.

3. Boolean Algebra & Bit-Level Operations¶

Operations in C:¶

Operator	Meaning	Example (Char)	Result
`&`	AND	`0x69 & 0x55` → `0x41`	`01000001`
`\|`	OR	`0x69 \| 0x55` → `0x7D`	`01111101`
`~`	NOT	`~0x41` → `0xBE`	`10111110`
`^`	XOR	`0x69 ^ 0x55` → `0x3C`	`00111100`

Logic vs. Bitwise Operations:¶

Logic Operators (&&, ||, !): Return 0 or 1.
Example: !0x41 → 0x00 (False), !!0x41 → 0x01 (True).

4. Shift Operations¶

Left Shift (`x << y`):¶

Fill right with 0s.
Example: 01100010 << 3 → 00010000.

Right Shift (`x >> y`):¶

Logical Shift: Fill left with 0s.
Example: 10100010 >> 2 → 00101000.
Arithmetic Shift: Replicate sign bit.
Example: 10100010 >> 2 → 11101000.

⚠️ Undefined Behavior: Shift amount < 0 or ≥ word size.

5. Integer Representation¶

Two’s Complement:¶

Encoding Negative Numbers:
-x = ~x + 1 (e.g., -5 in 4-bit: 0101 → 1010 + 1 = 1011).
Ranges:
Unsigned: 0 to 2^w - 1.
Signed (2’s complement): -2^(w-1) to 2^(w-1) - 1.

Example (16-bit):¶

Type	Decimal	Hex	Binary
UMax	65535	`FF FF`	`11111111 11111111`
TMax	32767	`7F FF`	`01111111 11111111`
TMin	-32768	`80 00`	`10000000 00000000`

6. Conversion & Casting¶

Sign Extension:¶

Replicate sign bit to expand width (e.g., 1010 → 11111010).

Truncation:¶

Drop higher-order bits (e.g., 0xFA1D37B truncated to 16 bits → 0xD37B).

⚠️ Casting Pitfalls:
- Mixing signed/unsigned in expressions → implicit casting to unsigned!

7. Addition & Multiplication¶

Unsigned Addition (`UAdd_w`):¶

Modular Arithmetic: UAdd_w(u, v) = (u + v) mod 2^w.

Two’s Complement Addition:¶

Same bit-level behavior as unsigned addition.

Multiplication:¶

Equivalent to (x * y) mod 2^w.
Shift-Multiply Trick: (x << 5) - (x << 3) → x * 24.

8. Byte Ordering¶

Endianness:¶

Big Endian: Most significant byte at lowest address.
Example: 0x01234567 → 01 23 45 67.
Little Endian: Least significant byte at lowest address.
Example: 0x01234567 → 67 45 23 01.

9. Practice Problems¶

Example 1:¶

Q: Convert FA1D37B₁₆ to binary.
A:
- F→1111, A→1010, 1→0001, D→1101, 3→0011, 7→0111, B→1011.
- Result: 1111 1010 0001 1101 0011 0111 1011.

Example 2:¶

Q: Compute 0x69 & 0x55 and interpret as a set intersection.
A:
- 0x69 = 01101001, 0x55 = 01010101.
- & → 01000001 = {0, 6}.

📘 Further Reading: Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition