📚 IB CIE Computer Science Formula Handbook | IB CIE 计算机科学公式汇总手册
This handbook brings together the essential formulas, conversions, and efficiency measures required for IB and CIE Computer Science courses. It covers data representation, Boolean algebra, algorithm complexity, networking computations, and error control — all presented with clear, concise expressions and dual‑language explanations.
本手册汇集了 IB 和 CIE 计算机科学课程中必备的公式、转换规则和效率度量。内容涵盖数据表示、布尔代数、算法复杂度、网络计算和差错控制，全部配以清晰简洁的表达式和双语解释。
1. Number Systems and Conversions | 数制与转换
To convert a decimal integer to binary, repeatedly divide by 2 and record the remainders. The binary result is read from the last remainder upwards.
将十进制整数转换为二进制时，反复除以2并记录余数，从最后一个余数向上读取即为二进制结果。
A binary number can be converted to hexadecimal by grouping the bits into sets of four (starting from the right) and converting each group to its hex digit. Hexadecimal to binary simply reverses this process.
二进制转十六进制时，将位从右向左每四位一组，每组转换为一个十六进制数字；十六进制转二进制则逆向展开。
The number of bits required to represent N distinct states is the ceiling of the base‑2 logarithm:
表示 N 种不同状态所需的最少位数为以2为底的对数上取整：
Bits required = ⌈log₂ N⌉
For an unsigned integer with n bits, the maximum representable value is 2ⁿ − 1.
对于 n 位的无符号整数，最大可表示的值为 2ⁿ − 1。
2. Binary Arithmetic and Overflow | 二进制算术与溢出
When adding two two’s complement numbers, an overflow occurs if the carry into the sign bit differs from the carry out of the sign bit. In unsigned addition, overflow is simply a carry out of the most significant bit.
对两个二进制补码做加法时，若进入符号位的进位与出符号位的进位不同，则发生溢出。无符号加法中，最高位产生进位即视为溢出。
To convert a negative decimal number to two’s complement: first write the positive magnitude in binary, then invert all bits (one’s complement) and add 1.
将负数转换为补码的方法：先写出其绝对值的二进制原码，再将所有位取反（反码），最后加1。
The rule for overflow detection can be expressed as a logic condition:
溢出检测规则可以表示为逻辑条件：
Overflow = Carryₙ₋₁ ⊕ Carryₙ
where Carryₙ₋₁ is the carry into the sign bit and Carryₙ is the carry out.
其中 Carryₙ₋₁ 表示进入符号位的进位，Carryₙ 表示出符号位的进位，⊕ 为异或。
3. Data Representation: Integers | 数据表示：整数
Sign‑and‑magnitude representation uses the leftmost bit for sign (0 for positive, 1 for negative) and the remaining bits for the magnitude. With n bits, the range is:
原码表示法用最左位表示符号（0正1负），其余位表示数值大小。对于 n 位，其表示范围为：
−(2ⁿ⁻¹ − 1) to +(2ⁿ⁻¹ − 1)
Two’s complement representation avoids a negative zero and has an asymmetric range:
补码表示法消除了负零，其范围为非对称的：
−2ⁿ⁻¹ to (2ⁿ⁻¹ − 1)
To compute the value of a two’s complement number bₙ₋₁bₙ₋₂…b₀, use:
计算补码数值的公式为：
Value = −bₙ₋₁ × 2ⁿ⁻¹ + Σ (bᵢ × 2ⁱ) for i = 0 to n−2
4. Data Representation: Floating-point | 浮点数表示
Binary floating‑point numbers store a value as (−1)^sign × 1.mantissa × 2^(exponent − bias). The bias for an exponent field of k bits is 2⁽ᵏ⁻¹⁾ − 1. For single precision (8‑bit exponent), bias = 127.
二进制浮点数将数值存储为 (−1)^符号 × 1.尾数 × 2^(阶码 − 偏置)。k 位阶码的偏置值为 2⁽ᵏ⁻¹⁾ − 1。单精度（8位阶码）的偏置为127。
The normalized mantissa has an implied leading 1, so the fractional part m represents 1.m. The value of a single‑precision float is:
规格化尾数隐含一个前导1，因此小数部分 m 实际表示 1.m。单精度浮点数的值为：
(−1)ˢ × (1.m) × 2⁽ᵉ⁻¹²⁷⁾
Special values: exponent all 1s with mantissa 0 represents infinity; exponent all 1s with non‑zero mantissa represents NaN.
特殊值：阶码全1且尾数为0时表示无穷大；阶码全1且尾数非0时表示 NaN（非数）。
5. Boolean Algebra and Logic Gates | 布尔代数与逻辑门
Boolean algebra uses the operators AND (·), OR (+), and NOT (′). The fundamental identities include:
布尔代数使用与（·）、或（+）、非（′）运算符。基本恒等式包括：
A + 0 = A, A · 1 = A, A + A′ = 1, A · A′ = 0, A + A = A, A · A = A
De Morgan’s laws are essential for simplifying and transforming logic expressions:
德摩根定律对化简和转换逻辑表达式至关重要：
(A · B)′ = A′ + B′
(A + B)′ = A′ · B′
The XOR (⊕) operation can be expressed with basic gates: A ⊕ B = A · B′ + A′ · B. A NAND gate alone is functionally complete.
异或（⊕）可用基本门表示：A ⊕ B = A·B′ + A′·B。单用与非门便构成功能完备集。
6. Karnaugh Maps and Simplification | 卡诺图与化简
A Karnaugh map for n variables contains 2ⁿ cells, each labelled with a minterm. Adjacent cells differ by exactly one variable; grouping adjacent 1s yields a minimal Sum‑of‑Products (SOP) expression.
n 个变量的卡诺图包含 2ⁿ 个单元格，每个单元格对应一个最小项。相邻单元格仅有一个变量不同；圈出相邻的1即可得到最简积之和（SOP）表达式。
The number of cells in a group must be a power of 2 (1, 2, 4, 8, …). Each group eliminates the variables that appear in both complemented and uncomplemented forms.
每个圈中的单元格数必须为2的幂（1, 2, 4, 8, …）。每个圈可消去既出现原变量又出现反变量的变量。
For a Product‑of‑Sums (POS) simplification, group the 0s and write the complemented output expression.
对于和之积（POS）化简，则圈出卡诺图中的0，并写出取反后的输出表达式。
7. Algorithm Complexity and Big O | 算法复杂度与大O符号
Big O notation describes the upper bound of an algorithm’s running time or space usage. Common complexities and their typical meanings are:
大O符号描述算法运行时间或空间占用的上界。常见的复杂度及其典型含义：
| Big O | Name | 中文名称 |
|---|---|---|
| O(1) | Constant | 常数 |
| O(log n) | Logarithmic | 对数 |
| O(n) | Linear | 线性 |
| O(n log n) | Linearithmic | 线性对数 |
| O(n²) | Quadratic | 平方 |
| O(2ⁿ) | Exponential | 指数 |
| O(n!) | Factorial | 阶乘 |
The efficiency of a recursive algorithm can often be expressed by a recurrence relation; solving it gives the Big O. For example, Merge Sort follows T(n) = 2T(n/2) + O(n), leading to O(n log n).
递归算法的效率常可用递推关系表示，求解后得到大O。例如归并排序满足 T(n) = 2T(n/2) + O(n)，可得 O(n log n)。
8. Searching and Sorting Algorithms | 查找与排序算法
Linear search scans each element sequentially; worst‑case comparisons = n, average = n/2.
线性查找逐个扫描元素，最坏情况需要比较 n 次，平均为 n/2 次。
Binary search on a sorted array halves the search space each step. Maximum comparisons = ⌈log₂(n+1)⌉ ≈ log₂ n.
二分查找在已排序的数组上每次将搜索空间减半，最大比较次数为 ⌈log₂(n+1)⌉ ≈ log₂ n。
Bubble sort and Insertion sort have quadratic worst‑case time. The number of comparisons for Bubble sort is:
冒泡排序和插入排序的最坏情况时间复杂度为平方级。冒泡排序的比较次数为：
Comparisons = n(n−1) / 2 = (n² − n) ÷ 2
Merge sort divides and conquers; depth of splitting is log₂ n, and at each level n elements are merged, giving O(n log n).
归并排序采用分治策略；分割深度为 log₂ n，每层合并 n 个元素，因此总复杂度为 O(n log n)。
9. Networking and Data Transmission | 网络与数据传输
Transmission time (serialization delay) is the time to push all bits of a frame onto the link:
传输时间（串行化延迟）是把帧所有位推入链路的时间：
Transmission time = File size (bits) / Bandwidth (bps)
Propagation delay depends on the physical distance and signal speed:
传播延迟取决于物理距离和信号速度：
Propagation delay = Distance / Propagation speed
Total delay is the sum of transmission time, propagation delay, queuing delay, and processing delay. Bandwidth‑delay product = Bandwidth × RTT.
总延迟为传输时间、传播延迟、排队延迟和处理延迟之和。带宽延迟积 = 带宽 × 往返时间。
To convert file sizes: 1 byte = 8 bits, 1 KB = 1024 bytes for storage; in networking, 1 kbps = 1000 bits per second.
文件大小换算：1字节 = 8位，存储中 1 KB = 1024 字节；网络中 1 kbps = 1000 位每秒。
10. Compression and File Sizes | 压缩与文件大小
The compression ratio measures how much a file is reduced:
压缩比衡量文件缩小的程度：
Compression ratio = Original size / Compressed size
Space saving percentage is often given by (1 − Compressed / Original) × 100%.
节省空间的百分比常表示为 (1 − 压缩后大小 / 原始大小) × 100%。
For an uncompressed audio file:
对于未压缩的音频文件：
Audio file size = Sample rate × Bit depth × Number of channels × Duration (seconds)
For a bitmap image:
对于位图图像：
Image file size = Width (pixels) × Height (pixels) × Colour depth (bits per pixel)
11. Error Detection and Correction | 错误检测与纠正
Parity bits add a single bit to make the total number of 1s even (even parity) or odd (odd parity). It can detect any single‑bit error but cannot correct it.
奇偶校验通过增加一个位使1的总数为偶数（偶校验）或奇数（奇校验），可检测任何单比特错误，但无法纠正。
Hamming distance between two codewords is the number of bit positions in which they differ. For a code with minimum Hamming distance d:
两个码字之间的汉明距离是它们不同位的个数。如果码的最小汉明距离为 d，则：
Detectable errors ≤ d − 1
Correctable errors ≤ ⌊(d − 1)/2⌋
Checksums (e.g. Internet checksum) use one’s complement addition of data blocks; Cyclic Redundancy Check (CRC) uses polynomial division and can detect burst errors up to the degree of the generator polynomial.
校验和（如互联网校验和）采用数据块的反码加法；循环冗余校验（CRC）利用多项式除法，能够检测出长度不超过生成多项式的突发错误。
12. Digital Logic Circuit Timing | 数字逻辑电路时序
The propagation delay of a gate is the time between an input change and the corresponding output change. In a ripple‑carry adder, the worst‑case delay occurs when a carry must propagate through all full adders:
门电路的传播延迟指输入变化到相应输出变化所需的时间。在行波进位加法器中，最坏延迟发生在进位必须经过所有全加器的情况下：
Total delay = n × Delay of a single full adder
For synchronous circuits, the clock period must be longer than the longest combinational path delay plus setup and hold times, ensuring reliable operation.
对于同步电路，时钟周期必须大于最长组合路径延迟加上建立时间和保持时间，以确保工作可靠。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导