算法沉淀——位运算（leetcode真题剖析）

算法沉淀——位运算

• 常用位运算总结
• • 1.基础位运算
  • 2.确定一个数中第x位是0还是1
  • 3.将一个数的第x位改成1
  • 4.将一个数的第x位改成0
  • 5.位图
  • 6.提取一个数最右边的1
  • 7.删掉一个数最右边的1
  • 8.异或运算
  • 9.基础例题
  • 力扣题目讲解
  • • 01.面试题 01.01. 判定字符是否唯一
    • 02.丢失的数字
    • 03.两整数之和
    • 04.只出现一次的数字 II
    • 05.面试题 17.19. 消失的两个数字

      常用位运算总结

      1.基础位运算

      1. 按位与（&）：对两个二进制数的对应位进行与运算，结果中的每一位都是两个数对应位上的位与操作的结果。

         int result = a & b;
         

      2. 按位或（|）：对两个二进制数的对应位进行或运算，结果中的每一位都是两个数对应位上的位或操作的结果。

         int result = a | b;
         

      3. 按位异或（^）：对两个二进制数的对应位进行异或运算，结果中的每一位都是两个数对应位上的位异或操作的结果。

         int result = a ^ b;
         

      4. 按位取反（~）：对一个二进制数的每一位取反，即将0变为1，将1变为0。

         int result = ~a;
         

      5. 左移（> 1; // 将a的二进制表示向右移动1位

      2.确定一个数中第x位是0还是1

      (n>>x)&1 
      

      1. n >> x：右移操作符将二进制表示的整数 n 向右移动 x 位。这意味着我们把整数 n 的二进制表示向右移动 x 位。
      2. (n >> x) & 1：与操作符 & 对两个二进制数的对应位进行与运算。在这里，对 (n >> x) 的结果与二进制数 1 进行与运算。
         • 如果 (n >> x) 的二进制表示中第 x 位是1，与1进行与运算的结果是1。
         • 如果 (n >> x) 的二进制表示中第 x 位是0，与1进行与运算的结果是0。

      这是一种常见的技巧，特别是在位操作中，用于提取或测试一个特定位的值。

      3.将一个数的第x位改成1

      n|=(1
      public:
          bool isUnique(string astr) {
              int n = astr.size();  // 获取字符串的长度
              int c = 0;  // 使用一个整数c来表示出现过的字符情况
              for (int i = 0; i