#

chat

是什么?

Java 中的位运算是对整数类型(byte, short, int, long)的二进制位进行操作的一种运算方式。位运算通常用于底层编程、优化性能、加密算法等领域。Java 提供了多种位运算符,下面是对这些运算符的详细介绍:

1. 按位与 (&)

按位与运算符对两个操作数的每一位进行与操作。如果对应的位都为 1,结果为 1,否则为 0

示例:

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

示例:

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

示例:

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

示例:

int a = 5;   // 0101
int result = ~a;  // 1010
System.out.println(result);  // 输出 -6

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

5. 左移 (<<)

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

示例:

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

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

6. 右移 (>>)

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

示例:

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 来填充高位。

示例:

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 位或更多)时,会产生未定义的行为。

9. 位运算的应用

  • 性能优化: 位运算通常比算术运算(如乘法、除法)更高效。比如,左移 n 位相当于乘以 2^n,右移 n 位相当于除以 2^n
  • 判断奇偶: 判断一个数是否为奇数可以通过 x & 1,如果结果为 1,则 x 是奇数。
  • 交换两个数: 通过异或运算可以交换两个数的值而不需要临时变量:
      a = a ^ b;
      b = a ^ b;
      a = a ^ b;
    

位运算虽然简单,但由于其底层性质,常常用在需要高效、精确控制的场景中。

leetcode 经典题目

位运算在 LeetCode 中有许多经典的题目,它们常用于优化算法、减少时间复杂度以及解决某些特殊问题。下面列举了一些经典的 LeetCode 题目,它们都涉及到位运算:

1. LeetCode 136. Single Number

题目描述: 给定一个非空整数数组,每个元素都出现两次,只有一个元素出现一次。找出这个唯一的元素。

解法: 使用位运算中的 异或^)。异或的性质是:相同的数字异或结果为 0,0 和任何数字异或结果为该数字本身。所以异或所有元素,最后的结果就是那个只出现一次的数字。

代码:

   public int singleNumber(int[] nums) {
       int result = 0;
       for (int num : nums) {
           result ^= num;  // 将所有元素进行异或
       }
       return result;
   }

时间复杂度: O(n),其中 n 是数组的长度。

空间复杂度: O(1),只用了常数空间。


2. LeetCode 137. Single Number II

题目描述: 给定一个整数数组 nums,其中每个元素出现三次,除了一个元素只出现一次。找出这个唯一的元素。

解法: 使用位运算的 计数法。可以通过记录每一位出现的次数来找到只出现一次的数字。通过和 3 取模来找到那一位为 1 的数字。

代码:

   public int singleNumber(int[] nums) {
       int ones = 0, twos = 0;
       for (int num : nums) {
           ones = (ones ^ num) & ~twos;
           twos = (twos ^ num) & ~ones;
       }
       return ones;
   }

时间复杂度: O(n),其中 n 是数组的长度。

空间复杂度: O(1),只用了常数空间。


3. LeetCode 191. Number of 1 Bits

题目描述: 编写一个函数,输入一个无符号整数 n,返回其二进制表示中 1 的个数。

解法: 使用 位运算 来判断每一位是否为 1,可以通过不断与 1 做 按位与运算,然后右移,直到数字变为 0。

代码:

   public int hammingWeight(int n) {
       int count = 0;
       while (n != 0) {
           count += n & 1;  // 如果当前最低位是 1,则计数器加 1
           n >>>= 1;         // 无符号右移
       }
       return count;
   }

时间复杂度: O(32),因为 n 是 32 位的整数。

空间复杂度: O(1)。


4. LeetCode 268. Missing Number

题目描述: 给定一个包含 n 个数字的数组,数字范围从 0n,请找出这个数组中缺失的那个数字。

解法: 使用 异或运算。对于一个包含数字 0n 的数组,所有数字与它们的索引异或后,最后的结果就是缺失的那个数字。

代码:

   public int missingNumber(int[] nums) {
       int result = nums.length;  // 初始时将结果设为 n
       for (int i = 0; i < nums.length; i++) {
           result ^= i ^ nums[i];
       }
       return result;
   }

时间复杂度: O(n),其中 n 是数组的长度。

空间复杂度: O(1)。


5. LeetCode 462. Minimum Moves to Equal Array Elements II

题目描述: 给定一个整数数组,求最小的移动次数,使得数组中的所有元素都变成一样的数。每次移动可以使一个元素增加或减少 1。

解法: 通过 位运算,在中位数附近的元素最接近相同,所以使用 中位数 来解决该问题。

代码:

   public int minMoves2(int[] nums) {
       Arrays.sort(nums);
       int median = nums[nums.length / 2];
       int moves = 0;
       for (int num : nums) {
           moves += Math.abs(num - median);
       }
       return moves;
   }

时间复杂度: O(n log n),需要对数组进行排序。

空间复杂度: O(1)。


6. LeetCode 260. Single Number III

题目描述: 给定一个整数数组 nums,其中有两个元素只出现一次,其他元素出现两次。找出这两个只出现一次的数字。

解法: 使用 异或运算。首先通过异或所有元素得到这两个唯一元素的异或结果,然后通过分组的方式找出这两个数字。

代码:

   public int[] singleNumber(int[] nums) {
       int xor = 0;
       for (int num : nums) {
           xor ^= num;  // 先对所有元素进行异或
       }
       int rightmostBit = xor & (-xor);  // 获取异或结果的最低位 1
       int[] result = new int[2];
       for (int num : nums) {
           if ((num & rightmostBit) != 0) {
               result[0] ^= num;  // 低位 1 分组
           } else {
               result[1] ^= num;  // 低位 0 分组
           }
       }
       return result;
   }

时间复杂度: O(n),其中 n 是数组的长度。

空间复杂度: O(1)。


7. LeetCode 405. Convert a Number to Hexadecimal

题目描述: 给定一个整数 num,将其转换为十六进制字符串。你需要使用最少的字符。

解法: 可以通过 位运算 按 4 位分割,逐步计算出十六进制字符串。

代码:

   public String toHex(int num) {
       if (num == 0) return "0";
       StringBuilder sb = new StringBuilder();
       char[] hex = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
       while (num != 0) {
           sb.append(hex[num & 15]);  // 获取最低四位并转为十六进制字符
           num >>>= 4;  // 无符号右移四位
       }
       return sb.reverse().toString();
   }

时间复杂度: O(log n),其中 n 是整数 num 的大小。

空间复杂度: O(1)。


总结

位运算在 LeetCode 中的应用非常广泛,特别是在需要优化时间复杂度或者处理与二进制位相关的问题时。

通过掌握异或、按位与、按位或、右移和左移等位运算技巧,可以有效地解决一系列看似复杂的问题,尤其是在处理数组、位图和数字特性时。

leetcode 中的经典题目

位运算在 LeetCode 中有许多经典的题目,它们常用于优化算法、减少时间复杂度以及解决某些特殊问题。

下面列举了一些经典的 LeetCode 题目,它们都涉及到位运算:

1. LeetCode 136. Single Number

题目描述: 给定一个非空整数数组,每个元素都出现两次,只有一个元素出现一次。找出这个唯一的元素。

解法: 使用位运算中的 异或^)。

异或的性质是:相同的数字异或结果为 0,0 和任何数字异或结果为该数字本身。所以异或所有元素,最后的结果就是那个只出现一次的数字。

代码:

   public int singleNumber(int[] nums) {
       int result = 0;
       for (int num : nums) {
           result ^= num;  // 将所有元素进行异或
       }
       return result;
   }

时间复杂度: O(n),其中 n 是数组的长度。

空间复杂度: O(1),只用了常数空间。


2. LeetCode 137. Single Number II

题目描述: 给定一个整数数组 nums,其中每个元素出现三次,除了一个元素只出现一次。找出这个唯一的元素。

解法: 使用位运算的 计数法。可以通过记录每一位出现的次数来找到只出现一次的数字。通过和 3 取模来找到那一位为 1 的数字。

代码:

   public int singleNumber(int[] nums) {
       int ones = 0, twos = 0;
       for (int num : nums) {
           ones = (ones ^ num) & ~twos;
           twos = (twos ^ num) & ~ones;
       }
       return ones;
   }

时间复杂度: O(n),其中 n 是数组的长度。

空间复杂度: O(1),只用了常数空间。


3. LeetCode 191. Number of 1 Bits

题目描述: 编写一个函数,输入一个无符号整数 n,返回其二进制表示中 1 的个数。

解法: 使用 位运算 来判断每一位是否为 1,可以通过不断与 1 做 按位与运算,然后右移,直到数字变为 0。

代码:

   public int hammingWeight(int n) {
       int count = 0;
       while (n != 0) {
           count += n & 1;  // 如果当前最低位是 1,则计数器加 1
           n >>>= 1;         // 无符号右移
       }
       return count;
   }

时间复杂度: O(32),因为 n 是 32 位的整数。

空间复杂度: O(1)。


4. LeetCode 268. Missing Number

题目描述: 给定一个包含 n 个数字的数组,数字范围从 0n,请找出这个数组中缺失的那个数字。

解法: 使用 异或运算。对于一个包含数字 0n 的数组,所有数字与它们的索引异或后,最后的结果就是缺失的那个数字。

代码:

   public int missingNumber(int[] nums) {
       int result = nums.length;  // 初始时将结果设为 n
       for (int i = 0; i < nums.length; i++) {
           result ^= i ^ nums[i];
       }
       return result;
   }

时间复杂度: O(n),其中 n 是数组的长度。

空间复杂度: O(1)。


5. LeetCode 462. Minimum Moves to Equal Array Elements II

题目描述: 给定一个整数数组,求最小的移动次数,使得数组中的所有元素都变成一样的数。每次移动可以使一个元素增加或减少 1。

解法: 通过 位运算,在中位数附近的元素最接近相同,所以使用 中位数 来解决该问题。

代码:

   public int minMoves2(int[] nums) {
       Arrays.sort(nums);
       int median = nums[nums.length / 2];
       int moves = 0;
       for (int num : nums) {
           moves += Math.abs(num - median);
       }
       return moves;
   }

时间复杂度: O(n log n),需要对数组进行排序。

空间复杂度: O(1)。


6. LeetCode 260. Single Number III

题目描述: 给定一个整数数组 nums,其中有两个元素只出现一次,其他元素出现两次。找出这两个只出现一次的数字。

解法: 使用 异或运算。首先通过异或所有元素得到这两个唯一元素的异或结果,然后通过分组的方式找出这两个数字。

代码:

   public int[] singleNumber(int[] nums) {
       int xor = 0;
       for (int num : nums) {
           xor ^= num;  // 先对所有元素进行异或
       }
       int rightmostBit = xor & (-xor);  // 获取异或结果的最低位 1
       int[] result = new int[2];
       for (int num : nums) {
           if ((num & rightmostBit) != 0) {
               result[0] ^= num;  // 低位 1 分组
           } else {
               result[1] ^= num;  // 低位 0 分组
           }
       }
       return result;
   }

时间复杂度: O(n),其中 n 是数组的长度。

空间复杂度: O(1)。


7. LeetCode 405. Convert a Number to Hexadecimal

题目描述: 给定一个整数 num,将其转换为十六进制字符串。你需要使用最少的字符。

解法: 可以通过 位运算 按 4 位分割,逐步计算出十六进制字符串。

代码:

   public String toHex(int num) {
       if (num == 0) return "0";
       StringBuilder sb = new StringBuilder();
       char[] hex = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
       while (num != 0) {
           sb.append(hex[num & 15]);  // 获取最低四位并转为十六进制字符
           num >>>= 4;  // 无符号右移四位
       }
       return sb.reverse().toString();
   }

时间复杂度: O(log n),其中 n 是整数 num 的大小。

空间复杂度: O(1)。


记忆的技巧

理解和记住位运算确实有一定难度,尤其是当它们在日常工作中不常用时。以下是一些帮助记忆和应用位运算的技巧:

1. 理解基本原理与运算性质

位运算的核心是操作二进制位,掌握一些基本的运算性质可以帮助你记住它们的作用:

  • 异或^): 相同的数字异或结果是 0,0 和任何数字异或是该数字本身。这种对称性可以帮助你记住它的用途(如找出唯一的数字)。
  • 按位与&): 只有当两个位都为 1 时结果才是 1,常用于检查特定位。
  • 按位或|): 只要有一个位是 1,结果就是 1,常用于合并状态或标记。
  • 左移/右移<<, >>): 左移相当于乘以 2 的幂,右移相当于除以 2 的幂。

2. 通过例子加深记忆

在学习位运算时,实际操作几个简单例子非常有帮助。比如,手动做几个异或、与、或、移位的题目,逐步分析每一步的运算过程。这可以帮助你直观地理解每种运算的作用。

3. 理解位运算在实际问题中的应用

位运算通常用于以下几种场景,理解这些场景有助于记住常见的使用模式:

  • 去重和唯一元素: 如单一数字问题(异或运算),通过异或运算找出只出现一次的元素。
  • 状态标记: 使用位运算可以高效地管理多个布尔值,如通过按位与或按位或合并多个标志位。
  • 优化算法: 位运算有时可以取代较慢的算术运算(如左移代替乘法,右移代替除法)。

4. 练习与反复应用

虽然位运算很抽象,但通过不断的练习可以逐渐变得熟悉。

比如,可以尝试做一些相关的 LeetCode 题目,或者在项目中找机会用位运算解决一些问题。这样可以加深对位运算的理解和记忆。

5. 记住一些常用模式

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