Program to Invert Bits of a Number Efficiently in Java

翻转数字的位意味着将每个位从 0 翻转为 1，反之亦然。在 Java 中，可以使用按位非 (~) 运算符高效地实现此操作，该运算符直接在二进制级别执行翻转，为该任务提供了快速而直接的解决方案。

输入 5

输出 -6

解释

在 Java 中，整数以二的补码表示形式存储。翻转 5 的位会得到二进制 11111111 11111111 11111111 11111010，这在十进制中表示 -6。最高有效位表示一个负数，根据二的补码规则，将结果转换为 -6。

方法 1：使用按位非或按位翻转。

算法

步骤 1：理解问题：翻转数字的位意味着翻转每个 二进制 位。例如，1 变成 0，0 变成 1。此操作在 Java 中使用按位非 (~) 运算符执行，该运算符直接作用于数字的二进制表示。

步骤 1.1：理解二的补码表示：在二的补码表示中，正数按常规表示，而负数则通过翻转绝对值的各位并在此基础上加 1 来存储。这使得系统能够有效地表示正数和负数。理解这一点对于解释位翻转后的结果至关重要。

步骤 1.2：认识到翻转对带符号数的影响：当对带符号整数应用按位非运算符时，翻转不仅会翻转位，还会由于二的补码表示而改变数字的符号。

对于正数，这将导致一个负值；对于负数，它会变成正数或更负的值，具体取决于位模式。了解这一点可确保在翻转后准确解释结果。

步骤 2：定义输入：从给定的 整数 作为输入开始。作为演示，请考虑数字 5。这将是我们想要翻转其位的数字。

步骤 3：输入的二进制表示：将数字转换为其二进制形式以了解其内部表示。在 Java 中，整数以 32 位格式存储。对于 5，其二进制表示为：00000000 00000000 00000000 00000101。

步骤 4：应用按位非运算符 (~)：使用 ~ 运算符翻转位。此运算符翻转数字二进制表示中的所有位。将 ~ 应用于 5 后，其二进制变为：11111111 11111111 11111111 11111010。

步骤 4.1：观察按位翻转过程：当对数字应用按位非 (~) 运算符时，它会翻转每个单独的位。例如，如果数字是 5（二进制 00000000 00000000 00000000 00000101），应用 ~ 会将每个 0 更改为 1，每个 1 更改为 0，结果为 11111111 11111111 11111111 11111010。此翻转后的二进制值是翻转的结果。

步骤 5：在二的补码中解释结果：在 Java 中，整数以二的补码格式存储。这意味着最高有效位 (MSB) 表示数字的符号（0 为正，1 为负）。翻转位后，结果 11111111 11111111 11111111 11111010 在十进制中表示 -6。

步骤 5.1：确定翻转位的二的补码：翻转数字的位后，由于最高有效位设置为 1，结果的二进制可能表示一个负值。要正确解释这一点，我们使用二的补码规则将二进制值转换回十进制。这涉及将翻转后的位视为负数，并计算其十进制等效值，同时牢记符号位。

步骤 6：输出结果：显示原始数字及其翻转后的值。对于输入 5，由于二的补码表示，其二进制翻转会产生 -6。

步骤 7：使用不同输入验证结果：为了确保位翻转过程的正确性，请尝试对不同类型的数字（正数和负数）应用按位非运算符。

这有助于验证该方法的可靠性，并确保翻转对于各种输入都能按预期工作。例如，对 -5 应用按位非应返回 4，这证实了该方法能恰当地处理正数和负数。

文件名：BitInversion.java

输出

 
Original Number: 5
Inverted Number: -6   

复杂度分析

时间复杂度

程序的 time complexity 为 O(1)。该操作使用 按位 非 (~) 运算符，该运算符直接在硬件级别操作位。无论数字的大小或值如何，此过程都花费固定时间。

空间复杂度

程序的 space complexity 为 O(1)。该操作只需要固定的空间来存储输入数字和结果。没有使用随输入大小增长的额外内存或 数据结构，因此是恒定的。

方法 2：使用位掩码手动进行位翻转

算法

步骤 1：理解整数的二进制表示：在 Java 中，整数以 32 位二的补码表示形式存储。这意味着每个正数或负数都表示为 32 位二进制位的序列。例如，数字 5 的二进制表示为：00000000 00000000 00000000 00000101。

步骤 2：初始化变量：创建一个变量（result）来存储最终翻转的数字。从 result = 0 开始，因为我们将逐位构建它。

步骤 2.1：设置位掩码：要手动处理和翻转每一位，请创建一个位掩码。位掩码是用于在数字中隔离或修改特定位的值。从初始化为 1 的掩码开始（二进制 00000000 00000000 00000000 00000001）。掩码将在每次迭代处理输入数字的各个位时用于提取。在处理完每个位后，掩码将左移以与数字中的下一位对齐。

步骤 3：迭代每一位：使用循环处理给定数字的所有 32 位：从最低有效位（最右位）开始，向最高有效位（最左位）移动。在每次迭代中，使用位掩码隔离当前位。

步骤 3.1：使用位掩码提取当前位：要提取数字的当前位，请在输入数字和位掩码之间执行按位 AND 操作。最初，位掩码设置为 1（二进制 00000000 00000000 00000000 00000001）。按位 AND 操作会隔离数字的最低有效位（最右位）。

步骤 4：提取当前位：要提取数字的当前位：使用右移运算符 (>) 将数字的位向右移动 i 位，其中 i 是当前位位置（从 0 到 31）。使用 1 进行按位 AND (&) 操作以提取移位数字的最低有效位。例如：在位置 0（最右位），(num >> 0) & 1 给出第一位。在位置 1，(num >> 1) & 1 给出第二位，依此类推。

步骤 5：翻转提取的位：提取当前位后：如果它是 0，则将其更改为 1。如果它是 1，则将其更改为 0。这可以通过简单的条件检查来完成。

步骤 6：更新结果：要将翻转后的位包含在最终结果中：使用左移运算符 (<<) 将翻转后的位移回其原始位置。使用按位 OR (|) 将其与结果合并，这确保了 result 中仅翻转后的位被更新。

步骤 7：对所有 32 位继续：对输入数字的所有 32 位重复上述步骤。循环确保所有位都被正确处理和翻转。

步骤 8：返回最终翻转的结果：遍历完输入数字的所有 32 位并翻转每一位后，最终翻转的结果存储在 result 变量中。现在，结果包含翻转数字的二进制值，其每一位都与原始数字相比翻转了。然后返回结果或将其作为输出打印。

步骤 9：验证输出：完成位翻转后，通过将其与预期结果进行比较来验证输出的正确性非常重要。我们可以使用不同的输入值（正数和负数）来测试该方法，以确保它能正确处理各种情况。

文件名：BitInversionManual.java

输出

 
Original Number: 5
Inverted Number: -6   

复杂度分析

时间复杂度

此位翻转算法的时间复杂度为 O(32)，可简化为 O(1)。整数中的 32 位中的每一位都恰好处理一次，涉及移位、掩码和翻转等恒定时间操作。由于位数是固定的，因此运行时保持恒定，与输入大小无关。

空间复杂度

此算法的空间复杂度为 O(1)，因为它为 变量（如输入数字、结果和循环计数器）使用了恒定的空间。不需要额外的数据结构或动态内存分配，因此无论输入的大小或值如何，空间使用都保持固定。