leetcode bit operator 位运算

#

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. 按位取反 (~)

按位取反运算符将操作数的每一位都反转，即 0 变 1，1 变 0。

示例:

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

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

5. 左移 (<<)

左移运算符将操作数的二进制位向左移动指定的位数，左移后低位补 0。左移相当于乘以 2 的 n 次方（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 个数字的数组，数字范围从 0 到 n，请找出这个数组中缺失的那个数字。

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

代码:

   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 个数字的数组，数字范围从 0 到 n，请找出这个数组中缺失的那个数字。

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

代码:

   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. 记住一些常用模式

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

• chat
  • 是什么？
    • 1. 按位与 (&)
    • 2. 按位或 (|)
    • 3. 按位异或 (^)
    • 4. 按位取反 (~)
    • 5. 左移 (<<)
    • 6. 右移 (>>)
    • 7. 无符号右移 (>>>)
    • 8. 移位运算与溢出
    • 9. 位运算的应用
  • leetcode 经典题目
    • 1. LeetCode 136. Single Number
    • 2. LeetCode 137. Single Number II
    • 3. LeetCode 191. Number of 1 Bits
    • 4. LeetCode 268. Missing Number
    • 5. LeetCode 462. Minimum Moves to Equal Array Elements II
    • 6. LeetCode 260. Single Number III
    • 7. LeetCode 405. Convert a Number to Hexadecimal
    • 总结
  • leetcode 中的经典题目
    • 1. LeetCode 136. Single Number
    • 2. LeetCode 137. Single Number II
    • 3. LeetCode 191. Number of 1 Bits
    • 4. LeetCode 268. Missing Number
    • 5. LeetCode 462. Minimum Moves to Equal Array Elements II
    • 6. LeetCode 260. Single Number III
    • 7. LeetCode 405. Convert a Number to Hexadecimal
  • 记忆的技巧
    • 1. 理解基本原理与运算性质
    • 2. 通过例子加深记忆
    • 3. 理解位运算在实际问题中的应用
    • 4. 练习与反复应用
    • 5. 记住一些常用模式