---
title: "二进制操作"
created: 2025-12-20
---
# 二进制操作

在 Java 中，操作二进制主要有两种方式，取决于你的需求是**处理任意长度的位集合**（类似 C++ 的 `std::bitset`），还是**处理 32/64 位的整数位运算**（算法题常用）。

### 1. 对应 C++ `std::bitset` 的类：`java.util.BitSet`

这是 Java 官方提供的专门用于处理位向量的类。

与 C++ 的 bitset<N> 不同，Java 的 BitSet 是动态扩容的，不需要在编译时指定大小。

#### 常用 API 对照表

| **操作** | **C++ (std::bitset)** | **Java (java.util.BitSet)** |
| --- | --- | --- |
| **初始化** | `bitset<100> b;` | `BitSet b = new BitSet(100);` (注: 只是初始容量，会自动扩容) |
| **置位 (设为1)** | `b.set(5);` | `b.set(5);` |
| **清零 (设为0)** | `b.reset(5);` | `b.clear(5);` |
| **检查 (是否为1)** | `b.test(5);` 或 `b[5]` | `b.get(5);` (返回 boolean) |
| **翻转** | `b.flip(5);` | `b.flip(5);` |
| **统计 1 的个数** | `b.count();` | `b.cardinality();` |
| **判空 (全0)** | `b.none();` | `b.isEmpty();` |
| **总位数 (最高位+1)** | `N` (固定) | `b.length();` (返回最高设置位的索引 + 1) |
| **逻辑运算** | `&=`, ` | =`,` ^=` |

#### 代码示例

```java
import java.util.BitSet;

public class BitSetDemo {
    public static void main(String[] args) {
        // 创建一个 BitSet
        BitSet bits = new BitSet();

        // 1. 设置位 (Set)
        bits.set(2);  // 第2位设为1
        bits.set(5);  // 第5位设为1
        // 现在 bits 逻辑上是 ...00100100

        // 2. 获取位 (Get/Test)
        boolean bit2 = bits.get(2); // true
        boolean bit3 = bits.get(3); // false

        // 3. 翻转 (Flip)
        bits.flip(5); // 1 变 0

        // 4. 清除 (Clear/Reset)
        bits.clear(2); // 1 变 0

        // 5. 统计 1 的数量 (Count)
        bits.set(10);
        bits.set(20);
        System.out.println(bits.cardinality()); // 输出 2

        // 6. 集合运算 (And/Or/Xor)
        BitSet b2 = new BitSet();
        b2.set(10);
        bits.and(b2); // bits = bits & b2
    }
}
```

---

### 2. 原生整数位运算 (算法题/高性能场景)

如果你处理的数据不超过 64 位（例如 LeetCode 刷题），直接使用 `int` (32位) 或 `long` (64位) 配合**位运算符**是最高效的，这也是 C++ 选手的“老本行”。

Java 的位运算符与 C++ 几乎完全一致，唯独多了一个无符号右移。

#### 运算符列表

- `&` : 按位与
- `|` : 按位或
- `^` : 按位异或
- `~` : 按位取反
- `<<` : 左移
- `>>` : 有符号右移 (高位补符号位)
- `>>>` : **无符号右移** (Java 特有，高位恒补 0，相当于 C++ `unsigned int` 的右移)

#### 常用“骚操作” (与 C++ 一致)

```
int n = 0; // 这里的 n 就相当于一个 32位的 bitset

// 1. 将第 k 位设为 1
n |= (1 << k);

// 2. 将第 k 位设为 0
n &= ~(1 << k);

// 3. 检查第 k 位是否为 1
boolean isSet = (n & (1 << k)) != 0;

// 4. 翻转第 k 位
n ^= (1 << k);

// 5. 取出最右边的 1 (Lowbit)
int lowbit = n & -n;

// 6. 去掉最右边的 1 (n = n & (n-1))
n &= (n - 1);
```

---

### 3. 包装类的辅助工具 (Helper Methods)

Java 的 `Integer` 和 `Long` 类提供了很多静态方法来处理二进制，非常方便，不用自己造轮子。

```
int x = 10; // 二进制 1010

// 转二进制字符串 (C++ 需要自己写或调库)
String binaryStr = Integer.toBinaryString(x); // "1010"

// 统计 1 的个数 (相当于 C++ 的 __builtin_popcount)
int count = Integer.bitCount(x);

// 寻找最高位的 1 (Highest One Bit)
int high = Integer.highestOneBit(x); // 返回 8 (1000)

// 寻找最低位的 1 (Lowest One Bit)
int low = Integer.lowestOneBit(x);   // 返回 2 (0010)

// 统计前导 0 的个数 (Leading Zeros)
int zeros = Integer.numberOfLeadingZeros(x);
```

### 总结建议

1. **如果题目限制**\(N \le 64\)：不要用 `BitSet`，直接用 `long` 配合位运算 (`<<`, `&`, `|`)，效率最高，代码最少。
2. **如果题目**\(N\)**很大 (如**\(10^5\)**)**：使用 `java.util.BitSet`。
3. **如果需要处理超大整数位操作**：可以使用 `java.math.BigInteger` (它是不可变的，支持 `setBit`, `testBit` 等操作)。