位运算专题

Java Bit Operation-位运算基本概念介绍

Java Bit Operation-位运算类型转换

leetcode bit operator 位运算入门介绍

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

示例:

  [java]
1
2
3
4
int 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

示例:

  [java]
1
2
3
4
int 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

示例:

  [java]
1
2
3
4
int a = 5; // 0101 int b = 3; // 0011 int result = a ^ b; // 0110 System.out.println(result); // 输出 6

解释: 5(二进制 0101)和 3(二进制 0011)按位异或的结果是 6(二进制 0110)。

4. 按位取反 (~)

按位取反运算符将操作数的每一位都反转,即 0110

示例:

  [java]
1
2
3
int a = 5; // 0101 int result = ~a; // 1010 System.out.println(result); // 输出 -6

解释: 5(二进制 0101)按位取反后得到 -6(二进制 1010,补码表示)。注意,由于 Java 中的整数是用补码表示的,结果是负数。

5. 左移 (<<)

左移运算符将操作数的二进制位向左移动指定的位数,左移后低位补 0。左移相当于乘以 2n 次方(n 为移位数)。

示例:

  [java]
1
2
3
int a = 5; // 0101 int result = a << 1; // 1010 System.out.println(result); // 输出 10

解释: 5(二进制 0101)左移 1 位后得到 10(二进制 1010),即 5 * 2^1 = 10

6. 右移 (>>)

右移运算符将操作数的二进制位向右移动指定的位数。右移时,符号位(对于负数)会保持不变,其他位会被丢弃。

示例:

  [java]
1
2
3
int a = 5; // 0101 int result = a >> 1; // 0010 System.out.println(result); // 输出 2

解释: 5(二进制 0101)右移 1 位后得到 2(二进制 0010),即 5 / 2^1 = 2

7. 无符号右移 (>>>)

无符号右移运算符将操作数的二进制位向右移动指定的位数。

无符号右移与右移的区别在于,它不考虑符号位,无论是正数还是负数,都会用 0 来填充高位。

示例:

  [java]
1
2
3
int 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. 记住一些常用模式

有些位运算的用法在问题中是非常常见的,可以把它们当作模板记住: