Java中数字位翻转的实现方法

[LOADING...]

1. 概述

位操作是编程中的一个基本概念，涉及对二进制数据的各个位进行处理。一种常见的操作是翻转整数中的所有位，即将每一个 0 变为 1，将每一个 1 变为 0。

在本教程中，我们将解释位翻转的含义，并探索几种在 Java 中翻转整数位的常用方法。为了保证内容的完整性，我们将涵盖翻转全部 32 位以及仅翻转有效位这两种情况。

2. 理解位翻转

在学习如何翻转整数中的位之前，最好先看一个直观的例子。

首先，考虑十进制数字 21，具体来说，是它的二进制表示：

$ java

我们的目标是反转每一位，使得每一个 0 变为 1，每一个 1 变为 0：

$ java

这对应于十进制值 10 (8+2)。

在这个转换过程中，原始数字中位置 i 处的每一位在结果中都会被反转。然而，这里有一个重要的区别：当我们翻转一个整数的全部 32 位（即其完整大小）时，结果与仅翻转有效位的结果是不同的。例如，由于采用了补码表示法，翻转整数 21 的全部 32 位会产生 -22，而仅翻转有效位（10101 -> 01010）则会得到 10。

在接下来的章节中，我们将详细探讨这两种情况。

3. 使用按位取反运算符

翻转位最直接的方法是使用按位取反运算符 ~。这个一元运算符会反转整数二进制表示中的每一位：

$ java

public static int flipAllBits(int n) {
    return ~n;
}

该运算符会翻转整数的全部 32 位。这意味着 ~ 会反转每一位，包括前导零，由于 Java 中采用了补码表示法，这会将正数变为负数。

让我们使用 JUnit 5 测试和 AssertJ 断言来验证结果：

$ java

@Test
void givenPositiveInteger_whenFlipAllBits_thenReturnsNegativeComplement() {
    assertThat(flipAllBits(21)).isEqualTo(-22);
    assertThat(flipAllBits(0)).isEqualTo(-1);
    assertThat(flipAllBits(-1)).isEqualTo(0);
}

正如我们所见，翻转 21 的全部 32 位得到的是 -22，而不是 10。这是因为 Java 的 int 类型是有符号 32 位整数。

为了从 21 得到 10 这样的结果，我们需要仅翻转有效位。接下来我们讨论这种情况。

4. 仅翻转有效位

在许多实际应用场景中，我们只想翻转数字二进制表示中实际使用的位，排除前导零。例如，翻转 21 (10101) 的有效位应该得到 10 (01010)。

4.1. 使用掩码结合位长度计算

这个思路很简单：我们创建一个在每个有效位位置上都为 1 的掩码，然后将该数字与此掩码进行异或 (XOR) 操作。异或操作仅会翻转掩码中对应位置为 1 的位：

$ java

public static int flipSignificantBits(int n) {
    if (n == 0) {
        return 0;
    }
    int bitLength = Integer.SIZE - Integer.numberOfLeadingZeros(n);
    int mask = (1 << bitLength) - 1;
    return n ^ mask;
}

首先，我们处理 n 为 0 的边界情况。然后，使用 Integer.numberOfLeadingZeros() 计算有效位的数量。利用这个值，我们通过将 1 向左移动 bitLength 位并减去 1 来创建一个掩码，这会得到一串与有效位长度相匹配的 1。

最后，异或操作 (^ ) 仅翻转有效位，因为与 1 进行异或会反转该位，而与 0 进行异或则保持不变。

让我们用测试来验证这一点：

$ java

@Test
void givenPositiveInteger_whenFlipSignificantBits_thenReturnsFlippedValue() {
    assertThat(flipSignificantBits(21)).isEqualTo(10);
    assertThat(flipSignificantBits(26)).isEqualTo(5);
    assertThat(flipSignificantBits(0)).isEqualTo(0);
    assertThat(flipSignificantBits(1)).isEqualTo(0);
    assertThat(flipSignificantBits(7)).isEqualTo(0);
}

为了说明这一点，让我们追踪 26（二进制 11010）的示例：

n        = 11010  (26)
mask     = 11111  (31)
n ^ mask = 00101  (5)

这种方法高效地仅翻转了有效位。

4.2. 使用 Integer.highestOneBit()

我们也可以使用内置的 Integer.highestOneBit() 方法来构建掩码。此方法返回一个仅设置了输入最高位的值：

$ java

public static int flipSignificantBitsUsingHighestOneBit(int n) {
    if (n == 0) {
        return 0;
    }
    int mask = (Integer.highestOneBit(n) << 1) - 1;
    return n ^ mask;
}

在这里，Integer.highestOneBit(n) 返回最高有效位的值。通过将其左移一位并减去 1，我们创建了一个在每个有效位上都有 1 的掩码。然后，再次与此掩码进行异或操作即可仅翻转这些位。

4.3. 使用按位取反和掩码

除了异或，我们还可以结合按位取反运算符和掩码来达到同样的结果：

$ java

public static int flipSignificantBitsUsingNot(int n) {
    if (n == 0) {
        return 0;
    }
    int bitLength = Integer.SIZE - Integer.numberOfLeadingZeros(n);
    int mask = (1 << bitLength) - 1;
    return ~n & mask;
}

该函数首先计算 n 的按位取反，这会翻转全部 32 位。然后，与掩码进行与操作会将有效位之外的所有位清零。简而言之，该结果等同于仅翻转有效位。

5. 替代方法

除了标准的位运算符外，还有其他一些非传统的方法可以翻转整数的全部 32 位。

5.1. 使用算术取反

由于采用了补码表示法，翻转 n 的所有位等同于计算 -n - 1：

$ java

public static int flipBitsArithmetic(int n) {
    return -n - 1;
}

这是因为在补码中，n 的取反等于按位取反加 1 (-n = ~n + 1)。因此，~n = -n - 1，这与按位取反运算符的结果相同。

5.2. 使用异或 -1

另一种翻转所有位的方法是将数字与 -1 进行异或。在二进制中，-1 表示为全 1（32 位中全是 1）。值得注意的是，~0 的结果也是 -1，因此两者可以互换使用：

$ java

public static int flipBitsXorMinusOne(int n) {
    return n ^ -1;
}

由于与 1 进行异或会翻转一位，因此与一个所有位都为 1 的值进行异或实际上会翻转整数中的每一位。这与 ~ 运算符产生的结果相同。

6. 结论

在本文中，我们探讨了在 Java 中翻转整数位的几种方法。我们从用于翻转全部 32 位的按位取反运算符开始。接下来，我们研究了使用异或和与操作仅翻转有效位的基于掩码的方法。最后，我们介绍了使用算术取反和异或的替代方法。

所有源代码均可在 GitHub 上找到。

分类导航

1. 概述

2. 理解位翻转

3. 使用按位取反运算符

4. 仅翻转有效位

4.1. 使用掩码结合位长度计算

4.2. 使用 Integer.highestOneBit()

4.3. 使用按位取反和掩码

5. 替代方法

5.1. 使用算术取反

5.2. 使用异或 -1

6. 结论