位运算为何能让一行代码抵十行循环从底层原理到LeetCode完整通关指南

假设你需要统计一个整数二进制表示中1的个数。最直观的想法是：转成二进制字符串，遍历统计每个字符——代码大概十行左右。但如果告诉你，用一行循环就能搞定，甚至不需要字符串转换呢？

int count = 0;
while (n != 0) {
    n &= (n - 1);  // 消除最低位的1
    count++;
}

这就是位运算的魅力：直接操作二进制位，用CPU原生指令完成复杂逻辑。在现代处理器上，一次位运算的时间开销与一次加法相当——都是纳秒级别。掌握位运算，不仅能让你在面试中脱颖而出，更能让你理解计算机最底层的工作原理。

计算机如何表示整数

理解位运算，首先要理解计算机如何存储整数。我们日常使用的是十进制，每位有0-9共十种可能。而计算机使用二进制，每位只有0和1两种可能。

一个32位整数在内存中就是一个32位的0/1序列。以数字13为例：

$$13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0 = 1101_2$$

在内存中表示为（假设为32位int）：

00000000 00000000 00000000 00001101

最低位（最右边）称为第0位，最高位（最左边）称为第31位。对于有符号整数，第31位是符号位：0表示正数，1表示负数。

负数通常使用补码表示。补码的定义是：将正数的所有位取反，然后加1。以-13为例：

 13: 00000000 00000000 00000000 00001101
取反: 11111111 11111111 11111111 11110010
加1: 11111111 11111111 11111111 11110011  ← 这就是-13

补码的设计有一个精妙之处：减法可以转化为加法。计算 $a - b$ 等价于计算 $a + (-b)$，而 $-b$ 就是 $b$ 的补码。这意味着CPU只需要实现加法器，就能同时处理加减法。

六种位运算符

Java提供了6种位运算符，分为三类：

位逻辑运算符

按位与 AND (&)：两个位都为1时结果才为1，否则为0。

  1101  (13)
& 1011  (11)
------
  1001  (9)

应用场景：掩码操作，提取特定位。例如 n & 0xFF 提取最低8位。

AND操作示意图

图片来源: Wikipedia - Bitwise operation

按位或 OR (|)：两个位只要有一个为1，结果就为1。

  1101  (13)
| 1011  (11)
------
  1111  (15)

应用场景：设置特定位。例如 n | (1 << 5) 将第5位设为1。

OR操作示意图

图片来源: Wikipedia - Bitwise operation

按位异或 XOR (^)：两个位不同时结果为1，相同时为0。

  1101  (13)
^ 1011  (11)
------
  0110  (6)

异或有几个重要性质：

自反性：$a \oplus a = 0$
恒等性：$a \oplus 0 = a$
交换律和结合律

应用场景：交换变量、找出唯一出现一次的数、简单加密。

按位取反 NOT (~)：将每一位翻转，0变1，1变0。

~  00001101  (13)
------
  11110010  (-14，用补码解释)

注意：由于Java使用补码，~n 等于 -n - 1。

移位运算符

左移 <<：将所有位向左移动指定位数，低位补0。

13 << 2:
  00001101  (13)
<<      2
----------
  00110100  (52)

左移n位相当于乘以 $2^n$：$13 \times 2^2 = 52$。

有符号右移 >>：将所有位向右移动，高位用符号位填充（正数补0，负数补1）。

-13 >> 2:
  11110011  (-13)
>>       2
----------
  11111100  (-4)

有符号右移n位相当于除以 $2^n$ 并向下取整。

无符号右移 >>>：将所有位向右移动，高位始终补0。

-13 >>> 2:
  11111111 11111111 11111111 11110011  (-13)
>>>                              2
--------------------------------------
  00111111 11111111 11111111 11111100  (1073741820)

无符号右移不考虑符号位，常用于处理哈希值或与无符号数交互的场景。

移位操作示意图

图片来源: Wikipedia - Bitwise operation

三个核心技巧

位运算的精髓在于几个"魔术公式"，掌握它们就能解决大部分位运算题目。

技巧一：n & (n - 1) 消除最低位的1

这是Brian Kernighan在《C程序设计语言》中介绍的经典技巧。n - 1 会将n的最低位1变成0，同时将该位右边的所有0变成1。与原数做AND运算，就只消除了最低位的1。

n:     1011000
n-1:   1010111
n&(n-1):1010000  ← 最低位的1消失了

应用：

// 统计1的个数
int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

// 判断是否为2的幂
boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

2的幂的二进制表示只有一个1，例如 $8 = 1000_2$，$16 = 10000_2$。消除这个1后结果为0，正好可以用来判断。

技巧二：n & (-n) 获取最低位的1

-n 在补码表示下等于 ~n + 1。当n与-n做AND运算时，只有最低位的1会被保留。

n:   1011000
-n:  0101000  (补码表示)
&:   0001000  ← 只有最低位的1保留下来

这个技巧称为 lowbit，在树状数组等数据结构中广泛应用。

应用：

// 获取最低位1代表的值
int lowbit(int n) {
    return n & (-n);
}

// 判断是否为2的幂（另一种写法）
boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (-n)) == n;
}

技巧三：异或的消消乐性质

异或运算有一个重要性质：相同的数异或结果为0，任何数与0异或结果不变。

$$a \oplus a = 0$$

$$a \oplus 0 = a$$

推论：如果有偶数个相同数做异或，结果为0；奇数个相同数做异或，结果为该数本身。

应用：

// 交换两个变量（不需要临时变量）
void swap(int a, int b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

// 找出数组中只出现一次的数
int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

LeetCode 题目分类精讲

一、位计数问题

LeetCode 191. 位1的个数

题目：编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数。

思路：使用 n & (n - 1) 技巧，每次消除一个1，计数器加1。

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
}

复杂度：时间 $O(k)$，k为1的个数；空间 $O(1)$。

LeetCode 338. 比特位计数

题目：给定一个非负整数 n，对于 0 ≤ i ≤ n 的每个 i，计算其二进制表示中 1 的个数，返回一个数组。

思路：动态规划 + 位运算。观察到：

如果 i 是偶数，dp[i] = dp[i >> 1]（右移一位，相当于除以2）
如果 i 是奇数，dp[i] = dp[i >> 1] + 1

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
}

复杂度：时间 $O(n)$，空间 $O(n)$。

LeetCode 461. 汉明距离

题目：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

思路：先异或，再统计1的个数。

class Solution {
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int count = 0;
        while (xor != 0) {
            xor &= (xor - 1);
            count++;
        }
        return count;
    }
}

复杂度：时间 $O(1)$（整数最多32位），空间 $O(1)$。

LeetCode 477. 汉明距离总和

题目：计算一个数组中所有数对之间的汉明距离总和。

思路：逐位统计。对于每一位，假设数组中有 c 个数该位为1，则该位贡献的汉明距离为 $c \times (n - c)$。

class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0;
        int n = nums.length;
        
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                if ((num >> i & 1) == 1) {
                    count++;
                }
            }
            total += count * (n - count);
        }
        
        return total;
    }
}

复杂度：时间 $O(32n) = O(n)$，空间 $O(1)$。

二、判断问题

LeetCode 231. 2的幂

题目：给定一个整数，判断它是否是 2 的幂次方。

思路：2的幂只有一个1，使用 n & (n - 1) == 0 判断。注意处理负数和0。

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

LeetCode 326. 3的幂

题目：判断一个整数是否是 3 的幂次方。

思路：3的幂不能像2的幂那样用位运算直接判断，但可以用数学方法：在32位整数范围内，最大的3的幂是 $3^{19} = 1162261467$，如果 n 是3的幂，则 $1162261467$ 一定能被 n 整除。

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

LeetCode 693. 交替位二进制数

题目：给定一个正整数，检查它的二进制表示是否是交替的01串（没有相邻相同的位）。

思路：如果n是交替位，则 n ^ (n >> 1) 的结果所有位都是1。检查这个结果加1后是否是2的幂。

class Solution {
    public boolean hasAlternatingBits(int n) {
        int xor = n ^ (n >> 1);
        return (xor & (xor + 1)) == 0;
    }
}

三、异或应用问题

LeetCode 136. 只出现一次的数字

题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

思路：利用异或的消消乐性质，所有出现两次的数异或后为0，剩下的就是只出现一次的数。

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

复杂度：时间 $O(n)$，空间 $O(1)$。

LeetCode 137. 只出现一次的数字 II

题目：给定一个整数数组，除了某个元素只出现一次以外，其余每个元素均出现三次。找出那个只出现了一次的元素。

思路：逐位统计。对于每一位，统计所有数该位上1的个数，模3的余数就是答案该位的值。

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                if ((num >> i & 1) == 1) {
                    count++;
                }
            }
            if (count % 3 != 0) {
                result |= (1 << i);
            }
        }
        return result;
    }
}

进阶解法：使用状态机，将空间优化到 $O(1)$：

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}

状态机原理：用两个变量记录每位出现次数模3的结果，ones记录出现1次的位，twos记录出现2次的位。

LeetCode 260. 只出现一次的数字 III

题目：给定一个整数数组，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出那两个只出现一次的元素。

思路：

先全部异或，得到两个目标数的异或值
找到异或值中任意一个为1的位（说明两个数在该位不同）
根据该位将数组分成两组，每组包含一个目标数
分别异或得到两个目标数

class Solution {
    public int[] singleNumber(int[] nums) {
        // 第一步：求所有数的异或
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        
        // 第二步：找到任意一个为1的位
        int diff = xor & (-xor);  // lowbit
        
        // 第三步：分组异或
        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & diff) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        
        return new int[]{a, b};
    }
}

复杂度：时间 $O(n)$，空间 $O(1)$。

四、位操作问题

LeetCode 190. 颠倒二进制位

题目：颠倒给定的 32 位无符号整数的二进制位。

思路：分治思想，依次交换16位、8位、4位、2位、1位的块。

public class Solution {
    public int reverseBits(int n) {
        n = (n >>> 16) | (n << 16);
        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
        return n;
    }
}

掩码解释：

0xff00ff00：每16位块内的前8位
0xf0f0f0f0：每8位块内的前4位
0xcccccccc：每4位块内的前2位（二进制 1100）
0xaaaaaaaa：每2位块内的前1位（二进制 1010）

LeetCode 476. 数字的补数

题目：给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

思路：找到最高位的1，构造一个全是1的掩码，然后异或。

class Solution {
    public int findComplement(int num) {
        int mask = 1;
        while (mask < num) {
            mask = (mask << 1) | 1;
        }
        return num ^ mask;
    }
}

或者用更简洁的方式：

class Solution {
    public int findComplement(int num) {
        int highestOneBit = Integer.highestOneBit(num);
        int mask = (highestOneBit << 1) - 1;
        return num ^ mask;
    }
}

LeetCode 371. 两整数之和

题目：不使用运算符 + 和 -，计算两整数 a 和 b 之和。

思路：用位运算模拟加法。异或得到不考虑进位的和，AND后左移得到进位。循环直到没有进位。

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;  // 进位
            a = a ^ b;                  // 不考虑进位的和
            b = carry;                  // 进位加到下一次
        }
        return a;
    }
}

原理分析：二进制加法的本质是：

每位的和（不考虑进位）= 异或结果
每位的进位 = AND结果左移一位

例如 $13 + 11$：

  1101 (13)
+ 1011 (11)
--------
  0110 (异或，不考虑进位)
 10010 (AND左移，进位)
--------
 11000 (继续异或)
00010 (新的进位)
--------
 11010 (最终结果 24)

五、子集生成问题

LeetCode 78. 子集

题目：给定一组不含重复元素的整数数组，返回该数组所有可能的子集。

思路：n个元素的子集有 $2^n$ 个，可以用n位二进制数表示每个子集的选择情况。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }
        
        return result;
    }
}

复杂度：时间 $O(n \times 2^n)$，空间 $O(n)$（不计输出）。

LeetCode 201. 数字范围按位与

题目：给定范围 [m, n]，返回该范围内所有数字按位与的结果。

思路：找到m和n的公共前缀。将m和n不断右移，直到相等，记录移动次数。最后左移回来。

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            shift++;
        }
        return m << shift;
    }
}

原理：当m和n在某位不同时，该位及更低位在范围内必然会经历0和1，AND结果必为0。只有公共前缀部分能保持不变。

位运算在实际工程中的应用

位运算不仅仅是面试技巧，在实际工程中有着广泛的应用。

权限系统

Unix文件权限（读4、写2、执行1）是位运算的经典应用：

// 定义权限
int READ = 1 << 2;    // 100 = 4
int WRITE = 1 << 1;   // 010 = 2
int EXECUTE = 1 << 0; // 001 = 1

// 组合权限
int permission = READ | WRITE;  // 110 = 6

// 检查权限
boolean canRead = (permission & READ) != 0;
boolean canExecute = (permission & EXECUTE) != 0;

// 添加权限
permission |= EXECUTE;

// 移除权限
permission &= ~WRITE;

状态压缩

在游戏开发中，角色的状态（是否跳跃、是否攻击、是否受伤等）可以用一个整数表示：

int IDLE = 0;
int JUMPING = 1 << 0;
int ATTACKING = 1 << 1;
int HURT = 1 << 2;

int state = IDLE;

// 开始跳跃
state |= JUMPING;

// 同时跳跃和攻击
state |= JUMPING | ATTACKING;

// 检查是否正在跳跃
boolean isJumping = (state & JUMPING) != 0;

// 结束跳跃
state &= ~JUMPING;

布隆过滤器

布隆过滤器使用位数组存储元素存在性信息，插入和查询都是位运算操作：

// 设置第i位为1
void setBit(long[] bits, int i) {
    bits[i / 64] |= (1L << (i % 64));
}

// 检查第i位是否为1
boolean getBit(long[] bits, int i) {
    return (bits[i / 64] & (1L << (i % 64))) != 0;
}

图像处理

RGB颜色值通常用24位整数表示，位运算可以高效提取和修改颜色分量：

int color = 0xFF8040;  // RGB(255, 128, 64)

int red = (color >> 16) & 0xFF;    // 255
int green = (color >> 8) & 0xFF;   // 128
int blue = color & 0xFF;           // 64

// 组合新颜色
int newColor = (red << 16) | (green << 8) | blue;

常见陷阱与注意事项

移位溢出

在Java中，左移操作不会自动检测溢出：

int x = 1 << 31;  // -2147483648，变成负数
int y = 1 << 32;  // 1，因为只有低5位有效（对int来说）

对于long类型，只有低6位有效。

优先级问题

位运算的优先级很低，容易出错：

// 错误：== 优先级高于 &
if (n & 1 == 1) { ... }

// 正确
if ((n & 1) == 1) { ... }

负数的右移

有符号右移会保留符号位：

int x = -1;
x >>= 1;  // 还是-1，因为符号位不断补1

如果需要逻辑右移，使用 >>>。

复杂度对比总结

题目	暴力解法	位运算解法	提升效果
位1的个数	$O(32)$ 或 $O(\log n)$	$O(k)$，k为1的个数	常数优化
2的幂	$O(\log n)$ 循环除法	$O(1)$	降维打击
Single Number	$O(n)$ 哈希表	$O(n)$ 位运算	空间 $O(n) \to O(1)$
两数之和	直接用 +	位运算模拟	不用算术运算符
子集	递归回溯	位掩举	代码更简洁

参考资料

Wikipedia. Bitwise operation. https://en.wikipedia.org/wiki/Bitwise_operation
LeetCode. Bit Manipulation Problem List. https://leetcode.com/problem-list/bit-manipulation/
GeeksforGeeks. Bits manipulation (Important tactics). https://www.geeksforgeeks.org/dsa/bits-manipulation-important-tactics/
CP-Algorithms. Bit manipulation. https://cp-algorithms.com/algebra/bit-manipulation.html
Oracle. Bitwise and Bit Shift Operators. https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html
Kernighan, B. W., & Ritchie, D. M. The C Programming Language, 2nd Edition.
Baeldung. Bitwise Operators in Java. https://www.baeldung.com/java-bitwise-operators

计算机如何表示整数#

六种位运算符#

位逻辑运算符#

移位运算符#

三个核心技巧#

技巧一：n & (n - 1) 消除最低位的1#

技巧二：n & (-n) 获取最低位的1#

技巧三：异或的消消乐性质#

LeetCode 题目分类精讲#

一、位计数问题#

LeetCode 191. 位1的个数#

LeetCode 338. 比特位计数#

LeetCode 461. 汉明距离#

LeetCode 477. 汉明距离总和#

二、判断问题#

LeetCode 231. 2的幂#

LeetCode 326. 3的幂#

LeetCode 693. 交替位二进制数#

三、异或应用问题#

LeetCode 136. 只出现一次的数字#

LeetCode 137. 只出现一次的数字 II#

LeetCode 260. 只出现一次的数字 III#

四、位操作问题#

LeetCode 190. 颠倒二进制位#

LeetCode 476. 数字的补数#

LeetCode 371. 两整数之和#

五、子集生成问题#

LeetCode 78. 子集#

LeetCode 201. 数字范围按位与#

位运算在实际工程中的应用#

权限系统#

状态压缩#

布隆过滤器#

图像处理#

常见陷阱与注意事项#

移位溢出#

优先级问题#

负数的右移#

复杂度对比总结#

参考资料#

更多精彩内容

扫描线算法如何将二维问题降维成一维从天际线到矩形面积的LeetCode完整通关指南

最长公共子序列为何能解决十几类LeetCode问题从字符串相似度到DNA比对的动态规划精髓

链表算法为何让无数开发者头疼从指针陷阱到快慢指针的完整LeetCode通关指南

单调队列算法如何在滑动窗口中保持O(n)时间复杂度

背包问题为何成为动态规划的基石从01背包到完全背包的完整LeetCode通关指南

计算机如何表示整数

六种位运算符

位逻辑运算符

移位运算符

三个核心技巧

技巧一：n & (n - 1) 消除最低位的1

技巧二：n & (-n) 获取最低位的1

技巧三：异或的消消乐性质

LeetCode 题目分类精讲

一、位计数问题

LeetCode 191. 位1的个数

LeetCode 338. 比特位计数

LeetCode 461. 汉明距离

LeetCode 477. 汉明距离总和

二、判断问题

LeetCode 231. 2的幂

LeetCode 326. 3的幂

LeetCode 693. 交替位二进制数

三、异或应用问题

LeetCode 136. 只出现一次的数字

LeetCode 137. 只出现一次的数字 II

LeetCode 260. 只出现一次的数字 III

四、位操作问题

LeetCode 190. 颠倒二进制位

LeetCode 476. 数字的补数

LeetCode 371. 两整数之和

五、子集生成问题

LeetCode 78. 子集

LeetCode 201. 数字范围按位与

位运算在实际工程中的应用

权限系统

状态压缩

布隆过滤器

图像处理

常见陷阱与注意事项

移位溢出

优先级问题

负数的右移

复杂度对比总结

参考资料