Chapter 1 · Introduction

按Hacker's Delight第二版第1章重建机器字记号、补码解释、指令集与执行时间模型。

从“同一串位为何有两个数值”开始

先预测：bit pattern 11101010既可表示unsigned 234，也可表示8-bit signed -22。AND、OR、XOR看到的是相同bits，但comparison、right shift、overflow与division会因interpretation不同而改变。Hacker's Delight的技巧不是脱离machine semantics的魔法；每个identity都依赖word width、signedness与instruction behavior。

（word）是本书的基本对象。先固定 $w$ ，再讨论mask、complement、rotate与overflow；没有width，NOT之后有多少high bits为1都没有答案。

1.1 Notation

Words, bits, and width

令word $x$ 的bits为 $x_{w-1}\ldots x_1x_0$ ， $x_0$ 是least significant bit， $x_{w-1}$ 是most significant bit。Unsigned interpretation为

U_w(x) = \sum_{i=0}^{w-1}x_i2^i, \qquad 0\le U_w(x)\le2^w-1.

与storage pattern一一对应。Arithmetic在unsigned word上按modulo $2^w$ 封闭：

x+y \quad\mapsto\quad (U_w(x)+U_w(y))\bmod 2^w.

Carry-out是数学结果超出word的evidence，不属于stored low word。多字算术会显式保留carry；普通single-word result则只保留low $w$ bits。

Two's-complement interpretation

（two's complement）定义

S_w(x) = -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2}x_i2^i.

等价地，若unsigned value低于 $2^{w-1}$ ，signed value不变；否则减 $2^w$ 。

Signed range为

-2^{w-1} \le S_w(x) \le 2^{w-1}-1.

最小negative value没有positive counterpart，所以对minimum integer取absolute value会overflow。后续所有branchless absolute、sign、min/max技巧都必须单独检查这个boundary。

Unsigned与signed cast若仅改变interpretation、保留low bits，可通过上述piecewise mapping推理；但programming language可能对out-of-range conversion作额外规定。Proof要分离abstract word algebra与具体language semantics。

Binary and hexadecimal notation

Binary最直接，却在32或64 bits时难以阅读。Hexadecimal每digit对应4 bits：high nibble与low nibble边界一目了然。

Mask应同时给width或类型，例如8-bit mask 0xFF与32-bit 0x000000FF在low byte相同，但complement结果不同。Leading zeros不是无意义排版，它们表达declared width。

Bit positions从0计数。One-hot mask $2^i$ 选择position $i$ ；low $k$ bits mask为 $2^k-1$ ，前提是 $k$ 处于valid range。若 $k=w$ ，在某些languages中直接shift by width是undefined或被hardware取模，必须特殊处理。

Logical operations

Logical operations逐bit独立：

(x\mathbin{\&}y)_i=x_i\land y_i, \quad (x\mathbin{|}y)_i=x_i\lor y_i, \quad (x\mathbin{\oplus}y)_i=x_i\oplus y_i.

AND用于clear或extract，OR用于set，XOR用于toggle与difference，NOT用于complement。Fixed width下

\operatorname{NOT}_w(x) = x\oplus(2^w-1).

这条width-aware formula避免host integer把infinitely many conceptual high bits也补成1。

常见notation还区分arithmetic addition/subtraction与logical operations。虽然XOR像“无进位加法”，它不是ordinary addition；carry bits由AND与left shift产生，Chapter 2会系统使用这一分解。

Shift and rotate notation

Left shift把bits向higher positions移动、low positions补0，并丢弃越过word width的bits。对unsigned且shift amount valid：

x\mathbin{\mathrm{shl}}n = (x2^n)\bmod2^w.

等价于unsigned floor division by $2^n$ 。

对negative input通常向negative infinity取整，而C/C++ signed division则向0截断；二者不能直接互换。

Rotate把移出的bits从另一端重新插入，不丢information。Rotate amount常按word width归一化，但language library与hardware具体规则不同；portable implementation要避免shift by exactly $w$ 。

Endianness is a memory property

Endianness描述multi-byte word写入addressed memory时的byte order。它不改变abstract word value，也不改变bit position 0是least significant bit。

只有在byte loads、serialization、network protocols或type punning时，endianness才进入公式。纯register-level AND/XOR/shift identity通常与endianness无关。

1.2 Instruction Set and Execution Time Model

The basic RISC proxy

（basic RISC）把常见primitive operation视为一条instruction，为不同bit tricks提供一致比较尺度。

模型通常关注：

Register logical operations：AND、OR、XOR、complement。
Fixed或variable shifts与rotates。
Addition、subtraction、negation与carry/borrow相关operations。
Comparisons、condition-code extraction与branches。
Multiplication、division等可能具有不同cost的operations。

它不是某一真实ISA的完整emulator。不同architectures可能有population count、count-leading-zeros、bit-field extract、conditional select等single instructions，使某个software identity失去性能优势。

Counting instructions

（execution time model）首先统计instruction count：

T_{\mathrm{model}} = \sum_j c_jN_j,

其中 $N_j$ 是class $j$ 的executed count， $c_j$ 是model cost。最简basic RISC常令多数 $c_j=1$ 。

Static count、worst-case executed count、average count与dependency depth是不同metrics。Straight-line sequence即使有8条instructions，若可parallel issue，latency可能接近dependency chain长度；反之，连续dependent shifts无法完全并行。

Branches and real processors

Branchless不是自动更快。Predictable branch可能只执行few instructions；branchless expression会固定执行所有operations。Unpredictable branch的misprediction penalty则可能使稍长的straight-line code占优。

Memory hierarchy、vectorization、instruction throughput、port pressure、register pressure与compiler transformations都不在simple count中。正确workflow是：

先用basic model缩小candidates。
检查compiler generated code。
在target ISA、compiler flags与representative data上benchmark。
同时保留reference implementation和correctness tests。

不应把2013年的某条instruction estimate直接写成2026 processor上的固定cycle claim。

Language-level contract

Book identities常按fixed-width two's-complement algebra表达。Portable C/C++实现应优先使用exact-width unsigned types，因为unsigned overflow按modulo定义；signed overflow则是undefined behavior，compiler可据此做看似意外的optimization。

#include <stdint.h>
 
static uint32_t low_word_add(uint32_t x, uint32_t y) {
    return x + y; // Defined modulo 2^32.
}

Shift amount必须低于type width；left shifting negative signed value或使signed result不可表示也可能undefined。Right shift of negative signed integers在现代C++有明确规则，但跨language与旧standards仍应显式核对。

static uint32_t logical_right_32(uint32_t x, unsigned n) {
    // Caller proves n is in [0, 31].
    return x >> n;
}

Type punning、alignment与endianness属于memory representation contract。需要reinterpret bits时使用language-defined bit-cast或byte copy path，而不是违反strict aliasing。

From experiments to proof

Bit identities适合small-width exhaustive testing。若identity为unary，可枚举所有 $2^w$ patterns；binary identity需要 $2^{2w}$ pairs。

EXHAUSTIVE-CHECK(width w, candidate, reference)
1  mask = 2^w - 1
2  for every x in [0, mask]
3      normalize candidate(x) and reference(x) to w bits
4      fail and print x if results differ
5  report all 2^w cases checked

Small-width exhaustive pass是强evidence，也经常发现zero、all-ones、minimum signed与boundary shift bugs。但它不是all-width proof；最终还需逐bit algebra、modular arithmetic或case analysis说明任意 $w$ 成立。

本书技巧的统一验收流程

小结

Chapter 1 Introduction建立Hacker's Delight第二版的共同language。Notation先固定word width与bit positions，再区分unsigned interpretation和two's-complement signed interpretation；hex、logical operations、logical/arithmetic shifts、rotate和endianness都有明确边界。

Instruction set and execution time model使用basic RISC作为稳定比较proxy，但不替代真实processor measurement。Portable implementation还要遵守language关于unsigned wraparound、signed overflow、shift count与aliasing的规则。

后续每个hack都应交付四层证据：abstract identity、fixed-width reference、edge-case or exhaustive tests、target-specific performance measurement。缺任一层，都不能从“公式很巧”直接升级为“可移植且更快”。