位运算算法题合集

# 只出现一次的数字 I / II / III

# 191 (136) 异或 a⊕a=0

public int singleNumber(int[] nums) { int r=0; for(int n:nums) r^=n; return r; }

Python: return reduce(xor, nums)

# 192 (137) 每个出现3次

public int singleNumber(int[] nums) { int o=0,t=0; for(int n:nums){ o=(o^n)&~t; t=(t^n)&~o; } return o; }

# 193 (260) 两个出现1次

public int[] singleNumber(int[] nums) { int x=0; for(int n:nums) x^=n; int m=x&-x,a=0; for(int n:nums) if((n&m)!=0) a^=n; return new int[]{a,x^a}; }

核心：xor & -xor 取最低位1，据此将数组分为两组。

复杂度：O(N)/O(1)。

# O002 只出现一次的数字 II

LeetCode 137 · ⭐⭐ · 位统计 / 状态机

# 01. 题目

[2,2,3,2] → 3。每个数字出现3次，唯一个出现1次。

# 02. 代码

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

1
2
3
4
5
6
7
8

Python：

def singleNumber(self, nums):
    ones = twos = 0
    for n in nums:
        ones = (ones ^ n) & ~twos
        twos = (twos ^ n) & ~ones
    return ones

1
2
3
4
5
6

复杂度：O(N)/O(1)。

相关：O001 出现一次、O003 出现一次III

# O003 只出现一次的数字 III

LeetCode 260 · ⭐⭐ · 异或+分组

# 01. 题目

[1,2,1,3,2,5] → [3,5]。两个出现一次，其余两次。

# 02. 分析

全体异或 = a⊕b。取 mask = xor & -xor（最低位1）。根据 mask 将数组分为两组，每组各含一个目标数字。

# 03. 代码

public int[] singleNumber(int[] nums) {
    int xor=0; for(int n:nums) xor^=n;
    int mask=xor&-xor, a=0;
    for(int n:nums) if((n&mask)==0) a^=n;
    return new int[]{a, xor^a};
}

1
2
3
4
5
6

Python：

def singleNumber(self, nums):
    xor = reduce(xor, nums)
    mask = xor & -xor
    a = reduce(xor, (n for n in nums if n & mask))
    return [a, xor ^ a]

1
2
3
4
5

复杂度：O(N)/O(1)。

# 位运算技巧集 (O004-O010)

# 194 2的幂 (231)

n>0 && (n&(n-1))==0 — 消最低位1后为0。

# 195 位1的个数 (191)

while(n!=0){ n&=n-1; cnt++; } — 每次消一个最低位1。

# 196 颠倒二进制位 (190)

public int reverseBits(int n) { int r=0; for(int i=0;i<32;i++){ r=(r<<1)|(n&1); n>>>=1; } return r; }

Python: int(bin(n)[2:].zfill(32)[::-1],2)

# 197 数字范围按位与 (201)

等价于找 m 和 n 的公共前缀。while(m<n){ m>>=1; n>>=1; s++; } return m<<s;

# 198 两整数之和 (371)

while(b!=0){ int c=(a&b)<<1; a^=b; b=c; } return a; — 异或=本位和，与运算<<1=进位。

# 199 汉明距离 (461)

Integer.bitCount(x^y) — 不同位=1。

# 200 比特位计数 (338)

dp[i]=dp[i>>1]+(i&1)

# 位运算核心技巧

操作	代码	用途
消最低位1	`n&(n-1)`	判2的幂、统计1
取最低位1	`n&-n`	分组
异或	`a^b`	去重、求和

# O005 位1的个数

LeetCode 191 · ⭐ · n & (n-1)

# 01. 题目

统计二进制中1的个数。11(1011) → 3。

# 02. 分析

n & (n-1) 消除最低位1。循环直到n=0。

# 03. 代码

Java：

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

Python：

def hammingWeight(self, n: int) -> int: return bin(n).count('1')

C++：

int hammingWeight(uint32_t n) { return __builtin_popcount(n); }

复杂度：O(k)/O(1)，k为1的个数。

相关：O004 2的幂、O009 汉明距离

# O006 颠倒二进制位

LeetCode 190 · ⭐ · 逐位反转

# 01. 题目

颠倒32位无符号整数的二进制位。

# 02. 代码

Java：

public int reverseBits(int n) {
    int r=0; for(int i=0;i<32;i++){ r=(r<<1)|(n&1); n>>>=1; } return r;
}

1
2
3

Python：

def reverseBits(self, n: int) -> int:
    return int(bin(n)[2:].zfill(32)[::-1], 2)

1
2

C++：

uint32_t reverseBits(uint32_t n) {
    uint32_t r=0; for(int i=0;i<32;i++){ r=(r<<1)|(n&1); n>>=1; } return r;
}

1
2
3

复杂度：O(1)。

# O007 数字范围按位与

LeetCode 201 · ⭐⭐ · 公共前缀

# 01. 题目

[5,7] → 4。5(101) & 6(110) & 7(111) = 4(100)。

# 02. 分析

等价于找 m 和 n 的二进制公共前缀。

Java：

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

1
2
3
4

Python：

def rangeBitwiseAnd(self, m: int, n: int) -> int:
    shift = 0
    while m < n: m >>= 1; n >>= 1; shift += 1
    return m << shift

1
2
3
4

复杂度：O(1)。

# O008 两整数之和

LeetCode 371 · ⭐⭐ · 位运算模拟加法

# 01. 题目

不用 + - * / 计算两整数之和。

# 02. 分析

a^b = 本位和（无进位），(a&b)<<1 = 进位。循环直到进位为0。

# 03. 代码

Java：

public int getSum(int a, int b) { while(b!=0){ int c=(a&b)<<1; a^=b; b=c; } return a; }

Python：

def getSum(self, a: int, b: int) -> int:
    mask = 0xffffffff
    while b: a, b = (a^b)&mask, ((a&b)<<1)&mask
    return a if a <= 0x7fffffff else ~(a^mask)

1
2
3
4

C++：

int getSum(int a, int b) { while(b){ int c=(unsigned)(a&b)<<1; a^=b; b=c; } return a; }

复杂度：O(1)/O(1)。

# O009 汉明距离

LeetCode 461 · ⭐ · 异或+位计数

# 01. 题目

两个整数的汉明距离 = 二进制位不同的位置数。1(001) vs 4(100) → 2。

# 02. 代码

Java：Integer.bitCount(x ^ y) Python：bin(x ^ y).count('1') C++：__builtin_popcount(x ^ y)

复杂度：O(1)。

# O010 比特位计数

LeetCode 338 · ⭐ · DP+位运算

# 01. 题目

对 0≤i≤n 每个数，计算其二进制中1的个数。n=5 → [0,1,1,2,1,2]

# 02. 分析

$$dp[i] = dp[i >> 1] + (i & 1)$$

# 03. 代码

Java：

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;
}

1
2
3
4
5

Python：

def countBits(self, n):
    dp=[0]*(n+1)
    for i in range(1,n+1): dp[i]=dp[i>>1]+(i&1)
    return dp

1
2
3
4

复杂度：O(N)/O(N)。