本文档涵盖了 TheAlgorithms/Java 仓库中实现的位操作算法。位操作涉及直接处理数字二进制表示中的单个位。这些技术常用于性能优化至关重要的场景，或解决可以利用二进制运算的特定算法问题。
位操作使用基本的按位运算符来操纵整数值中的单个位。理解这些运算符对于理解本节中的实现至关重要。
来源： src/main/java/com/thealgorithms/bitmanipulation/NonRepeatingNumberFinder.java src/main/java/com/thealgorithms/bitmanipulation/NumbersDifferentSigns.java src/main/java/com/thealgorithms/bitmanipulation/ReverseBits.java
| 运算符 | 符号 | 描述 |
|---|---|---|
| 按位与 (AND) | & | 如果两个对应位都为 1，则将该位设置为 1 |
| 或 | | | 如果至少一个对应位为 1，则将该位设置为 1 |
| 按位异或 (XOR) | ^ | 如果只有一个对应位为 1，则将该位设置为 1 |
| 按位非 (NOT) | ~ | 反转所有位 |
| 左移 | << | 将位向左移动指定的位数 |
| 右移 | >> | 将位向右移动指定的位数（符号位保留） |
| 无符号右移 | >>> | 将位向右移动指定的位数（用 0 填充） |
此仓库包含多种位操作算法，展示了这些操作的实际应用。
来源： src/main/java/com/thealgorithms/bitmanipulation/
NonRepeatingNumberFinder 类提供了一种方法，用于在一个数组中查找一个不重复的数字，其中所有其他数字都恰好出现两次。
此实现利用了异或运算的关键特性
x ^ x = 0x ^ 0 = x当所有元素进行异或运算时，重复的元素会相互抵消（变为 0），只剩下不重复的数字。
实现： src/main/java/com/thealgorithms/bitmanipulation/NonRepeatingNumberFinder.java28-34
时间复杂度：O(n) - 数组单次遍历 空间复杂度：O(1) - 常量空间使用
来源： src/main/java/com/thealgorithms/bitmanipulation/NonRepeatingNumberFinder.java src/test/java/com/thealgorithms/bitmanipulation/NonRepeatingNumberFinderTest.java
NumbersDifferentSigns 类使用按位操作来判断两个整数是否具有不同的符号（正/负）。
此方法利用了符号位（最高有效位）对于负数是 1，对于非负数是 0 的事实。当两个符号不同的数字进行异或运算时，结果的符号位将是 1，使其为负。
实现： src/main/java/com/thealgorithms/bitmanipulation/NumbersDifferentSigns.java27-29
时间复杂度：O(1) - 常量时间操作 空间复杂度：O(1) - 常量空间使用
来源： src/main/java/com/thealgorithms/bitmanipulation/NumbersDifferentSigns.java src/test/java/com/thealgorithms/bitmanipulation/NumbersDifferentSignsTest.java
ReverseBits 类反转一个 32 位整数的位，将最低有效位 (LSB) 转换为最高有效位 (MSB)，反之亦然。
该算法逐个处理输入整数的每个位，提取最低有效位并将其放置在结果中的适当位置。
实现： src/main/java/com/thealgorithms/bitmanipulation/ReverseBits.java31-40
时间复杂度：O(1) - 固定 32 次迭代，与输入无关 空间复杂度：O(1) - 常量空间使用
来源： src/main/java/com/thealgorithms/bitmanipulation/ReverseBits.java src/test/java/com/thealgorithms/bitmanipulation/ReverseBitsTest.java
IndexOfRightMostSetBit 类用于查找给定整数中最右边设为 1 的位的索引。
对于负数，该算法首先使用表达式 n & (~n + 1) 隔离最右边的置位位。这是一种常见的位操作技巧，可以清除除最右边置位位以外的所有位。
实现： src/main/java/com/thealgorithms/bitmanipulation/IndexOfRightMostSetBit.java25-43
时间复杂度：O(log n) - 最坏情况下，检查位数与输入相同 空间复杂度：O(1) - 常量空间使用
来源： src/main/java/com/thealgorithms/bitmanipulation/IndexOfRightMostSetBit.java src/test/java/com/thealgorithms/bitmanipulation/IndexOfRightMostSetBitTest.java
IsEven 类使用一种简单的位操作技术来判断一个数字是否为偶数。
此方法利用了最低有效位 (LSB) 对于偶数为 0，对于奇数为 1 的事实。与 1 进行按位与运算可以提取出最低有效位。
实现： src/main/java/com/thealgorithms/bitmanipulation/IsEven.java11-13
时间复杂度：O(1) - 常量时间操作 空间复杂度：O(1) - 常量空间使用
来源： src/main/java/com/thealgorithms/bitmanipulation/IsEven.java src/test/java/com/thealgorithms/bitmanipulation/IsEvenTest.java
此仓库中的实现展示了几种常见的位操作技术
| 技术 | 描述 | 仓库中的示例 |
|---|---|---|
| 使用异或运算查找唯一元素 | 使用异或运算识别数组中不重复的元素 | NonRepeatingNumberFinder |
| 符号位检查 | 检查最高有效位以确定符号 | NumbersDifferentSigns |
| 位反转 | 反转整数中位的顺序 | ReverseBits |
| 隔离最右边的置位位 | 使用 n & (~n + 1) 隔离最右边的 1 位 | IndexOfRightMostSetBit |
| LSB（最低有效位）检查 | 检查最低有效位以确定奇偶性等属性 | IsEven |
这些技术常用于各种算法中，通过直接操作位而不是传统的算术操作，可以显著优化某些运算。