位运算技巧详解：从基础到实战全攻略

位运算技巧详解：从基础到实战全攻略

前言

位运算是程序设计中一种非常重要的优化技巧，它直接操作二进制位，执行效率极高。本文将系统介绍位运算的常见技巧和经典应用，包括位运算基础、位图实现以及用位运算实现加减乘除等高级技巧。

一、位运算基础技巧

1.1 判断是否是2的幂

核心思想：2的幂在二进制中只会有一位上为1，其余位上均为0。因此提取最右侧的1后如果与原数字相等则为2的幂。

LeetCode题目：Power of Two

class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && n == (n & (–n));
}
};

复杂度分析：

• 时间复杂度：O(1)
• 空间复杂度：O(1)

1.2 判断是否为3的幂

核心思想：在int范围内，最大的3的幂是1162261467。如果n是3的幂，那么1162261467一定能被n整除。

LeetCode题目：Power of Three

class Solution {
public:
bool isPowerOfThree(int n) {
// 1162261467是int类型中最大的3的幂
return (n > 0 && 1162261467 % n == 0);
}
};

复杂度分析：

• 时间复杂度：O(1)
• 空间复杂度：O(1)

1.3 返回大于等于n的最小的2的幂

核心思想：通过一系列的位或运算，将最高位的1之后的所有位都变成1，然后加1即可得到下一个2的幂。

int near2Power(int n) {
if (n <= 0) {
return 1;
}
n—; // 当n为2的幂时要减1，不然不会返回其本身而是返回比它大的2的幂

n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n + 1;
}

算法解释：

举例：n为 00101100，n–为 00100011
n右移1位为 00010001
与n或 00110011
n右移2位或n为 00111111
…
将最左的1之后的位都变为1，再加1即为所求

复杂度分析：

• 时间复杂度：O(1)
• 空间复杂度：O(1)

1.4 区间按位与（Brian Kernighan算法）

问题描述：给定区间 [left, right]，返回此区间内所有数字按位与的结果。

LeetCode题目：Bitwise AND of Numbers Range

核心算法：「Brian Kernighan 算法」，用于清除二进制串中最右边的1。

算法原理：

• Brian Kernighan算法的关键在于每次对 number 和 number-1 之间进行按位与运算后，number 中最右边的1会被抹去变成0
• 对于给定的范围 [m, n]（m < n），我们对数字n迭代地应用上述技巧，清除最右边的1，直到它小于或等于m
• 此时非公共前缀部分的1均被消去，最后返回n即可

class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
while (m < n) {
// 抹去最右边的1
n = n & (n – 1);
}
return n;
}
};

复杂度分析：

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

1.5 逆序二进制

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

LeetCode题目：Reverse Bits

核心思想：分而治之，把数字分为两半，然后交换这两半的顺序；再把前后两个半段都分成两半，交换内部顺序……直至最后交换的数字只有1位。

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

复杂度分析：

• 时间复杂度：O(1)
• 空间复杂度：O(1)

1.6 统计二进制中1的个数（汉明距离）

问题描述：计算两个整数之间的汉明距离（对应二进制位不同的位置的数目）。

LeetCode题目：Hamming Distance

方法一：分组统计法

算法原理：

举例说明：

• 八位数：11111010
• 与01010101相与后为 01010000（统计奇数位的1）
• 原数右移1位（01111101）再与01010101相与为 01010101（统计偶数位的1）
• 两个结果相加为 10 10 01 01（每两位表示对应位置1的个数）

class Solution {
public:
int hammingDistance(int x, int y) {
return cntOnes(x ^ y);
}

int cntOnes(int n) {
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
return n;
}
};

方法二：Brian Kernighan算法

class Solution {
public:
int hammingDistance(int x, int y) {
int n = x ^ y;
int ret = 0;
while (n) {
n &= n – 1; // 消除最右边的1
ret++;
}
return ret;
}
};

方法三：系统内置函数

class Solution {
public:
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
};

复杂度分析：

• 时间复杂度：O(1) 或 O(k)，k为1的个数
• 空间复杂度：O(1)

二、位图的设计与实现

2.1 除法向上取整技巧

对于a和b都是非负数的情况：

// 除法向上取整
(a + b – 1) / b;

2.2 位图的基本实现

位图（BitMap）是一种用于快速查找、判断数据是否存在的数据结构，每个bit位代表一个数字。

class bitMap {
public:
bitMap(int n) {
bit.resize((n + 31) / 32, 0);
}

void add(int n) {
bit[n / 32] |= 1 << (n % 32);
}

void remove(int n) {
bit[n / 32] &= ~(1 << (n % 32));
}

void reverse(int n) {
bit[n / 32] ^= 1 << (n % 32);
}

bool contain(int n) {
return (((bit[n / 32] >> (n % 32)) & 1) == 1);
}

private:
vector<int> bit; // 存储位
};

设计要点：

• 使用整型数组存储，每个int存储32个bit
• n/32 确定在哪个int中
• n%32 确定在该int的哪一位

2.3 实现Bitset类（LeetCode高级题）

问题描述：设计一个Bitset类，支持以下操作：

• Bitset(int size)：初始化size个位，全部为0
• void fix(int idx)：将idx位置设为1
• void unfix(int idx)：将idx位置设为0
• void flip()：翻转所有位
• boolean all()：检查是否全为1
• boolean one()：检查是否至少有一个1
• int count()：返回值为1的位数
• String toString()：返回当前组成情况

LeetCode题目：Design Bitset

核心优化：使用反转标志位避免真实翻转所有bit，实现O(1)的flip操作。

class Bitset {
private:
vector<int> set;
bool reverse;
int ones;
int zores;
int size;

public:
Bitset(int size) {
set.resize((size + 31) / 32, 0);
reverse = false;
ones = 0;
zores = size;
this->size = size;
}

void fix(int idx) {
int index = idx / 32;
int bit = idx % 32;
if (!reverse) {
if (((set[index]) & (1 << bit)) == 0) {
set[index] |= (1 << bit);
zores—;
ones++;
}
} else {
if (((set[index]) & (1 << bit)) != 0) {
set[index] ^= (1 << bit);
zores—;
ones++;
}
}
}

void unfix(int idx) {
int index = idx / 32;
int bit = idx % 32;
if (!reverse) {
if (((set[index] & (1 << bit))) != 0) {
set[index] ^= (1 << bit);
zores++;
ones—;
}
} else {
if ((set[index] & (1 << bit)) == 0) {
set[index] |= (1 << bit);
zores++;
ones—;
}
}
}

void flip() {
reverse = !reverse;
int temp = zores;
zores = ones;
ones = temp;
}

bool all() {
return size == ones;
}

bool one() {
return ones > 0;
}

int count() {
return ones;
}

string toString() {
int indexs = (size + 31) / 32;
string str = "";
for (int i = 0; i < indexs; i++) {
int number = set[i];
for (int j = 0; j < 32 && (i * 32 + j) < size; j++) {
int status = (number >> j) & 1;
status ^= reverse ? 1 : 0;
str.append(to_string(status));
}
}
return str;
}
};

复杂度分析：

• fix/unfix/flip/all/one/count：O(1)
• toString：O(size)

三、位运算实现四则运算

3.1 位运算实现加法

核心思想：

• a ^ b 得到不含进位的和
• (a & b) << 1 得到进位
• 重复上述过程直到没有进位

int add(int a, int b) {
while (b != 0) {
int ans = a ^ b;
b = (a & b) << 1;
a = ans;
}
return a;
}

3.2 位运算实现减法

核心思想：减法等价于加上一个数的相反数，相反数 = ~b + 1

int sub(int a, int b) {
return add(a, add(~b, 1));
}

3.3 位运算实现乘法

核心思想：a不断左移，b右移；当b的最右位为1时，将当前的a累加到结果中。

int mul(int a, int b) {
int ans = 0;
while (b != 0) {
if (b & 1) {
ans = add(ans, a);
}
a <<= 1;
b >>= 1;
}
return ans;
}

3.4 位运算实现除法

核心思想：不断尝试a是否大于等于b×2^n，大于则做差并在结果的对应位设置1。为避免溢出，改为a右移n位与b比较。

LeetCode题目：Divide Two Integers

class BitCalculator {
public:
int add(int a, int b) {
while (b != 0) {
int ans = a ^ b;
b = (a & b) << 1;
a = ans;
}
return a;
}

int sub(int a, int b) {
return add(a, add(~b, 1));
}

int mul(int a, int b) {
int ans = 0;
while (b != 0) {
if (b & 1) {
ans = add(ans, a);
}
a <<= 1;
b >>= 1;
}
return ans;
}

int neg(int a) {
return add(~a, 1);
}

int div(int a, int b) {
int x = a < 0 ? neg(a) : a;
int y = b < 0 ? neg(b) : b;
int ans = 0;
for (int i = 30; i >= 0; i = sub(i, 1)) {
if ((x >> i) >= y) {
ans |= (1 << i);
x = sub(x, y << i);
}
}
return ((a > 0) ^ (b > 0)) ? neg(ans) : ans;
}

// 处理INT_MIN特殊情况
int minDiv(int a, int b) {
if (a == INT_MIN && b == INT_MIN) {
return 1;
}
if (a != INT_MIN && b != INT_MIN) {
return div(a, b);
}
if (b == INT_MIN) {
return 0;
}
// a==INT_MIN b==-1时返回INT_MAX
if (b == neg(1)) {
return INT_MAX;
}
// a==INT_MIN b!=-1
a = add(a, b > 0 ? b : neg(b));
int ans = div(a, b);
int offset = b > 0 ? neg(1) : 1;
return add(ans, offset);
}
};

边界处理：

• INT_MIN的特殊处理
• 除数为-1的溢出处理

总结

本文系统介绍了位运算的三大应用场景：

位运算的优势：

• 运算速度快（直接操作二进制）
• 节省空间（位图）
• 代码简洁（一行解决问题）

学习建议：

• 理解每种位运算的本质含义
• 掌握常见位运算技巧的模板
• 多做相关LeetCode题目巩固

希望本文能帮助你掌握位运算这一重要技能！

参考资料：

• LeetCode位运算题集
• 算法可视化演示

关键字：位运算、Brian Kernighan算法、位图、Bitset、汉明距离、LeetCode

如果本文对你有帮助，欢迎点赞收藏！有任何问题欢迎在评论区讨论交流。