← Back to COMP1521 返回 COMP1521

Week 2 — Integers & Bitwise 第 2 周 — 整数与位运算

Binary/hex, two’s complement, masks, shifts, and overflow patterns 二进制/十六进制、补码、掩码、移位与溢出判定

🎯 Learning Objectives学习目标

🧩 Exam Alignment与考试练习的对应关系

🗂️ Week Position & Study Flow周次定位与学习流程

Week 2 bridges pure C fundamentals (Week 1) and the low-level data manipulation needed for later MIPS, floating-point, and memory manager labs. 第2周连接了第1周的C语言基础与后续MIPS、浮点与内存管理实验所需的底层数据操作能力。

Use the flow below to stay exam-ready while keeping practice synced with the tutorials and labs. 按照下列节奏推进，可在同步完成教程/实验的同时保持面向考试的准备状态。

Coverage Targets 覆盖目标

Aim for ≥4 conversion tasks (binary↔decimal↔hex), ≥3 mask manipulations, ≥2 overflow diagnoses, and ≥1 full lab function implementation each week. 每周至少完成4次进制转换（十进制/二进制/十六进制互换）、3次掩码操作、2次溢出判定、1个完整实验函数实现。

🧪 Tutorial & Lab Mapping教程与实验映射

Tutorial 02 Highlights Tutorial 02 重点

  • Paper drills on converting signed/unsigned numbers between bases; emphasise grouping bits for hex. 纸笔练习：有符号/无符号数的多进制转换，强调按4位分组快速得到十六进制。
  • Quick overflow judgment: identify when sign bits change unexpectedly. 溢出速判：识别符号位异常变化即溢出。
  • Mask reasoning puzzles: choose correct combination of shifts and AND/OR. 掩码推理题：选择正确的移位与与/或组合。

Lab 02 Programming Tasks Lab 02 编程任务

  • bit_masks.c: fill helper functions to test, set, clear bits; reuse in later labs. bit_masks.c：补全测试/置位/清零函数，为后续实验复用。
  • pack_colour.c: combine RGB components; practise field packing/unpacking. pack_colour.c：组合RGB颜色分量，练习字段打包/拆包。
  • bit_rotate.c (challenge): implement rotate-left/right via masks and shifts. bit_rotate.c（挑战）：通过掩码与移位实现循环左移/右移。

Complete official tests, then add custom inputs that hit corner cases (e.g., turning high bits on/off, rotating 0 or all-ones). 在完成官方测试后，再添加高位开关、旋转0或全1等边界输入自行验证。

📑 Exam Playbook & Templates考试模板与解题策略

Template 1 — Base Conversion Ladder 模板1 — 进制阶梯法

Draw a ladder: decimal ↔ binary ↔ hex. Convert through binary to avoid mistakes. 画出“十进制↔二进制↔十六进制”阶梯，始终通过二进制中转以减少错误。

Step 1: decimal → binary (divide-by-2 table) Step 2: group 4 bits → hex digits Step 3: for signed values, ensure MSB matches sign expectation

Template 2 — Two’s Complement Diagnostic 模板2 — 补码诊断

Checklist: same sign inputs? Does the sign of the result flip? If yes, overflow occurred. 检查表：输入是否同号？结果符号是否翻转？若是，则发生溢出。

Useful mnemonic: S + S = D where S is sign bit; if D ≠ S, overflow. 记忆提示：用符号位S表示输入；S+S得到输出符号D，若D≠S即溢出。

Template 3 — Field Extraction Engine 模板3 — 字段抽取流程

1) Shift target field down; 2) Apply mask (width bits of 1); 3) Optionally sign-extend if the field is signed. 1）右移到最低位；2）以字段宽度构建全1掩码；3）若字段有符号则做符号扩展。

uint32_t extract_signed(uint32_t x, int h, int l) { uint32_t width = h - l + 1; uint32_t raw = (x >> l) & ((1u << width) - 1); if (raw & (1u << (width - 1))) { // sign bit inside field uint32_t extend_mask = ~((1u << width) - 1); raw |= extend_mask; } return raw; }

Template 4 — Shift as Multiply/Divide 模板4 — 将移位视作乘除

Left shift by k ≈ multiply by 2^k (beware overflow). Logical right ≈ unsigned divide by 2^k; arithmetic right ≈ signed divide rounding toward -∞. 左移k位≈乘以2^k（注意溢出）；逻辑右移≈无符号除以2^k；算术右移≈向下取整的有符号除以2^k。

📚 Core Concepts核心概念

Number Bases & Ranges 进制与取值范围

8-bit unsigned: 0..255; 8-bit two’s complement: -128..127. Hex groups 4 bits per digit for readability. 8位无符号：0..255；8位补码：-128..127。十六进制每位代表4个二进制位，便于阅读。

37(10) = 0b0010_0101 = 0x25

Two’s Complement 二进制补码

Negate by invert bits + 1. Add/subtract works uniformly for signed and unsigned, but interpretation differs. 取负：按位取反再加1。加/减运算对有符号与无符号统一实现，但数值解释不同。

-37 (8-bit) → 37=0010 0101 → invert 1101 1010 → +1 = 1101 1011
Overflow: signed add overflow if inputs share sign and result flips sign. 溢出判定：当两个同号相加且结果变号，则发生有符号溢出。

Bitwise AND/OR/XOR/NOT 按位与/或/异或/取反

0xF0 & 0x3C = 0x30 0b1010 ^ 0b0110 = 0b1100 ~0x00FF = 0xFF00 (on 16-bit view)

Logical vs Arithmetic Shifts 逻辑移位 vs 算术移位

Logical right (>> on unsigned) fills with 0s; arithmetic right (>> on signed) preserves sign bit. 无符号右移用0填充；有符号右移保留符号位（算术右移）。

(unsigned)0xF0 >> 2 = 0x3C ; (signed)-8 >> 2 = -2

Bit Masks & Field Extraction 位掩码与字段抽取

/* test */ int is_set(uint32_t x, int k) { return (x >> k) & 1; } /* set */ uint32_t set_bit(uint32_t x, int k) { return x | (1u << k); } /* clear*/ uint32_t clr_bit(uint32_t x, int k) { return x & ~(1u << k); } /* toggle*/ uint32_t tgl_bit(uint32_t x, int k) { return x ^ (1u << k); } /* extract [h:l] */ uint32_t field(uint32_t x,int h,int l){ return (x >> l) & ((1u<< (h-l+1)) - 1); }

Endianness 字节序 Optional可选

Byte ordering (little vs big-endian). Useful context; rarely examined standalone. 字节顺序（小端/大端）。作为背景知识较有用，但单独考查较少。

🧪 Examples例题与讲解

E1: Two’s Complement Encoding例1：补码编码

Q: Encode -37 in 8-bit two’s complement. 问：将 -37 表示为 8 位补码。

37 → 0010 0101 → invert 1101 1010 → +1 = 1101 1011
Template: positive → binary → invert → plus 1. 模板：正数二进制 → 取反 → 加一。

E2: Field Extraction例2：字段抽取

Q: Extract bits [15:8] from a 32-bit value x. 问：从32位整数 x 中抽取 [15:8] 位。

(x >> 8) & 0xFF
Template: shift down by low index; mask with (1<<(width))-1. 模板：右移至最低位；使用 (1<<(宽度))-1 掩码。

E3: Shift Reasoning例3：移位推导

Q: What is (unsigned)0xF0 >> 2 and why? What about (signed)-8 >> 2? 问：(unsigned)0xF0 >> 2 的结果与原因？(signed)-8 >> 2 又是多少？

0xF0 → 1111 0000 >>2 (logical) = 0011 1100 = 0x3C ; -8 >>2 (arithmetic) = -2

🧮 Worked Walkthrough拆解示范

Scenario: Detect Overflow & Produce Saturated Result 场景：检测溢出并输出饱和值

Exam-style prompt: “Given two signed 16-bit integers a and b, produce their sum unless overflow occurs. If overflow, clamp to INT16_MAX or INT16_MIN.” 考试风格题： “给定两个16位有符号整数 a 与 b，若相加溢出则输出 INT16_MAX/INT16_MIN，否则返回和。”

  1. Compute raw sum with 32-bit temp: int32_t s = (int32_t)a + (int32_t)b; 使用32位临时变量求和：int32_t s = (int32_t)a + (int32_t)b;
  2. Overflow detection via sign bits: overflow if ((a ^ s) & (b ^ s)) & 0x8000 is non-zero. 通过符号位检测溢出：若 ((a ^ s) & (b ^ s)) & 0x8000 ≠ 0，则溢出。
  3. Return s when safe. When overflow occurs, choose clamp using conditional operator. 无溢出时返回 s；若溢出，则根据符号返回相应的饱和值。
int16_t add_sat(int16_t a, int16_t b) { int32_t s = (int32_t)a + (int32_t)b; int32_t overflow = ((a ^ s) & (b ^ s)) & 0x8000; if (!overflow) return (int16_t)s; return (s & 0x8000) ? INT16_MIN : INT16_MAX; }

Tie back to templates: use Template 2 for overflow logic, Template 3 for mask application. 与模板回链：溢出判断使用模板2，掩码操作利用模板3思路。

Scenario: Pack Sensor Flags 场景：打包传感器标志位

Prompt: “Given four 1-bit boolean flags (north, south, east, west) and a 4-bit error code, compose a status word: bits [3:0] store error, bits [7:4] store flags (N,S,E,W).” 题目： “给定四个1比特布尔标记（north/south/east/west）和4位错误码，将它们打包成状态字：低4位为错误码，高4位依次为N、S、E、W。”

uint8_t pack_status(int error, int north, int south, int east, int west) { uint8_t status = 0; status |= (error & 0xF); status |= (north & 1) << 4; status |= (south & 1) << 5; status |= (east & 1) << 6; status |= (west & 1) << 7; return status; }

Reverse operation: apply Template 3 to read back each flag with mask+shift in quizzes. 逆操作：在测验中可用模板3通过掩码+移位读取每个标志位。

⚠️ Common Pitfalls易错点

🛠️ Practice Task实践任务

Bit Toolkit位运算工具集

Implement: count_ones(x), set_field(x,h,l,val), clear_lowest_set(x). 实现：count_ones(x)、set_field(x,h,l,val)、clear_lowest_set(x)。

int count_ones(uint32_t x){ int c=0; while(x){ x &= (x-1); c++; } return c; } uint32_t set_field(uint32_t x,int h,int l,uint32_t v){ uint32_t m=((1u<<(h-l+1))-1u)<

Daily Drill Checklist每日训练清单

  • Morning: write two base-conversion problems (include negative numbers) and solve without calculator. 早间：手写两道进制转换题（含负数），全程不用计算器。
  • Lunch break: implement one mask helper from memory, then explain each line aloud. 中午：凭记忆写出一个掩码函数，并大声解释每行作用。
  • Evening: redo one past-exam overflow question and record your rationale in the study log. 晚上：重做一道往年溢出题，并在学习日志中写下理由。
  • Weekend: simulate Lab 02 under timing constraints (45 minutes) to build fluency. 周末：限时45分钟模拟完成Lab 02，培养手感。

Stretch Goal进阶目标

Write a small command-line tool that reads integers until EOF and reports population count, parity (odd/even number of 1s), and highest set bit position. 编写命令行小工具，读取整数直到EOF，并输出1的数量、奇偶校验（1的个数奇偶）以及最高位1的位置。

Reuse count_ones and clear_lowest_set, and log tricky inputs (0, power-of-two, alternating bits) for quiz revision. 复用 count_ones 与 clear_lowest_set，将棘手输入（0、2的幂、交替比特）记录下来备测验复习。

Go to Week 2 Quiz 进入第 2 周测验

📝 Study Log (Week 2)学习记录（第2周）

  • Inputs to AI: PPT (integers/bitwise), tut/lab 02 links, selected final links. 输入材料：PPT（整数/位运算）、第02周教程/实验链接、部分期末题链接。
  • Key prompts: focus on conversions, masks, overflow; keep Optional under 10%. 关键提示：聚焦转换、掩码、溢出；可选内容≤10%。
  • Learned: standard templates for field extraction and two’s complement. 收获：字段抽取与补码的通用解题模板。
  • Next: attempt Lab02/Tut02 exercises and review mistakes. 后续：完成Lab02/Tut02练习并复盘错题。
  • Reflection: struggled with distinguishing arithmetic vs logical shift—replayed example E3 and documented “sign-bit guard” reminder. 反思：对算术/逻辑右移区分仍有困难——复盘例题E3并记录“符号位守护”提示。
  • Action item: build Anki cards for masks (#template-mask) and overflow rules (#template-twos) with bilingual cues. 行动：为掩码模板（#template-mask）与溢出规则（#template-twos）制作双语Anki卡片。