【算法系列篇】位运算

文章目录

• 前言
• 什么是位运算算法
• 1.判断字符是否唯一
• • 1.1 题目要求
  • 1.2 做题思路
  • 1.3 Java代码实现
  • 2. 丢失的数字
  • • 2.1 题目要求
    • 2.2 做题思路
    • 2.3 Java代码实现
    • 3. 两数之和
    • • 3.1 题目要求
      • 3.2 做题思路
      • 3.3 Java代码实现
      • 4. 只出现一次的数字
      • • 4.1 题目要求
        • 4.2 做题思路
        • 4.3 Java代码实现
        • 5. 消失的两个数字
        • • 5.1 题目要求
          • 5.2 做题思路
          • 5.3 Java代码实现
          • ���结

            前言

            位操作符想必大家都知道吧，&——按位与，|——按位或，^——按位异或，~——按位取法，位操作主要是用来操作二进制数的，就是因为它操作的是二进制，所以它的速度非常的快，那么既然他的速度很快，我们是否可以用位运算来解决一些实际问题呢？当然是可以的，这篇文章我将为大家分享如何使用位运算这种算法来解决一些问题。

            什么是位运算算法

            位运算算法是一组基于二进制位的操作符和操作方法的算法，用于在计算机中对二进制数字进行快速和高效的操作。位运算算法可以在二进制位级别上进行操作，包括位与（AND）、位或（OR）、位异或（XOR）、位取反（NOT）以及移位操作（左移和右移）等。

            • 按位与(&)：只有当两个比特位都为1的时候结果才为1，否则为0
            • 按位或(|)：两个比特位中有一个1，结果就为1
            • 按位异或(^)：两个比特位相同为0，相异为1
            • 按位取反(~)：除符号位之外，其它的比特位取反，为0结果为1，为1结果为0

              位运算算法常用于以下情况：

              1. 位操作：可以通过位与、位或、位异或等运算符来对二进制数字的每一位进行操作，实现快速的位级别操作。
              2. 位掩码：可以使用位运算来创建和操作掩码，掩码经常用于标志位、权限控制和位字段的操作。
              3. 整数运算优化：位运算算法可以实现某些整数运算的高效实现，如乘以2的幂次方、除以2的幂次方、判断奇偶性等。
              4. 位图算法：位运算常用于位图算法，其中每个二进制位表示集合中的一个元素，可以进行高效的集合操作，如并集、交集、差集等。
              5. 压缩算法：位运算可以在压缩算法中起到重要的作用，用于压缩和解压缩数据，常见的例子包括哈夫曼编码和算术编码。

              位运算算法通常具有高效性、简洁性和可移植性的特点，可以提供快速的底层操作，特别适合某些特定的问题和应用领域。在编写低级别的系统程序、嵌入式系统、网络协议和算法优化等方面，位运算算法发挥着重要的作用。

              1.判断字符是否唯一

              https://leetcode.cn/problems/is-unique-lcci/

              1.1 题目要求

              实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

              示例 1：

              输入: s = "leetcode"
              输出: false 
              

              示例 2：

              输入: s = "abc"
              输出: true
              

              限制：

              • 0 public boolean isUnique(String astr) { } } public boolean isUnique(String astr) { //鸽巢原理，当字符串长度大于26的时候一定会有重复的字符 if(astr.length() 26) return fasle; int tmp = 0; //tmp 代表32位比特位的位图 for(int i = 0; i (ch - 'a')) & 1) == 1) return false; else tmp = tmp | (1 public int missingNumber(int[] nums) { } } public int missingNumber(int[] nums) { int ret = 0; for(int n : nums) ret ^= n; for(int i = 0; i public int getSum(int a, int b) { } } public int getSum(int a, int b) { while(b != 0) { int x = a ^ b; int y = a & b; a = x; b = y public int singleNumber(int[] nums) { } } public int singleNumber(int[] nums) { int ret = 0; for(int i = 0; i