从二分查找溢出讲清Java移位运算符：＞＞、＞＞＞、＜＜与补码差异

在一次代码审查里有人指着int mid (low high) 1;问我这里为什么要用三个大于号写成(low high) / 2不是一样吗更省事。我当时没直接回答而是让他把low设成1000000000、high设成2000000000跑一遍。结果他盯着那个负数mid看了半天说了一句原来/ 2会溢出啊。这个问题的答案横跨了移位运算符的三条主线右移时符号位到底填什么、移位量超出位宽时算几位、以及语言规范对溢出到底保证什么。、、这三个符号看起来像语法糖实际上每一条规则背后都有具体的机器语义和语言设计取舍。我见过太多人把它们当成乘 2除 2的快捷写法然后在1 31、b 1、1 32这几个点上连续翻车。这篇内容适合所有写过位运算的人看不管你是刚开始接触二进制的新手还是写了几年业务代码、偶尔要在协议解析或位图里用移位的工程师下面这些坑基本都会碰到。我会从二分查找那个真实的 bug 讲起把补码、类型提升、跨语言差异一层层拆开最后给出我在实际项目里固定检查的几个审查点。1.(low high) 1这个写法到底在防什么1.1 溢出才是二分查找真正的 bug 来源先把这个经典案例讲透因为它一次性暴露了移位运算符的三个关键特性。low high的结果是int两个都不超过Integer.MAX_VALUE的正数相加结果完全可能超过2147483647。在 Java 里int运算溢出不会抛异常它会静默回绕1000000000 2000000000 3000000000而3000000000 - 4294967296 -1294967296。这时候如果再执行-1294967296 / 2得到的是-647483648。一个负数下标传给数组直接ArrayIndexOutOfBoundsException。这就是二分查找历史上真实存在过的缺陷Joshua Bloch 在 2006 年专门写过一篇博文讲这件事java.util.Arrays.binarySearch也是在那个时期把写法改成了(low high) 1。那为什么(low high) 1就能拿到正确答案把-1294967296写成 32 位二进制是0xB2D05E00也就是符号位为 1。在右移时往高位补 0移一位之后变成0x59682F00换算成有符号整数正好是1500000000也就是3000000000 / 2的正确答案。1.2为什么替代不了同样拿-1294967296试因为符号位是 1算术右移会把最高位继续补 1结果是0xD9682F00还是个负数。所以在这个场景里完全失效。这就是和的根本分野把最高位当作符号位来尊重把它当作普通数据位来处理。前者保号后者不保号。顺带提一个容易忽略的点算术右移对负数的结果等价于向下取整的除法不是截断除法。-5 1等于-3而-5 / 2在 Java 里等于-2因为整数除法是朝零截断的。这两个规则不一致凡是把和/混着用、又涉及负数的代码几乎必然出现 off-by-one。1.3 换成long之后这个写法还成立吗如果把low和high都提升成longlow high就不会溢出此时和的结果完全一致写哪个都对。真正要小心的是运算符优先级Java 里的优先级高于所以long mid (long) low high 1;实际等价于((long) low high) 1没问题。但如果你写成long mid (long) (low high) 1;括号里的加法已经在int域里溢出完了再转long也救不回来。这两种写法的差别只有一对括号但结果完全不同。我个人的习惯是只要涉及两个可能很大的数相加取中值一律写成low ((high - low) 1)或者显式补上括号不给自己留犹豫的空间。2. 补码视角下右移往高位填的到底是什么2.1 算术右移负数右移等于向下取整想真正记住的行为最好直接从补码推。以 32 位int为例-5的补码是0xFFFFFFFB推导方式是~5 1也就是0xFFFFFFFA 1。对这个值做 1符号位是 1所以最高位补 1整体右移一位后得到0xFFFFFFFD。0xFFFFFFFD取反加一~0xFFFFFFFD 0x00000002加一得 3所以值是-3。这个结果其实可以用一句话记住对有符号整数x n恒等于floor(x / 2^n)。注意是floor不是截断。Java 里正好有Math.floorDiv可以对照验证Math.floorDiv(-5, 2) -3和-5 1完全一致。2.2 逻辑右移把符号位也当成数据-5 1就完全是另一回事了。0xFFFFFFFB右移一位高位补 0得到0x7FFFFFFD也就是十进制的2147483645。一个负数经过之后直接变成一个接近Integer.MAX_VALUE的正数这个跳变幅度第一次看确实会愣一下。这里有个实操层面的通用结论对于非负数和的结果完全相同只有当左操作数可能是负数时两者才会分叉。所以平时写位图、掩码、下标计算输入天然非负用哪个都行。但只要你处理的是哈希值、字节流、有符号 ID就必须明确自己想不想要符号扩展。2.3 左移不溢出信息别指望能还原的行为相对简单低位补 0高位直接丢弃。正因为高位被丢掉左移是不可逆的。int a 0x40000000; // 1073741824 int b a 1; // 0x80000000即 Integer.MIN_VALUE int c b 1; // 0xC0000000即 -1073741824a 1 1并不等于a因为中间那一步已经把信息丢了。任何先左移打包、再右移解包的代码都必须保证每一步都在容量范围内否则就是不可逆的数据损坏。顺带说一个使用频率很高的场景从字节流里抽取一个 16 位有符号数时常用(short) ((raw 16) 16)来做符号扩展。这里的原理是先把目标位推到最高位再算术右移把符号位传染到整个高位区这是一个非常经典的位技巧。3. 移位量这件事各语言的规矩完全不一样3.1 Java移位量按0x1F或0x3F取模Java 语言规范规定得很死左操作数是int时移位量只用低 5 位等价于shift 0x1F左操作数是long时用低 6 位等价于shift 0x3F。System.out.println(1 32); // 1因为 32 0x1F 0 System.out.println(1 33); // 2 System.out.println(1 -1); // -2147483648因为 -1 0x1F 31 System.out.println(1L 64); // 164 0x3F 0这个规则没有一个越界就报错的兜底它是静默取模。所以1 32 1这种结果看起来像玄学其实是规范明文规定的。我见过实际代码里出现1 i而i来自配置或循环变量的情况一旦i到了 32、64、96掩码就会诡异地重复而且不会报错只会让线上的权限判断在某几个编号上错乱。这种 bug 排查起来非常费劲因为控制台不会有任何异常输出。3.2 C/C越界移位是未定义行为C 和 C 在这件事上比 Java 危险得多。当移位量大于等于类型位宽或者为负数时行为是未定义的编译器可以任意处理。危险在于x86 的shl指令本身会把移位量按0x1F截断所以你在本机测试时看到的结果和 Java 一模一样可能会以为没问题。但换个架构、换个优化等级或者编译器认定这段代码不可达而直接优化掉结果就变了。开-O2之后逻辑莫名改变的情况在位运算代码里并不罕见。C/C 还有一个差异对有符号整数做左移如果结果溢出在 C 里依然是未定义行为C20 之后左移被明确定义为按无符号回绕但如果你面对的是老代码库或者跨标准编译还是别依赖这个。3.3 JavaScript先塞进 32 位再说JavaScript 的数字是双精度浮点但所有位运算都会先把操作数转成 32 位整数。、用的是ToInt32用的是ToUint32移位量同样按 31处理。console.log(1 32); // 1 console.log(1 31); // -2147483648 console.log(-1 0); // 4294967295 console.log(-1 1); // 2147483647 console.log(2 ** 31 | 0); // -2147483648注意最后一行2 ** 31本身是2147483648这个正常的浮点数但一旦参与位运算就被截成-2147483648。所以 JS 里位运算是不能直接用来做大整数计算的超过 32 位的部分会被直接丢掉。要用超过 32 位的位运算只能用BigInt而BigInt只支持和没有。 0这个写法在 JS 社区里几乎是标准操作用来把任意数字转成无符号 32 位视图。后面讲调试的时候还会用到它。3.4 防御性写法不管你用哪种语言只要移位量来自变量就应该在边界上做一次夹紧而不是赌语言规范帮你兜底。static int safeShift(int value, int shift) { if (shift 0 || shift 31) { throw new IllegalArgumentException(shift out of range: shift); } return value shift; }多这一层判断代价是一次比较换来的是线上不再出现某个编号的权限偶尔失效这种幽灵问题。我在处理权限位和位图索引时都会在入口处做这个校验。4. 类型提升带来的经典翻车现场4.1byte参与移位之前会先变成int这是我在面试和代码审查里见过最多的一个坑。byte b (byte) 0xFF; // 实际值是 -1 System.out.println(b 1); // 2147483647不是 127 System.out.println((b 0xFF) 1); // 127这才对原因很清楚Java 里byte和short在参与几乎所有算术和位运算之前都会被提升成int。提升过程中符号扩展0xFF变成0xFFFFFFFF然后 1就得到0x7FFFFFFF。如果你确实想要把这个字节当成无符号数来右移必须先 0xFF把高位清干净再做移位。这个模式在解析二进制协议、计算校验和、处理 UTF-8 字节序列时几乎是标配。4.21 31是负数1L 31才是正数int a 1 31; // -2147483648 long b 1L 31; // 2147483648 long c 1 31; // -2147483648先算完 int 再拓宽救不回来第三行是最阴的变量声明成了long看起来应该能装下2147483648但右边整个表达式先在int域里算完了溢出已经发生之后拓宽只是把一个负数变成同样数值的long。处理 64 位掩码时同理千万不要写1 63那个结果在int里是1 31因为移位量被 0x1F截成 31跟你想的完全不是一回事。正确的是1L 63。我的经验是只要掩码可能用到第 31 位及以上1后面就必须带L。这一条可以直接写进团队的代码规范。4.3 用long左移时移位数上限是 63 不是 31前面说过左操作数是long时移位量按 0x3F取模。这意味着1L 64等于1L1L 65等于2L。如果代码里用循环变量控制移位而循环上界是靠位数算出来的很容易在 64 这个位置上撞车。4.4 从字节流拼 32 位整数时 0xFF一个都不能少int value ((data[0] 0xFF) 24) | ((data[1] 0xFF) 16) | ((data[2] 0xFF) 8) | (data[3] 0xFF);假设data[1]是(byte) 0x80也就是-128。如果少了 0xFF-128 16会得到0xFF800000跟前面已经放好的高字节一或整个高 8 位全被污染结果从0x12800000变成0xFF800000。有意思的是最后那个字节其实可以省掉 0xFF因为它的高位本来就会被或运算忽略。但我在实际代码里从来不省——统一写法的可读性和一致性比省两个字符重要得多而且以后改字段顺序时也不容易漏。5. 工程代码里移位运算符的真实落点5.1 哈希扰动与容量对齐两个教科书级的位运算第一个是HashMap里的扰动函数static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }它的动机是桶下标计算用的是(n - 1) hash而n是 2 的幂且不超过2^30所以下标只用到hash的低位。如果hashCode的实现里低位区分度不高比如只用到了低位做递增高位信息就完全浪费了。把h无符号右移 16 位再异或回低位相当于让高 16 位也参与到下标计算里。为什么用而不是因为会把符号位复制到高 16 位如果hashCode是负数扰动后的高半部会全变成 1这等于凭空引入了一种结构性偏置。用得到的是一份干净的无符号高半部。第二个是容量向上取整到 2 的幂static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }这段代码的巧妙之处在于步长的倍增。第一步把最高的 1 后面一位填成 1此时顶部有连续 2 个 1第二步移 2 位顶部变成连续 4 个 1第三步 8 个第四步 16 个第五步 32 个。5 次操作覆盖 32 位因为2^5 32这是指数逼近。理解了这个套路你自己写把一个数低位全部填 1时就不会再傻乎乎地循环 32 次了。同样的思路用在long上需要一路写到 32。5.2 位图与 BitSet用移位代替除法和取模java.util.BitSet内部用long[]存位寻址逻辑就是移位的标准应用public void set(int bitIndex) { int wordIndex bitIndex 6; // 等价于 / 64 words[wordIndex] | 1L bitIndex; // 1L (bitIndex 63) }bitIndex 6是除以 641L bitIndex里隐含的bitIndex 0x3F是模 64。这里用还是都行因为bitIndex必须非负。但用1L而不是1就很关键——用1的话第 32 位以上全部算错。我在用户标签、每日签到、活跃度统计这类场景里用位图用得比较多。千万级用户的签到状态按每位 1 bit 算一千万人一天 1.25 MB一年也才 450 MB 出头比一行行记录省了不止一个数量级。取某一位的状态用(words[i 6] (i 63)) 1L或者更省事的Long.numberOfTrailingZeros、Long.bitCount这些现成方法。5.3 权限位掩码int装 32 个开关long装 64 个public static final int READ 1 0; public static final int WRITE 1 1; public static final int DELETE 1 2; public static final int SHARE 1 3; int perm READ | WRITE; boolean canWrite (perm WRITE) ! 0; perm | DELETE; perm ~WRITE;这套写法的好处是增删查都是一次位运算而且可以把整个权限组合存成数据库的一个int字段读写都便宜。判断权限时一定要用! 0而不是 1因为perm WRITE的结果是2不是1写成 1会永远判断失败。超过 32 个标志位就换long超过 64 个就得考虑BitSet或者拆成多个字段。这里有一个很容易被忽略的副作用把权限掩码存进数据库再读出来时如果用了会做符号处理的方式打印或传输负数掩码比如用到了第 31 位可能会出问题。Java 里安全打印可以用Integer.toUnsignedString(perm)或者干脆约定最高几位不用。5.4 颜色通道与协议字段的拼装ARGB 颜色的打包和解包是另一个高频场景int argb (a 24) | (r 16) | (g 8) | b; int a2 (argb 24) 0xFF; int r2 (argb 16) 0xFF; int g2 (argb 8) 0xFF; int b2 argb 0xFF;这里 24和 24配合 0xFF的结果其实一样但用意图更清楚我要的是那 8 个数据位。写也没错只是需要读者自己知道后面有 0xFF兜底。再比如 IPv4 地址和整数的互转、UTF-8 变长编码里的续字节判断(b 0xC0) 0x80、Base64 每 3 字节拆成 4 个 6 位索引都是同一类操作。这些代码看多了会发现一个规律凡是要把若干小字段塞进一个大整数必然用到凡是要从大整数里抠出某一段必然用到加掩码。6. 一张表把跨语言差异钉死6.1 到底哪些语言有语言左移算术右移逻辑右移备注Java移位量按0x1F/0x3F取模C / C无对有符号数是实现定义越界移位未定义C#C# 11 起移位量同样取模JavaScript全部按 32 位处理BigInt无Python无任意精度右移即向下取整Go无有符号走算术、无符号走逻辑移位量无上限Rust无有wrapping_shl、checked_shl等显式变体Kotlinshlshrushr以中缀函数形式提供这张表里最需要注意的是 C/C它没有所以把有符号数当无符号处理必须显式转成无符号类型再做右移或者靠 0xFF之类的掩码自己清理高位。6.2 溢出与越界移位的行为差异场景JavaC/CJavaScriptPythonGo左移溢出静默回绕有符号是未定义按 32 位截断不会溢出静默回绕移位量 位宽取模后执行未定义取模后执行结果变成 0大数结果为 0 或按位填充移位量为负取模后执行未定义取模后执行抛异常运行时 panic负数右移保号或补 0由运算符决定实现定义通常是保号同 Java向下取整有符号保号把这张表背下来意义不大但你至少要知道只有 Java 和 JavaScript 这一路语言给了你越界不报错的静默取模行为其他语言要么报错要么未定义。所以在 Java/JS 里更依赖主动校验在 C/C 里更依赖防御性代码和不写越界移位。6.3 Python 和 Go 为什么没有这个烦恼Python 的整数是任意精度的1 1000就是一个 1000 位的整数不存在溢出概念。代价是它没法映射到单条 CPU 指令性能上比定长整数慢所以在需要极限性能的位运算场景里Python 通常会借助numpy的定长类型或者干脆换语言。Go 的选择是显式声明int8、uint32这些类型泾渭分明对无符号类型就是逻辑右移对有符号类型就是算术右移不需要额外的运算符。移位量没有上限var x uint8 1; x 8直接得到 0行为完全确定。这种设计在写底层协议代码时体验很好因为不需要记到底该用哪个大于号。7. 排查与验证我怎么快速确认一个移位结果7.1 打印二进制比打印十进制有用得多位运算出问题时看十进制数字基本看不出所以然。我习惯第一时间把它转成补齐的 32 位二进制。int x -5; String bits String.format(%32s, Integer.toBinaryString(x)).replace( , 0); System.out.println(bits); // 11111111111111111111111111111011console.log((-5 0).toString(2).padStart(32, 0)); // 11111111111111111111111111111011print(format(-5 0xFFFFFFFF, 032b)) # 11111111111111111111111111111011注意 Java 的Integer.toBinaryString对负数返回的是补码形式但不会补齐到 32 位所以要用长度格式化补零。上面 Java 那句里的格式化字符串用%32s就够了不需要额外转义。7.2 我固定检查的几个审查点每次代码审查看到移位运算符我会按这个顺序过一遍所有1 n里的1是不是应该写成1L特别是掩码可能用到第 31 位以上的场景。所有右移是不是应该用判断标准是左操作数是否可能为负以及负值时符号扩展是否是我想要的。所有对byte、short的移位前面有没有 0xFF或 0xFFFF清理高位移位量是变量吗如果是有没有夹紧到合法区间表达式里混用了移位和其他运算符吗有没有依赖优先级我倾向于全部加括号。移位量来自数组长度、配置项或用户输入时有没有可能超过 31 或者变成负数第 5 条值得单独说一句。移位运算符的优先级比加减法低比关系运算符和按位与高。也就是说int a 1 2 3; // 等价于 1 5 32不是 (1 2) 3 7 int b 0xFF 1 8; // 等价于 0xFF (1 8) 0这两行如果按直觉理解都很容易出错。我的做法是只要移位表达式里出现了别的运算符就无条件加括号不给自己和别人留推断优先级的负担。7.3 什么时候应该放弃移位运算最后说一下我自己的取舍标准。移位本质上是一种暴露底层表示的写法它省掉了除法和取模的开销但把这个数字是几进制、宽度是多少、符号怎么处理这些问题直接摆到了读者面前。我大概遵循这几条如果位本身就是需求掩码、位图、协议字段、颜色通道那就大方地用移位这时候用除法反而绕。如果只是乘以 2或除以 2直接用* 2、/ 2让 JIT 或编译器去决定要不要优化成移位。现代编译器对 2 的幂次乘除的优化已经非常成熟手写移位带来的性能收益基本可以忽略。如果是在循环体里做大量位运算先测再改。我见过不止一次用移位替换除法后性能反而下降的情况因为改变了数据依赖关系或者破坏了向量化机会。那次代码审查结束之后我把(low high) 1这一段单独抽出来做了一次团队分享重点讲了和在负数上的分叉。后来有人在项目里真的抓到了一个类似的 bug一个用计算分页偏移的地方当偏移量因为某种原因变成负数之后算出来的页号也变成了负数最终查了一个空结果集接口返回正常、日志没有异常只有用户反馈翻到某几页之后列表是空的。这类问题如果不理解符号扩展光看代码是看不出来的。