尧图网站建设 
1. 项目概述为什么Java开发者必须掌握位运算如果你是一名Java开发者尤其是工作1-3年的朋友面试时被问到“HashMap的容量为什么是2的幂次方”或者“如何高效地判断一个整数的奇偶性”你是否能立刻从底层原理层面给出答案又或者当你看到一些开源框架比如Netty、Disruptor或JDK源码中那些充斥着、|、、的代码时是否感到一阵头大觉得这是“天书”这正是我写这篇长文的原因。位运算这个看似古老、底层甚至有些“过时”的话题恰恰是区分普通码农和资深工程师的一道分水岭。它不常出现在业务逻辑里却深深扎根于性能核心、算法优化和系统设计的土壤中。很多人觉得它难是因为教材和大多数教程只讲了“是什么”运算符的含义却很少讲“为什么用”和“怎么用得好”。结果就是大家背下了是按位与但永远想不到用它来替代% 2判断奇偶性能能提升一个数量级。我自己在早期做高频交易系统时为了榨干每一纳秒的性能不得不深入研究位运算。从用(n (n-1)) 0来判断一个数是否是2的幂到用异或^来找数组中只出现一次的数字再到理解ReentrantReadWriteLock中如何用一个int变量同时维护读锁和写锁的状态——每一次突破都让我对Java乃至计算机系统的理解更深一层。这篇文章就是我这些年踩坑、实践、优化的经验总结。我的目标不是让你死记硬背运算符而是带你像使用加减乘除一样自然而然地想到并运用位运算来解决实际问题。我们会从最基础的二进制和补码讲起这是所有位运算的基石必须夯实然后逐一拆解六大位运算符最后深入到JDK源码、算法实战和性能优化场景。无论你是正在备战面试还是希望写出更高效、更优雅的代码这篇文章都将是你工具箱里一件趁手的利器。2. 基石彻底理解二进制与补码在开始挥舞位运算这把“手术刀”之前我们必须先了解它要操作的“肌体”——数据在计算机内存中的真实形态。很多对位运算的误解都源于对二进制和补码的一知半解。2.1 二进制计算机世界的通用语言计算机的所有操作最终都归结为对0和1的运算。一个二进制位bit是信息的最小单位8个bit构成一个字节byte。Java中的基本数据类型如int、long在内存中就是以连续的二进制位序列存储的。例如十进制数5在Java的int类型32位中表示为00000000 00000000 00000000 00000101而-5呢它并不是简单地把最高位变成1100...0101这种直接加符号位的表示法称为“原码”它有一个致命缺点存在两个零0和-0并且加减法运算电路设计会非常复杂。为了解决这个问题现代计算机普遍采用补码。2.2 补码负数的“魔法”表示法补码的定义是正数的补码是其本身负数的补码是其绝对值的二进制表示按位取反后加1。我们来一步步推导-5的补码5的二进制原码00000101假设8位简写按位取反11111010加111111011所以在8位系统中-5的补码就是11111011。补码的精妙之处在于统一的零0和-0的补码都是00000000。无缝的加减法减法可以转化为加法。5 - 3等价于5 (-3)。在补码体系下直接对5的补码和-3的补码做加法丢弃最高位的溢出就能得到正确结果的补码。这极大地简化了CPU算术逻辑单元的设计。实操心得在Java中查看一个整数的二进制补码最直观的方法是使用Integer.toBinaryString()方法。但要注意这个方法对于负数会输出其32位补码形式对于int。例如Integer.toBinaryString(-5)会输出一串很长的“1”开头后跟011的字符串这正是-5的32位补码前面的“1”是高位符号位的扩展。2.3 Java中数据类型的位宽了解位宽是进行位操作的前提否则你可能会遇到意想不到的符号扩展问题。byte: 8位short: 16位int:32位最常用long: 64位char: 16位无符号当对不同位宽的类型进行位运算时Java会进行二进制数字提升如果操作数是byte、short或char在运算前会被提升为int类型。这也是为什么下面这段代码会编译报错byte a 0b00000101; // 5 byte b 0b00000011; // 3 byte c a b; // 编译错误因为 a b 的结果是 int 类型 byte c (byte) (a b); // 必须强制转换注意事项进行位运算时心里要始终清楚你操作的数据的位宽。特别是与byte、short打交道时警惕因类型提升导致的意外结果或必须的强制类型转换。3. 六大位运算符深度解析与实战掌握了补码我们就可以正式认识位运算的六种“武器”了。我会为每个运算符配上清晰的二进制演算、实用的代码示例以及最重要的——它们在实际开发中的典型应用场景。3.1 按位与屏蔽与提取的利器运算规则两位同时为1结果才为1否则为0。1 1 1 1 0 0 0 1 0 0 0 0实战示例1奇偶性判断判断一个整数n是奇数还是偶数。常规做法是n % 2 0。但取模运算%比位运算慢得多。原理二进制中奇数的最低位永远是1偶数的最低位永远是0。操作n 1如果结果为0则n是偶数。如果结果为1则n是奇数。boolean isEven (n 1) 0; // 性能远优于 n % 2 0实战示例2掩码操作与状态标志位这是最经典的应用。假设我们用一个8位的byte或int的低8位来表示一个用户的权限每一位代表一种权限如第0位读第1位写第2位执行。final byte READ_PERM 0b00000001; // 1 0 final byte WRITE_PERM 0b00000010; // 1 1 final byte EXECUTE_PERM 0b00000100; // 1 2 byte userPermission 0b00000101; // 用户拥有读和执行权限 // 检查是否拥有写权限 boolean canWrite (userPermission WRITE_PERM) ! 0; // false // 检查是否拥有读权限 boolean canRead (userPermission READ_PERM) ! 0; // true // 移除执行权限清空特定位 userPermission ~EXECUTE_PERM; // userPermission 变为 0b00000001核心技巧操作可以看作一个过滤器。用一个掩码mask去和原数做掩码中为1的位会被保留为0的位会被清零。~是按位取反运算符~EXECUTE_PERM得到0b11111011再与userPermission相与就将第2位清零了。3.2 按位或|合并与设置的利器运算规则两位只要有一个为1结果就为1。1 | 1 1 1 | 0 1 0 | 1 1 0 | 0 0实战示例设置状态标志位承接上面的权限例子如果要给用户添加写权限。// 添加写权限设置特定位 userPermission | WRITE_PERM; // userPermission 变为 0b00000111|操作可以将原数中指定的位掩码为1的位强制设为1而其他位保持不变。组合应用实现一个简单的位标志工具类public class PermissionManager { private int flags 0; public void enable(int flag) { flags | flag; } public void disable(int flag) { flags ~flag; } public boolean isEnabled(int flag) { return (flags flag) ! 0; } public void toggle(int flag) { flags ^ flag; // 异或下文会讲 } } // 使用 PermissionManager mgr new PermissionManager(); mgr.enable(READ_PERM | WRITE_PERM); // 一次性启用多个权限3.3 按位异或^找不同与加密的利器运算规则两位相同为0相异为1。1 ^ 1 0 1 ^ 0 1 0 ^ 1 1 0 ^ 0 0异或有几个非常重要的数学性质是解题的关键归零律a ^ a 0恒等律a ^ 0 a交换律和结合律a ^ b b ^ a,(a ^ b) ^ c a ^ (b ^ c)自反性a ^ b ^ b a因为a ^ b ^ b a ^ (b ^ b) a ^ 0 a实战示例1交换两个变量的值无需临时变量int a 5, b 10; a a ^ b; // a 现在为 15 (5 ^ 10) b a ^ b; // b 15 ^ 10 5 (归零律和恒等律) a a ^ b; // a 15 ^ 5 10 System.out.println(a a , b b); // a10, b5虽然现代编译器优化后这种技巧的性能优势已不明显但它充分展示了异或的自反性是理解异或的绝佳例子。实战示例2找出数组中唯一不重复的元素LeetCode 136题目给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现一次的元素。public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; // 利用 a ^ a 0 和 a ^ 0 a } return result; }原理由于异或满足交换律和结合律数组中所有成对出现的数字异或后都会变成0a^a0最后0与那个唯一的数字异或结果就是该数字本身0^bb。时间复杂度O(n)空间复杂度O(1)极其优雅。实战示例3最简单的对称加密// 加密和解密使用同一个密钥key int data 12345; int key 98765; int encrypted data ^ key; // 加密 int decrypted encrypted ^ key; // 解密decrypted data注意事项异或加密Vernam cipher在密钥真随机、长度不小于明文、且一次一密时是理论上绝对安全的。但这里的简单实现密钥固定且短绝对不安全切勿用于真实加密仅作原理演示。3.4 按位取反~逐位翻转运算规则一元运算符将操作数的每一位取反0变11变0。~1 0 ~0 1例如~5假设8位5-00000101~5-11111010这是-6的补码重要理解~n等价于-n - 1。因为补码体系中一个数与其按位取反再加1互为相反数。即~n 1 -n。实战应用常与结合用于创建掩码如前文userPermission ~EXECUTE_PERM;用于清除特定位。3.5 左移乘以2的幂运算规则将操作数的所有位向左移动指定的位数低位补0高位溢出丢弃。int a 5; // 二进制 101 int b a 2; // 二进制 10100即 20数学意义a n等价于a * (2^n)。左移一位相当于乘以2。实战应用快速计算2的幂1 n可以快速得到2^n。在HashMap源码中计算容量时大量使用。构建掩码如前文的READ_PERM 1 0。这种方式比直接写二进制常量更清晰不易出错。警告对于int类型左移时如果导致符号位最高位发生变化结果可能出乎意料尤其是左移超过31位时。对于long类型是63位。(a n)当n 32对于int时实际移动位数是n % 32。3.6 右移 和 除以2的幂与逻辑右移右移有两种极易混淆算术右移向右移动高位补符号位。即正数补0负数补1。其数学意义是向下取整的除法a n约等于a / (2^n)。int a 8; // ...0001000 int b a 2; // ...0000010即 2 (8 / 4) int c -8; // 补码表示 int d c 2; // 高位补1结果仍是负数值为 -2 (-8 / 4)逻辑右移向右移动高位一律补0。对于正数效果与相同对于负数会将其当作无符号数处理移动后变成一个很大的正数。int a -8; int b a 2; // 结果是一个很大的正数 (1073741822)应用场景用于带符号数的快速除以2的幂。当你需要将整数值纯粹当作位模式处理而不关心其符号意义时使用。例如在计算哈希码或处理颜色值ARGB时。4. 源码级实战位运算在JDK中的精妙应用理解了基本操作我们来看看大师们JDK开发者是如何在实战中运用位运算的。阅读源码是提升位运算理解的最佳途径。4.1 HashMap如何实现高效的取模与扩容HashMap中根据key的哈希值决定元素落在哪个数组桶bucket里核心计算是index hash(key) (table.length - 1)。为什么用而不是%前提是table.length必须是2的幂HashMap的构造函数和扩容机制保证了这一点。当length是2的幂时length - 1的二进制形式就是一串连续的1例如length16, length-115 - 二进制 01111。hash % length取模运算在CPU层面的开销远大于位运算。hash (length - 1)效果等价于取模但速度极快。因为操作只是简单地保留哈希值的低几位。扩容机制中的位运算HashMap扩容时默认2倍旧桶中的元素要么留在原索引j要么移动到新索引j oldCap。判断条件非常巧妙// 在JDK 1.8的resize方法中 if ((e.hash oldCap) 0) { // 留在原索引 j } else { // 移动到新索引 j oldCap }原理因为oldCap是2的幂只有一位是1比如16是10000。e.hash oldCap的结果实际上就是检查e.hash在oldCap那个对应位上是0还是1。如果是0说明该元素的新索引低位和旧索引一样如果是1则新索引需要加上oldCap。这个判断一次位运算搞定效率极高。4.2 ThreadPoolExecutor如何用一个int管理线程池状态ThreadPoolExecutor使用一个AtomicInteger类型的变量ctl来同时存储线程池运行状态runState和工作线程数量workerCount。private final AtomicInteger ctl new AtomicInteger(ctlOf(RUNNING, 0)); private static final int COUNT_BITS Integer.SIZE - 3; // 29 private static final int CAPACITY (1 COUNT_BITS) - 1; // 低29位掩码约5亿 // 运行状态存储在高3位 private static final int RUNNING -1 COUNT_BITS; private static final int SHUTDOWN 0 COUNT_BITS; private static final int STOP 1 COUNT_BITS; private static final int TIDYING 2 COUNT_BITS; private static final int TERMINATED 3 COUNT_BITS; // 打包与解包方法 private static int runStateOf(int c) { return c ~CAPACITY; } // 获取高3位状态 private static int workerCountOf(int c) { return c CAPACITY; } // 获取低29位数量 private static int ctlOf(int rs, int wc) { return rs | wc; } // 合并状态和数量精妙之处空间极致利用一个int32位被拆成高3位状态和低29位数量避免了使用两个变量带来的原子性管理难题。操作高效原子通过ctl.getAndIncrement()等原子操作可以同时安全地修改线程数量而状态判断通过位掩码快速提取。状态比较有序运行状态值RUNNING SHUTDOWN STOP TIDYING TERMINATED可以通过直接比较runStateOf(ctl)的大小来判断状态转换是否合法。4.3 Integer.bitCount如何快速计算一个int中1的个数Integer.bitCount(int i)方法返回指定int值的二进制补码表示形式中的1的位数。它的实现不是我们想象的逐位循环而是采用了堪称“魔法”的位操作算法汉明重量算法。public static int bitCount(int i) { // HD, Figure 5-2 i i - ((i 1) 0x55555555); i (i 0x33333333) ((i 2) 0x33333333); i (i (i 4)) 0x0f0f0f0f; i i (i 8); i i (i 16); return i 0x3f; }算法思路分治并行计算0x555555550101...将每2位作为一个单元计算其中1的个数结果00,01,10。0x333333330011...将上一步的结果每2组合并计算每4位中1的个数。0x0f0f0f0f00001111...继续合并计算每8位中1的个数。最后通过移位相加将8位的结果累加到32位并取低6位因为32位最多32个16位足够表示。这种算法的时间复杂度是O(log₂(位宽))在32位CPU上通常只需十几条指令比循环32次要快得多。这是空间换时间和利用CPU并行计算能力的经典范例。5. 算法与优化实战位运算解题套路掌握了基础知识和源码思维我们来看一些经典的算法问题位运算往往能提供时间复杂度O(n)、空间复杂度O(1)的极致解法。5.1 判断一个数是否是2的幂问题给定一个整数n判断它是否是2的幂如1,2,4,8,...。常规思路循环除以2。位运算思路观察2的幂的二进制形式1 - 1,2 - 10,4 - 100,8 - 1000。它们共同的特点是只有最高位是1其余位都是0。那么n-1呢1-10(0),2-11(01),4-13(011),8-17(0111)。发现规律n (n-1)的结果会把n最低位的1变成0。对于2的幂它只有一个1所以n (n-1)的结果必然是0。同时要排除n0的情况。boolean isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }扩展n (n - 1)这个操作本身非常有用它可以将整数n的二进制表示中最右边的1变为0。常用于计算一个数的二进制中1的个数不断执行n n (n-1)直到n0次数即为1的个数。判断一个数是否是2的幂如上。找出一个数二进制中最低位的1所对应的值lowbit n -n利用了补码的特性。5.2 找出只出现一次的数字升级版问题LeetCode 137给定一个整数数组除了某个元素只出现一次以外其余每个元素均出现三次。找出那个只出现一次的元素。要求时间复杂度O(n)空间复杂度O(1)。思路如果所有数字都出现三次那么每一位上1出现的次数总和一定是3的倍数。现在有一个数只出现一次那么对于每一位统计所有数字在该位为1的次数这个次数除以3的余数只能是0或1就是只出现一次的数字在该位的值。public int singleNumber(int[] nums) { int result 0; for (int i 0; i 32; i) { // int有32位 int sum 0; for (int num : nums) { // 统计第i位是否为1 sum (num i) 1; } // 如果该位的和不是3的倍数则只出现一次的数在该位为1 if (sum % 3 ! 0) { result | (1 i); // 使用 | 操作设置该位为1 } } return result; }这个方法可以推广到“除一个数字出现一次其他数字出现k次”的问题。5.3 使用BitSet进行海量数据去重与排序java.util.BitSet类底层就是用long数组实现的位向量。它非常适合处理大规模布尔值标记的场景例如海量整数去重如果有10亿个整数范围在0~20亿用HashSet内存可能扛不住。但如果只是判断存在性可以用一个BitSet每一位代表一个数是否存在。20亿位大约需要250MB内存比HashSet小得多。简单排序遍历数据将对应位设为true最后再遍历BitSet输出为true的索引就得到了排序结果仅限于非负整数且范围不大的情况。// 示例统计0-100万之间随机数的存在情况 BitSet bitSet new BitSet(1_000_001); Random rand new Random(); for (int i 0; i 100000; i) { bitSet.set(rand.nextInt(1_000_001)); } // 检查某个数是否存在 boolean exists bitSet.get(123456); // 获取第一个被设置为true的位最小存在的数 int firstSetBit bitSet.nextSetBit(0); // 获取所有存在的数遍历 for (int i bitSet.nextSetBit(0); i 0; i bitSet.nextSetBit(i1)) { System.out.println(i); }6. 性能对比与避坑指南位运算虽好但也不能滥用。理解其性能边界和潜在陷阱至关重要。6.1 性能对比实测我们用一个简单的例子对比位运算与算术运算的性能。任务是循环1亿次判断一个固定数的奇偶性。// 测试代码框架 public class PerformanceTest { public static void main(String[] args) { int n 123456789; int iterations 100_000_000; long start System.nanoTime(); for (int i 0; i iterations; i) { boolean result (n % 2 0); // 算术运算 } long time1 System.nanoTime() - start; start System.nanoTime(); for (int i 0; i iterations; i) { boolean result (n 1) 0; // 位运算 } long time2 System.nanoTime() - start; System.out.printf(取模运算耗时: %d ns%n, time1); System.out.printf(位运算耗时: %d ns%n, time2); System.out.printf(位运算比取模快 %.2f%%%n, (1 - (double)time2/time1)*100); } }在我的机器JDK 17上运行多次位运算通常比取模运算快20% ~ 50%。在极端性能敏感的循环或底层库中这种差异会被放大。但请注意现代JVM的JIT编译器非常智能对于简单的、可预测的运算它可能会进行优化。位运算的绝对优势体现在复杂的表达式或编译器无法优化的场景中。不要为了微小的、可读性差的优化而过度使用位运算。6.2 常见“坑”与注意事项运算符优先级陷阱位运算符的优先级通常低于比较运算符。例如if (a 1 0) { // 错误 优先级高于 // 本意是判断a是否为偶数 } // 正确写法 if ((a 1) 0) { }牢记位运算符优先级很低使用时务必加括号。符号位与移位左移右移时要时刻注意操作数的类型和符号。对负数进行右移会保持符号这可能不是你想要的结果。逻辑右移只对int和long有效。对byte、short、char进行移位时它们会先被提升为int再进行操作结果可能出乎意料需要强制转换。byte b -1; // 0xFF (补码) int i b 4; // b被提升为int 0xFFFFFFFF然后逻辑右移4位结果是0x0FFFFFFF byte result (byte)(b 4); // 强制转换后结果为0x0F错b4结果是int强转byte取低8位是0xFF // 正确做法先与掩码操作再移位 byte result (byte)((b 0xFF) 4); // 结果为0x0F可读性与维护性位运算就像一把锋利的匕首用得好一招制敌用不好伤到自己。在业务代码中如果一段位运算逻辑需要写注释才能让人看懂那就要考虑是否值得。优先保证代码的清晰可读在确有效能瓶颈且位运算能带来显著提升时再使用。例如用a 3代替a * 8虽然快但后者意图更明确。浮点数不支持位运算Java中不能直接对float和double进行位运算。如果需要对浮点数的二进制表示进行操作可以使用Float.floatToIntBits或Double.doubleToLongBits将其转换为整数类型操作后再转换回去。但这属于非常底层的操作通常只在特殊领域如图形学、科学计算使用。7. 总结与个人心得回顾整篇文章我们从二进制补码这个最基础的“地基”开始一层层搭建起了位运算的知识大厦。我们拆解了六大运算符的每一个细节不是为了记忆而是为了理解其背后的逻辑。我们深入HashMap和线程池的源码看到了位运算在工业级代码中是如何优雅地解决性能与设计难题的。我们也挑战了算法问题体验了位运算如何化繁为简用近乎“魔法”的方式达成最优解。我个人最深的体会是位运算不是一种孤立的技术而是一种思维方式。它是一种让你从“数值”视角切换到“位模式”视角的能力。当你看到% 2时能想到 1当你需要紧凑存储多个布尔状态时能想到int标志位当你需要极速计算时能想到代替乘法这种思维就建立起来了。最后给想深入掌握位运算的朋友几点建议多读源码JDK的java.util和java.util.concurrent包是学习位运算的最佳教材。BitSet,AtomicInteger, 各种并发工具类里都有宝藏。刻意练习去LeetCode上找“位运算”标签的题目从简单到中等不追求数量追求彻底理解每一道题的位操作原理。先清晰后优化在业务代码中永远把可读性放在第一位。只有在性能剖析Profiling证明某处是热点且位运算能带来明确收益时才进行替换并务必加上清晰的注释。位运算的世界远不止于此还有位段、布隆过滤器、位图索引等高级主题。但只要你扎实地掌握了本文的内容你就已经拥有了打开这扇大门的钥匙。剩下的就是在不断的实践中让这种思维成为你本能的一部分。当你下次再看到那些神秘的位操作代码时希望你的反应不再是畏惧而是会心一笑“哦原来是这个技巧。” Java位运算实战：从HashMap源码到算法优化，提升代码性能
1. 项目概述为什么Java开发者必须掌握位运算如果你是一名Java开发者尤其是工作1-3年的朋友面试时被问到“HashMap的容量为什么是2的幂次方”或者“如何高效地判断一个整数的奇偶性”你是否能立刻从底层原理层面给出答案又或者当你看到一些开源框架比如Netty、Disruptor或JDK源码中那些充斥着、|、、的代码时是否感到一阵头大觉得这是“天书”这正是我写这篇长文的原因。位运算这个看似古老、底层甚至有些“过时”的话题恰恰是区分普通码农和资深工程师的一道分水岭。它不常出现在业务逻辑里却深深扎根于性能核心、算法优化和系统设计的土壤中。很多人觉得它难是因为教材和大多数教程只讲了“是什么”运算符的含义却很少讲“为什么用”和“怎么用得好”。结果就是大家背下了是按位与但永远想不到用它来替代% 2判断奇偶性能能提升一个数量级。我自己在早期做高频交易系统时为了榨干每一纳秒的性能不得不深入研究位运算。从用(n (n-1)) 0来判断一个数是否是2的幂到用异或^来找数组中只出现一次的数字再到理解ReentrantReadWriteLock中如何用一个int变量同时维护读锁和写锁的状态——每一次突破都让我对Java乃至计算机系统的理解更深一层。这篇文章就是我这些年踩坑、实践、优化的经验总结。我的目标不是让你死记硬背运算符而是带你像使用加减乘除一样自然而然地想到并运用位运算来解决实际问题。我们会从最基础的二进制和补码讲起这是所有位运算的基石必须夯实然后逐一拆解六大位运算符最后深入到JDK源码、算法实战和性能优化场景。无论你是正在备战面试还是希望写出更高效、更优雅的代码这篇文章都将是你工具箱里一件趁手的利器。2. 基石彻底理解二进制与补码在开始挥舞位运算这把“手术刀”之前我们必须先了解它要操作的“肌体”——数据在计算机内存中的真实形态。很多对位运算的误解都源于对二进制和补码的一知半解。2.1 二进制计算机世界的通用语言计算机的所有操作最终都归结为对0和1的运算。一个二进制位bit是信息的最小单位8个bit构成一个字节byte。Java中的基本数据类型如int、long在内存中就是以连续的二进制位序列存储的。例如十进制数5在Java的int类型32位中表示为00000000 00000000 00000000 00000101而-5呢它并不是简单地把最高位变成1100...0101这种直接加符号位的表示法称为“原码”它有一个致命缺点存在两个零0和-0并且加减法运算电路设计会非常复杂。为了解决这个问题现代计算机普遍采用补码。2.2 补码负数的“魔法”表示法补码的定义是正数的补码是其本身负数的补码是其绝对值的二进制表示按位取反后加1。我们来一步步推导-5的补码5的二进制原码00000101假设8位简写按位取反11111010加111111011所以在8位系统中-5的补码就是11111011。补码的精妙之处在于统一的零0和-0的补码都是00000000。无缝的加减法减法可以转化为加法。5 - 3等价于5 (-3)。在补码体系下直接对5的补码和-3的补码做加法丢弃最高位的溢出就能得到正确结果的补码。这极大地简化了CPU算术逻辑单元的设计。实操心得在Java中查看一个整数的二进制补码最直观的方法是使用Integer.toBinaryString()方法。但要注意这个方法对于负数会输出其32位补码形式对于int。例如Integer.toBinaryString(-5)会输出一串很长的“1”开头后跟011的字符串这正是-5的32位补码前面的“1”是高位符号位的扩展。2.3 Java中数据类型的位宽了解位宽是进行位操作的前提否则你可能会遇到意想不到的符号扩展问题。byte: 8位short: 16位int:32位最常用long: 64位char: 16位无符号当对不同位宽的类型进行位运算时Java会进行二进制数字提升如果操作数是byte、short或char在运算前会被提升为int类型。这也是为什么下面这段代码会编译报错byte a 0b00000101; // 5 byte b 0b00000011; // 3 byte c a b; // 编译错误因为 a b 的结果是 int 类型 byte c (byte) (a b); // 必须强制转换注意事项进行位运算时心里要始终清楚你操作的数据的位宽。特别是与byte、short打交道时警惕因类型提升导致的意外结果或必须的强制类型转换。3. 六大位运算符深度解析与实战掌握了补码我们就可以正式认识位运算的六种“武器”了。我会为每个运算符配上清晰的二进制演算、实用的代码示例以及最重要的——它们在实际开发中的典型应用场景。3.1 按位与屏蔽与提取的利器运算规则两位同时为1结果才为1否则为0。1 1 1 1 0 0 0 1 0 0 0 0实战示例1奇偶性判断判断一个整数n是奇数还是偶数。常规做法是n % 2 0。但取模运算%比位运算慢得多。原理二进制中奇数的最低位永远是1偶数的最低位永远是0。操作n 1如果结果为0则n是偶数。如果结果为1则n是奇数。boolean isEven (n 1) 0; // 性能远优于 n % 2 0实战示例2掩码操作与状态标志位这是最经典的应用。假设我们用一个8位的byte或int的低8位来表示一个用户的权限每一位代表一种权限如第0位读第1位写第2位执行。final byte READ_PERM 0b00000001; // 1 0 final byte WRITE_PERM 0b00000010; // 1 1 final byte EXECUTE_PERM 0b00000100; // 1 2 byte userPermission 0b00000101; // 用户拥有读和执行权限 // 检查是否拥有写权限 boolean canWrite (userPermission WRITE_PERM) ! 0; // false // 检查是否拥有读权限 boolean canRead (userPermission READ_PERM) ! 0; // true // 移除执行权限清空特定位 userPermission ~EXECUTE_PERM; // userPermission 变为 0b00000001核心技巧操作可以看作一个过滤器。用一个掩码mask去和原数做掩码中为1的位会被保留为0的位会被清零。~是按位取反运算符~EXECUTE_PERM得到0b11111011再与userPermission相与就将第2位清零了。3.2 按位或|合并与设置的利器运算规则两位只要有一个为1结果就为1。1 | 1 1 1 | 0 1 0 | 1 1 0 | 0 0实战示例设置状态标志位承接上面的权限例子如果要给用户添加写权限。// 添加写权限设置特定位 userPermission | WRITE_PERM; // userPermission 变为 0b00000111|操作可以将原数中指定的位掩码为1的位强制设为1而其他位保持不变。组合应用实现一个简单的位标志工具类public class PermissionManager { private int flags 0; public void enable(int flag) { flags | flag; } public void disable(int flag) { flags ~flag; } public boolean isEnabled(int flag) { return (flags flag) ! 0; } public void toggle(int flag) { flags ^ flag; // 异或下文会讲 } } // 使用 PermissionManager mgr new PermissionManager(); mgr.enable(READ_PERM | WRITE_PERM); // 一次性启用多个权限3.3 按位异或^找不同与加密的利器运算规则两位相同为0相异为1。1 ^ 1 0 1 ^ 0 1 0 ^ 1 1 0 ^ 0 0异或有几个非常重要的数学性质是解题的关键归零律a ^ a 0恒等律a ^ 0 a交换律和结合律a ^ b b ^ a,(a ^ b) ^ c a ^ (b ^ c)自反性a ^ b ^ b a因为a ^ b ^ b a ^ (b ^ b) a ^ 0 a实战示例1交换两个变量的值无需临时变量int a 5, b 10; a a ^ b; // a 现在为 15 (5 ^ 10) b a ^ b; // b 15 ^ 10 5 (归零律和恒等律) a a ^ b; // a 15 ^ 5 10 System.out.println(a a , b b); // a10, b5虽然现代编译器优化后这种技巧的性能优势已不明显但它充分展示了异或的自反性是理解异或的绝佳例子。实战示例2找出数组中唯一不重复的元素LeetCode 136题目给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现一次的元素。public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; // 利用 a ^ a 0 和 a ^ 0 a } return result; }原理由于异或满足交换律和结合律数组中所有成对出现的数字异或后都会变成0a^a0最后0与那个唯一的数字异或结果就是该数字本身0^bb。时间复杂度O(n)空间复杂度O(1)极其优雅。实战示例3最简单的对称加密// 加密和解密使用同一个密钥key int data 12345; int key 98765; int encrypted data ^ key; // 加密 int decrypted encrypted ^ key; // 解密decrypted data注意事项异或加密Vernam cipher在密钥真随机、长度不小于明文、且一次一密时是理论上绝对安全的。但这里的简单实现密钥固定且短绝对不安全切勿用于真实加密仅作原理演示。3.4 按位取反~逐位翻转运算规则一元运算符将操作数的每一位取反0变11变0。~1 0 ~0 1例如~5假设8位5-00000101~5-11111010这是-6的补码重要理解~n等价于-n - 1。因为补码体系中一个数与其按位取反再加1互为相反数。即~n 1 -n。实战应用常与结合用于创建掩码如前文userPermission ~EXECUTE_PERM;用于清除特定位。3.5 左移乘以2的幂运算规则将操作数的所有位向左移动指定的位数低位补0高位溢出丢弃。int a 5; // 二进制 101 int b a 2; // 二进制 10100即 20数学意义a n等价于a * (2^n)。左移一位相当于乘以2。实战应用快速计算2的幂1 n可以快速得到2^n。在HashMap源码中计算容量时大量使用。构建掩码如前文的READ_PERM 1 0。这种方式比直接写二进制常量更清晰不易出错。警告对于int类型左移时如果导致符号位最高位发生变化结果可能出乎意料尤其是左移超过31位时。对于long类型是63位。(a n)当n 32对于int时实际移动位数是n % 32。3.6 右移 和 除以2的幂与逻辑右移右移有两种极易混淆算术右移向右移动高位补符号位。即正数补0负数补1。其数学意义是向下取整的除法a n约等于a / (2^n)。int a 8; // ...0001000 int b a 2; // ...0000010即 2 (8 / 4) int c -8; // 补码表示 int d c 2; // 高位补1结果仍是负数值为 -2 (-8 / 4)逻辑右移向右移动高位一律补0。对于正数效果与相同对于负数会将其当作无符号数处理移动后变成一个很大的正数。int a -8; int b a 2; // 结果是一个很大的正数 (1073741822)应用场景用于带符号数的快速除以2的幂。当你需要将整数值纯粹当作位模式处理而不关心其符号意义时使用。例如在计算哈希码或处理颜色值ARGB时。4. 源码级实战位运算在JDK中的精妙应用理解了基本操作我们来看看大师们JDK开发者是如何在实战中运用位运算的。阅读源码是提升位运算理解的最佳途径。4.1 HashMap如何实现高效的取模与扩容HashMap中根据key的哈希值决定元素落在哪个数组桶bucket里核心计算是index hash(key) (table.length - 1)。为什么用而不是%前提是table.length必须是2的幂HashMap的构造函数和扩容机制保证了这一点。当length是2的幂时length - 1的二进制形式就是一串连续的1例如length16, length-115 - 二进制 01111。hash % length取模运算在CPU层面的开销远大于位运算。hash (length - 1)效果等价于取模但速度极快。因为操作只是简单地保留哈希值的低几位。扩容机制中的位运算HashMap扩容时默认2倍旧桶中的元素要么留在原索引j要么移动到新索引j oldCap。判断条件非常巧妙// 在JDK 1.8的resize方法中 if ((e.hash oldCap) 0) { // 留在原索引 j } else { // 移动到新索引 j oldCap }原理因为oldCap是2的幂只有一位是1比如16是10000。e.hash oldCap的结果实际上就是检查e.hash在oldCap那个对应位上是0还是1。如果是0说明该元素的新索引低位和旧索引一样如果是1则新索引需要加上oldCap。这个判断一次位运算搞定效率极高。4.2 ThreadPoolExecutor如何用一个int管理线程池状态ThreadPoolExecutor使用一个AtomicInteger类型的变量ctl来同时存储线程池运行状态runState和工作线程数量workerCount。private final AtomicInteger ctl new AtomicInteger(ctlOf(RUNNING, 0)); private static final int COUNT_BITS Integer.SIZE - 3; // 29 private static final int CAPACITY (1 COUNT_BITS) - 1; // 低29位掩码约5亿 // 运行状态存储在高3位 private static final int RUNNING -1 COUNT_BITS; private static final int SHUTDOWN 0 COUNT_BITS; private static final int STOP 1 COUNT_BITS; private static final int TIDYING 2 COUNT_BITS; private static final int TERMINATED 3 COUNT_BITS; // 打包与解包方法 private static int runStateOf(int c) { return c ~CAPACITY; } // 获取高3位状态 private static int workerCountOf(int c) { return c CAPACITY; } // 获取低29位数量 private static int ctlOf(int rs, int wc) { return rs | wc; } // 合并状态和数量精妙之处空间极致利用一个int32位被拆成高3位状态和低29位数量避免了使用两个变量带来的原子性管理难题。操作高效原子通过ctl.getAndIncrement()等原子操作可以同时安全地修改线程数量而状态判断通过位掩码快速提取。状态比较有序运行状态值RUNNING SHUTDOWN STOP TIDYING TERMINATED可以通过直接比较runStateOf(ctl)的大小来判断状态转换是否合法。4.3 Integer.bitCount如何快速计算一个int中1的个数Integer.bitCount(int i)方法返回指定int值的二进制补码表示形式中的1的位数。它的实现不是我们想象的逐位循环而是采用了堪称“魔法”的位操作算法汉明重量算法。public static int bitCount(int i) { // HD, Figure 5-2 i i - ((i 1) 0x55555555); i (i 0x33333333) ((i 2) 0x33333333); i (i (i 4)) 0x0f0f0f0f; i i (i 8); i i (i 16); return i 0x3f; }算法思路分治并行计算0x555555550101...将每2位作为一个单元计算其中1的个数结果00,01,10。0x333333330011...将上一步的结果每2组合并计算每4位中1的个数。0x0f0f0f0f00001111...继续合并计算每8位中1的个数。最后通过移位相加将8位的结果累加到32位并取低6位因为32位最多32个16位足够表示。这种算法的时间复杂度是O(log₂(位宽))在32位CPU上通常只需十几条指令比循环32次要快得多。这是空间换时间和利用CPU并行计算能力的经典范例。5. 算法与优化实战位运算解题套路掌握了基础知识和源码思维我们来看一些经典的算法问题位运算往往能提供时间复杂度O(n)、空间复杂度O(1)的极致解法。5.1 判断一个数是否是2的幂问题给定一个整数n判断它是否是2的幂如1,2,4,8,...。常规思路循环除以2。位运算思路观察2的幂的二进制形式1 - 1,2 - 10,4 - 100,8 - 1000。它们共同的特点是只有最高位是1其余位都是0。那么n-1呢1-10(0),2-11(01),4-13(011),8-17(0111)。发现规律n (n-1)的结果会把n最低位的1变成0。对于2的幂它只有一个1所以n (n-1)的结果必然是0。同时要排除n0的情况。boolean isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }扩展n (n - 1)这个操作本身非常有用它可以将整数n的二进制表示中最右边的1变为0。常用于计算一个数的二进制中1的个数不断执行n n (n-1)直到n0次数即为1的个数。判断一个数是否是2的幂如上。找出一个数二进制中最低位的1所对应的值lowbit n -n利用了补码的特性。5.2 找出只出现一次的数字升级版问题LeetCode 137给定一个整数数组除了某个元素只出现一次以外其余每个元素均出现三次。找出那个只出现一次的元素。要求时间复杂度O(n)空间复杂度O(1)。思路如果所有数字都出现三次那么每一位上1出现的次数总和一定是3的倍数。现在有一个数只出现一次那么对于每一位统计所有数字在该位为1的次数这个次数除以3的余数只能是0或1就是只出现一次的数字在该位的值。public int singleNumber(int[] nums) { int result 0; for (int i 0; i 32; i) { // int有32位 int sum 0; for (int num : nums) { // 统计第i位是否为1 sum (num i) 1; } // 如果该位的和不是3的倍数则只出现一次的数在该位为1 if (sum % 3 ! 0) { result | (1 i); // 使用 | 操作设置该位为1 } } return result; }这个方法可以推广到“除一个数字出现一次其他数字出现k次”的问题。5.3 使用BitSet进行海量数据去重与排序java.util.BitSet类底层就是用long数组实现的位向量。它非常适合处理大规模布尔值标记的场景例如海量整数去重如果有10亿个整数范围在0~20亿用HashSet内存可能扛不住。但如果只是判断存在性可以用一个BitSet每一位代表一个数是否存在。20亿位大约需要250MB内存比HashSet小得多。简单排序遍历数据将对应位设为true最后再遍历BitSet输出为true的索引就得到了排序结果仅限于非负整数且范围不大的情况。// 示例统计0-100万之间随机数的存在情况 BitSet bitSet new BitSet(1_000_001); Random rand new Random(); for (int i 0; i 100000; i) { bitSet.set(rand.nextInt(1_000_001)); } // 检查某个数是否存在 boolean exists bitSet.get(123456); // 获取第一个被设置为true的位最小存在的数 int firstSetBit bitSet.nextSetBit(0); // 获取所有存在的数遍历 for (int i bitSet.nextSetBit(0); i 0; i bitSet.nextSetBit(i1)) { System.out.println(i); }6. 性能对比与避坑指南位运算虽好但也不能滥用。理解其性能边界和潜在陷阱至关重要。6.1 性能对比实测我们用一个简单的例子对比位运算与算术运算的性能。任务是循环1亿次判断一个固定数的奇偶性。// 测试代码框架 public class PerformanceTest { public static void main(String[] args) { int n 123456789; int iterations 100_000_000; long start System.nanoTime(); for (int i 0; i iterations; i) { boolean result (n % 2 0); // 算术运算 } long time1 System.nanoTime() - start; start System.nanoTime(); for (int i 0; i iterations; i) { boolean result (n 1) 0; // 位运算 } long time2 System.nanoTime() - start; System.out.printf(取模运算耗时: %d ns%n, time1); System.out.printf(位运算耗时: %d ns%n, time2); System.out.printf(位运算比取模快 %.2f%%%n, (1 - (double)time2/time1)*100); } }在我的机器JDK 17上运行多次位运算通常比取模运算快20% ~ 50%。在极端性能敏感的循环或底层库中这种差异会被放大。但请注意现代JVM的JIT编译器非常智能对于简单的、可预测的运算它可能会进行优化。位运算的绝对优势体现在复杂的表达式或编译器无法优化的场景中。不要为了微小的、可读性差的优化而过度使用位运算。6.2 常见“坑”与注意事项运算符优先级陷阱位运算符的优先级通常低于比较运算符。例如if (a 1 0) { // 错误 优先级高于 // 本意是判断a是否为偶数 } // 正确写法 if ((a 1) 0) { }牢记位运算符优先级很低使用时务必加括号。符号位与移位左移右移时要时刻注意操作数的类型和符号。对负数进行右移会保持符号这可能不是你想要的结果。逻辑右移只对int和long有效。对byte、short、char进行移位时它们会先被提升为int再进行操作结果可能出乎意料需要强制转换。byte b -1; // 0xFF (补码) int i b 4; // b被提升为int 0xFFFFFFFF然后逻辑右移4位结果是0x0FFFFFFF byte result (byte)(b 4); // 强制转换后结果为0x0F错b4结果是int强转byte取低8位是0xFF // 正确做法先与掩码操作再移位 byte result (byte)((b 0xFF) 4); // 结果为0x0F可读性与维护性位运算就像一把锋利的匕首用得好一招制敌用不好伤到自己。在业务代码中如果一段位运算逻辑需要写注释才能让人看懂那就要考虑是否值得。优先保证代码的清晰可读在确有效能瓶颈且位运算能带来显著提升时再使用。例如用a 3代替a * 8虽然快但后者意图更明确。浮点数不支持位运算Java中不能直接对float和double进行位运算。如果需要对浮点数的二进制表示进行操作可以使用Float.floatToIntBits或Double.doubleToLongBits将其转换为整数类型操作后再转换回去。但这属于非常底层的操作通常只在特殊领域如图形学、科学计算使用。7. 总结与个人心得回顾整篇文章我们从二进制补码这个最基础的“地基”开始一层层搭建起了位运算的知识大厦。我们拆解了六大运算符的每一个细节不是为了记忆而是为了理解其背后的逻辑。我们深入HashMap和线程池的源码看到了位运算在工业级代码中是如何优雅地解决性能与设计难题的。我们也挑战了算法问题体验了位运算如何化繁为简用近乎“魔法”的方式达成最优解。我个人最深的体会是位运算不是一种孤立的技术而是一种思维方式。它是一种让你从“数值”视角切换到“位模式”视角的能力。当你看到% 2时能想到 1当你需要紧凑存储多个布尔状态时能想到int标志位当你需要极速计算时能想到代替乘法这种思维就建立起来了。最后给想深入掌握位运算的朋友几点建议多读源码JDK的java.util和java.util.concurrent包是学习位运算的最佳教材。BitSet,AtomicInteger, 各种并发工具类里都有宝藏。刻意练习去LeetCode上找“位运算”标签的题目从简单到中等不追求数量追求彻底理解每一道题的位操作原理。先清晰后优化在业务代码中永远把可读性放在第一位。只有在性能剖析Profiling证明某处是热点且位运算能带来明确收益时才进行替换并务必加上清晰的注释。位运算的世界远不止于此还有位段、布隆过滤器、位图索引等高级主题。但只要你扎实地掌握了本文的内容你就已经拥有了打开这扇大门的钥匙。剩下的就是在不断的实践中让这种思维成为你本能的一部分。当你下次再看到那些神秘的位操作代码时希望你的反应不再是畏惧而是会心一笑“哦原来是这个技巧。”