ShowDocs
搜索文章Ctrl K

外观

← 返回数学列表
知识讲解

程序员数学 04：整数、取模与位运算 ​

数学中的整数可以无限大，程序中的整数表示往往有范围。先分清数学模型与语言语义，才不会把一个正确的公式写成错误代码。

模运算让位置循环 ​

对正整数 m，若 m 整除 a−b，就记为 a≡b(modm)。例如 14≡2(mod12)。长度为 12 的环上，走到下标 14 与走到下标 2 落在同一位置。

对非负整数下标，下一位置可写成 (index + 1) % length，前提是 length 为正整数。长度为 0 时没有有效环形下标，不应直接代入。

JavaScript 的 % 是余数运算，负数行为不等同于始终取非负代表元的数学模运算。参见 MDN 余数运算说明。小整数范围内可这样归一化：

js
const index = -1;
const length = 5;
console.log(index % length);                   // -1
console.log(((index % length) + length) % length); // 4

它要求 length > 0，并要求数值运算精确且不溢出；不要将公式不加检查地用于任意浮点输入或超范围整数。

二进制把集合编码成位 ​

给三个独立标记分配不同的二进制位：读为 001，写为 010，执行为 100。按位或表示加入标记，按位与表示检查交集。

js
const READ = 1, WRITE = 2, EXECUTE = 4;
let permissions = READ | WRITE;
console.log((permissions & READ) !== 0);          // true
console.log((permissions & EXECUTE) !== 0);       // false
console.log((permissions & (READ | WRITE)) === (READ | WRITE)); // true
permissions &= ~WRITE;
console.log(permissions); // 1

检查“至少一个需要的位”用交集非零；检查“全部需要的位”要与完整掩码相等，不能混用。空掩码也需要业务定义：按集合包含关系，空集被任何集合包含。

JavaScript 对 Number 的这些位运算使用 32 位整数语义；不要用 1 << 40 表示第 40 位。需要更大位集时，选择明确的 BigInt 位运算或集合结构，并统一类型。

哈希取模不等于无碰撞 ​

将键的哈希值对 m 取模，可以得到 m 个桶中的一个。键多于桶时，根据抽屉原理至少有两个键落入同一桶。即使键少于桶，也仍可能碰撞。

例如 hash(key) % 4 只能产生四类非负余数。把模数换成某个质数，并不自动保证均匀，更不保证无碰撞；分布还取决于哈希函数和输入。不要把取模本身当成安全哈希或唯一 ID 方案。

练习 ​

  1. 长度为 7 的环中，下标 1 向后退 3 格，非负下标是多少？
  2. 掩码为 5，即二进制 101，包含 READ、WRITE、EXECUTE 中哪些权限？
  3. 1001 个不同键映射到 1000 个桶，能否保证全部不碰撞？
查看答案与讲解
  1. 原位置为 1−3=−2，模 7 的非负代表元是 5。
  2. READ 和 EXECUTE；WRITE 对应中间位，为 0。
  3. 不能，至少有一次碰撞。这只证明碰撞必然存在，不说明哪一对键碰撞，也不描述碰撞有多均匀。

资料与延伸 ​

MIT 6.042J 阅读目录 的数论与计数材料适合补充同余和抽屉原理。超过普通整数精度范围的问题继续看浮点数、误差与单位。

继续阅读