位运算专题
leetcode 002-leetcode.136 single-number 力扣.136 只出现一次的数字
leetcode 002-leetcode.137 single-number-ii 力扣.137 只出现一次的数字II
leetcode 002-leetcode.260 single-number-iii 力扣.260 只出现一次的数字III
位运算介绍
Java 中的位运算是对整数类型(byte
, short
, int
, long
)的二进制位进行操作的一种运算方式。
位运算通常用于底层编程、优化性能、加密算法等领域。
Java 提供了多种位运算符,下面是对这些运算符的详细介绍:
基本介绍
1. 按位与 (&
)
按位与运算符对两个操作数的每一位进行与操作。
如果对应的位都为 1
,结果为 1
,否则为 0
。
示例:
1
2
3
4int a = 5; // 0101
int b = 3; // 0011
int result = a & b; // 0001
System.out.println(result); // 输出 1
解释: 5(二进制 0101
)和 3(二进制 0011
)按位与的结果是 1(二进制 0001
)。
2. 按位或 (|
)
按位或运算符对两个操作数的每一位进行或操作。如果对应的位有一个为 1
,结果为 1
,否则为 0
。
示例:
1
2
3
4int a = 5; // 0101
int b = 3; // 0011
int result = a | b; // 0111
System.out.println(result); // 输出 7
解释: 5(二进制 0101
)和 3(二进制 0011
)按位或的结果是 7(二进制 0111
)。
3. 按位异或 (^
)
按位异或运算符对两个操作数的每一位进行异或操作。如果对应的位不同,则结果为 1
,相同则为 0
。
示例:
1
2
3
4int a = 5; // 0101
int b = 3; // 0011
int result = a ^ b; // 0110
System.out.println(result); // 输出 6
解释: 5(二进制 0101
)和 3(二进制 0011
)按位异或的结果是 6(二进制 0110
)。
4. 按位取反 (~
)
按位取反运算符将操作数的每一位都反转,即 0
变 1
,1
变 0
。
示例:
1
2
3int a = 5; // 0101
int result = ~a; // 1010
System.out.println(result); // 输出 -6
解释: 5(二进制 0101
)按位取反后得到 -6(二进制 1010
,补码表示)。注意,由于 Java 中的整数是用补码表示的,结果是负数。
5. 左移 (<<
)
左移运算符将操作数的二进制位向左移动指定的位数,左移后低位补 0
。左移相当于乘以 2
的 n
次方(n
为移位数)。
示例:
1
2
3int a = 5; // 0101
int result = a << 1; // 1010
System.out.println(result); // 输出 10
解释: 5(二进制 0101
)左移 1 位后得到 10(二进制 1010
),即 5 * 2^1 = 10
。
6. 右移 (>>
)
右移运算符将操作数的二进制位向右移动指定的位数。右移时,符号位(对于负数)会保持不变,其他位会被丢弃。
示例:
1
2
3int a = 5; // 0101
int result = a >> 1; // 0010
System.out.println(result); // 输出 2
解释: 5(二进制 0101
)右移 1 位后得到 2(二进制 0010
),即 5 / 2^1 = 2
。
7. 无符号右移 (>>>
)
无符号右移运算符将操作数的二进制位向右移动指定的位数。
无符号右移与右移的区别在于,它不考虑符号位,无论是正数还是负数,都会用 0
来填充高位。
示例:
1
2
3int a = -5; // 11111111111111111111111111111011
int result = a >>> 1; // 01111111111111111111111111111101
System.out.println(result); // 输出 2147483643
解释: -5
的二进制表示为补码形式 11111111111111111111111111111011
,无符号右移 1 位后得到 2147483643
,高位补充 0
。
8. 移位运算与溢出
移位操作对于大整数值会造成溢出,尤其是使用 <<
和 >>
时。
Java 的 int
类型是 32 位,超出范围时会截断。
需要注意的是,移位位数大于等于位数长度(例如 32 位整数移位 32 位或更多)时,会产生未定义的行为。
记忆的技巧
理解和记住位运算确实有一定难度,尤其是当它们在日常工作中不常用时。
以下是一些帮助记忆和应用位运算的技巧:
1. 理解基本原理与运算性质
位运算的核心是操作二进制位,掌握一些基本的运算性质可以帮助你记住它们的作用:
- 异或(
^
): 相同的数字异或结果是 0,0 和任何数字异或是该数字本身。这种对称性可以帮助你记住它的用途(如找出唯一的数字)。 - 按位与(
&
): 只有当两个位都为 1 时结果才是 1,常用于检查特定位。 - 按位或(
|
): 只要有一个位是 1,结果就是 1,常用于合并状态或标记。 - 左移/右移(
<<
,>>
): 左移相当于乘以 2 的幂,右移相当于除以 2 的幂。
2. 理解位运算在实际问题中的应用
位运算通常用于以下几种场景,理解这些场景有助于记住常见的使用模式:
- 去重和唯一元素: 如单一数字问题(异或运算),通过异或运算找出只出现一次的元素。
- 状态标记: 使用位运算可以高效地管理多个布尔值,如通过按位与或按位或合并多个标志位。
- 优化算法: 位运算有时可以取代较慢的算术运算(如左移代替乘法,右移代替除法)。
3. 记住一些常用模式
有些位运算的用法在问题中是非常常见的,可以把它们当作模板记住: