本文共 1724 字，大约阅读时间需要 5 分钟。

位操作（Bit Operation）相关题目解法总结

在面试环节中，面试官喜欢问一些特殊题目，而位操作（Bit Operation）正是这些题目中最有魅力的之一。今天，我将分享LeetCode上与位操作相关的四个经典题目及其解法。

第1题：位 1 的个数

LeetCode号：191 题。题目要求编写一个函数，输入一个无符号整数，返回其二进制表示中数字位为1的个数。

解法分析：

• 方法一：利用位移操作。观察n和n-1的二进制表示，发现n-1会将n的最低位1变为0，并将后续的0变为1。通过n & (n-1)，可以消除末尾的1，重复这个操作直到n为0，统计1的个数即可。
• 方法二：逐位检查。对每一位进行检查看是否为1，可以使用mask的方式逐位提取并累加。
• 方法三：求和法。将数的每一位与1进行按位与操作后相加，得到结果。

推荐代码：

int hammingWeight(uint32_t n) {
  int res = 0;
  for (int i = 0; i < 32; ++i) {
    res += (n & 1);
    n >>= 1;
  }
  return res;
}

第2题：2 的幂

LeetCode号：231 题。给定一个整数，判断它是否是2的幂。

解法分析：

• 方法一：逐位检查。将数字不断右移，并统计1的个数。一旦发现还有多个1，则不是2的幂。
• 方法二：利用二进制性质。若n为2的幂，其二进制形式只有一个1。因此，只需检查n-1与n & (n-1)是否为0。

推荐代码：

bool isPowerOfTwo(int n) {
  return (n > 0) && !(n & (n - 1));
}

第3题：数字范围按位与

LeetCode号：201 题。给定一个整数范围[m, n]，计算区间内所有数字的按位与。

解法分析：

• 方法一：通过掩码逐步移位。从最高位到底，检查是否m和n在当前位上对应位置相同。当所有相同位数都已找到时，将m与当前掩码相与即为结果。

推荐代码：

int rangeBitwiseAnd(int m, int n) {
  int d = INT_MAX;
  while ((m & d) != (n & d)) {
    d <<= 1;
  }
  return m & d;
}

第4题：重复的 DNA 序列

LeetCode号：187 题。查找DNA分子中所有出现超过一次的10个字母长的序列。

解法分析：

• 方法一：滑动窗口法。使用哈希表记录子串的出现次数。一旦发现新子串已存在，则记录。
• 方法二：位操作。将每个字符用位掩码表示，提取特定位数后处理。

推荐代码：

vector
   
     findRepeatedDnaSequences(string s) {
  vector
    
      res;
  unordered_set
     
       st;
  unordered_map
      
        m;
  int mask = 0x7FFFFFF;
  int cur = 0;
  for (int i = 0; i < 9; ++i) {
    cur = (cur << 3) | (s[i] & 7);
  }
  for (int i = 9; i < s.size(); ++i) {
    cur = ((cur & 0x7FFFFFF) << 3) | (s[i] & 7);
    if (st.count(cur)) {
      res.push_back(s.substr(i - 9, 10));
      ++m[cur];
    } else {
      st.insert(cur);
      m[cur] = 1;
    }
  }
  return res;
}
      
     
    
   

总结

这些题目通过位操作的巧妙运用，展现了如何在算法中通过简单的位操作来解决复杂的问题。掌握这些技巧对面试perfence极为有利，也为编程思维的提升提供了丰富的思路。