位运算

二进制与符号位

二进制是以 2 为基数的数制，使用位（bit）表示数值。每一位从右到左代表 2^0、2^1、2^2……的权重。用 N 位二进制可以表示 0 到 2^N - 1 的无符号整数。

例子：8 位二进制 0000 0101 表示十进制 5。
把二进制转换为十进制：按位相加，1*2^k 的和。

有符号与无符号表示的区别

无符号（unsigned）：所有位共同表示大小，范围为 0 到 2^N - 1。
有符号（signed，通常采用补码表示）：最高位作为符号位，0 表示非负，1 表示负数，范围为 -2^(N-1) 到 2^(N-1) - 1。

例如：

8 位无符号范围：0 到 255。
8 位有符号（补码）范围：-128 到 127。

按位与（AND）

按位与操作用符号 & 表示。对两个二进制位同时为 1 的位返回 1，否则返回 0。常用于掩码（mask）操作，保留目标位域。

定义：result = a & b
真值表：0&0=0，0&1=0，1&0=0，1&1=1
用途：屏蔽不需要的位、检测某个位是否为 1

示例（短表达）： if ((flags & MASK) != 0) { ... }

示例（Java）：

int flags = 0b10110;        // 二进制 22
int mask  = 0b00100;        // 只检测第三位
boolean isSet = (flags & mask) != 0; // true，第三位为1

按位或（OR）

按位或操作用符号 | 表示。对两个二进制位中任意一个为 1 的位返回 1，否则返回 0。常用于设置某些位为 1。

定义：result = a | b
真值表：0|0=0，0|1=1，1|0=1，1|1=1
用途：将若干标志合并、把特定位置为 1

示例：

int flags = 0b10000;
int add   = 0b00110;
int merged = flags | add; // 0b10110，将 add 指示的位设置为1

按位异或（XOR）

按位异或操作用符号 ^ 表示。对两个二进制位不同则返回 1，相同返回 0。异或具有可逆性：a ^ b ^ b = a。

定义：result = a ^ b
真值表：0^0=0，0^1=1，1^0=1，1^1=0
用途：切换（翻转）位、校验或在无需临时变量时交换两个数（仅整数场景）

示例（翻转指定位）：

int flags = 0b10110;
int toggle = 0b00100;         // 翻转第三位
flags = flags ^ toggle;       // 第三位被翻转

示例（交换两个整数，不用临时变量，仅示例说明）：

int x = 5;
int y = 7;
x = x ^ y;
y = x ^ y; // y = 原 x
x = x ^ y; // x = 原 y

注意：用异或交换仅适用于整数且在可读性上较差，一般不推荐用于生产代码。

按位非（NOT，取反）

按位非用符号 ~ 表示，对每一位取反，0 变 1，1 变 0。结果长度与数据类型宽度相关（例如在 Java 中对 int 是 32 位）。

定义：result = ~a
用途：产生掩码的反掩码、快速求相反位模式

示例：

int a = 0b00001111;  // 15
int b = ~a;          // 32位 int 的按位取反，结果为 -16（二进制补码表示）

说明：按位取反和负数的补码表示有关，直接观察十进制结果时要注意符号扩展和数据类型位宽。

左移（<<）

左移运算用符号 <<，将二进制位向左移动若干位，高位丢弃，低位补 0。等价于乘以 2 的若干次方（对于无符号情形）。在有符号整型中，左移不会改变符号位的定义方式，但可能改变符号。

定义：result = a << n（把 a 的位向左移动 n 位）
用途：快速乘以 2 的幂、在位域中放置值（例如把低位值移到高位段）

示例：

int x = 1;
int y = x << 4; // 1 * 2^4 = 16，二进制 0b10000

注意：当移位位数超过类型位宽或接近时，结果受语言规范影响（例如 Java 中移位的位数会对整型宽度取模）。

右移（算术右移，>>）

算术右移用符号 >>，将二进制位向右移动若干位，低位丢弃，高位用原符号位填充（保持符号）。等价于除以 2 的若干次方并向负无穷舍入（对负数保持符号）。

定义：result = a >> n
用途：快速除以 2 的幂（保留符号）、从高位字段恢复带符号值

示例：

int a = -16;     // 二进制补码表示
int b = a >> 2;  // 结果为 -4（向右移位，符号位保持）

无符号右移（逻辑右移，>>>）

逻辑右移用符号 >>>（在 Java 中），将二进制位向右移动若干位，高位统一补 0（不保留符号）。在需要将带符号整型视为无符号值时常用。

定义（Java）：result = a >>> n
用途：无符号右移、对位模式的无符号解释、从高位字段恢复无符号值

示例：

int a = -1;          // 所有位为 1（32 位）
int b = a >>> 1;     // 最高位补 0，结果为 0x7FFFFFFF（正数）

位掩码与位域

位掩码是使用位运算控制或访问特定位或位段的常用技术。掩码通常使用左移或常量构造。

创建单个位的掩码：1 << n 表示第 n 位
创建连续位段掩码：((1 << width) - 1) << offset

示例（短）： int mask = ((1 << 5) - 1) << 8; // 在偏移 8 上创建宽度 5 的掩码

示例（Java，注意溢出与类型宽度）：

int width = 5;
int offset = 8;
int mask = ((1 << width) - 1) << offset; // 掩码覆盖 offset..offset+width-1 的位

注意：当 width 等于或超过数据类型位宽时需要特殊处理，避免 1 << width 溢出或结果不符合预期。

位的测试 / 设置 / 清除 / 切换（通用模式）

测试某位是否为 1：(value & (1 << n)) != 0
设置某位为 1：value = value | (1 << n) 或 value |= (1 << n)
清除某位为 0：value = value & ~(1 << n) 或 value &= ~(1 << n)
切换（翻转）某位：value = value ^ (1 << n) 或 value ^= (1 << n)

示例：

int flags = 0;
int bit = 3;
flags |= (1 << bit);   // 设置第3位
boolean isSet = (flags & (1 << bit)) != 0;
flags &= ~(1 << bit);  // 清除第3位
flags ^= (1 << bit);   // 切换第3位

常见注意事项与陷阱

移位位数的范围：在不同语言中，移位时移位计数可能会被模类型位宽（例如 Java 中 int 的移位计数对 32 取模），要参照语言规范。
符号扩展：算术右移 >> 会保留符号，逻辑右移 >>> 则补零，注意负数处理差异。
类型宽度与溢出：构造掩码或使用常量时要注意整型溢出，例如 1 << 31 在 int 中是负数；在需要时应使用更宽类型或无符号类型（例如 Java 使用 1L << 31）。
可读性：尽管位运算高效，但过度使用会降低代码可读性，使用具有描述性的常量和注释提高可维护性。

示例：ReentrantReadWriteLock 中的高低位计数模式

在 Java 的 ReentrantReadWriteLock 源码中，常见的模式是将读计数放在整型状态的高若干位，写计数放在低若干位。例如：

SHARED_SHIFT = 16
SHARED_UNIT = (1 << SHARED_SHIFT)，即 1 << 16 = 65536
状态 c 的高 16 位：readCount = c >>> SHARED_SHIFT
状态 c 的低 16 位：writeCount = c & ((1 << SHARED_SHIFT) - 1)（等价于 c & 0xFFFF）

示例代码片段（Java）：

int c = getState();
int readCount = c >>> 16;
int writeCount = c & 0xFFFF;

c += SHARED_UNIT; // 增加一个读锁计数（c = c + 65536）
c -= SHARED_UNIT; // 减少一个读锁计数

位运算

位运算