《算法导论》中“机器字长w位、k fits into a single word”含义解释

你看到的原文：

Suppose that the word size of the machine is w bits and that k fits into a single word
中文翻译：假设机器字长为w位，且整数k可以存入单个机器字。

核心概念拆解 #

• 机器字长w：就是你已知的32位、64位这类硬件固有参数，是CPU单次运算、内存单次读写的最小自然数据块大小。
• k fits into a single word的实际约束：整数k的二进制表示长度不超过w位，不需要拆分到多个连续的内存字单元存储，CPU可以一次把整个k读进寄存器处理。
  • 如果k是无符号整数，等价于取值范围满足 0 ≤ k ≤ 2^w - 1
  • 如果k是带符号整数，等价于取值范围满足 -2^(w-1) ≤ k ≤ 2^(w-1)-1

这个假设的作用 #

这是算法复杂度分析里非常常见的前提假设，在第11章散列表相关内容里，这个假设是为了保证后续和k相关的位运算、乘法、取模等散列计算操作，都能在常数时间O(1)内完成——如果k太大塞不进一个机器字，就需要拆分多个字做大整数运算，时间开销就不是常数了，会干扰散列操作均摊O(1)复杂度的推导。

举个直观的例子：32位字长的机器，单字能存的最大无符号整数是4294967295；64位字长的机器这个上限是18446744073709551615，绝大多数日常业务场景用到的整数都满足这个单字存储的要求。

内容的提问来源于stack exchange，提问作者Learner