⭐算法OJ⭐位操作实战（C++ 实现）190. Reverse Bits | 268. Missing Number | 338. Counting Bits

190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

逐位反转

思路

从右到左逐位提取原数的二进制位，然后从左到右构建反转后的数。

步骤

• 初始化一个变量 result 为 0。
• 遍历 32 次，每次将 result 左移一位，并加上原数的最低位。
• 将原数右移一位，继续处理下一位。

代码

uint32_t reverseBits(uint32_t n) {uint32_t result = 0;for (int i = 0; i < 32; i++) {result = (result << 1) | (n & 1); // 将 result 左移并加上 n 的最低位n >>= 1; // 右移 n}return result;
}

复杂度分析

• 时间复杂度：O(1)，因为只需要固定 32 次操作。
• 空间复杂度：O(1)，只使用了常数空间。

268. Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

利用异或运算的性质，a ^ a = 0 和 a ^ 0 = a，将数组中的所有数字与 [0, n] 范围内的所有数字进行异或运算，最终结果即为缺失的数字。

int missingNumber(vector<int>& nums) {int missing = nums.size();for (int i = 0; i < nums.size(); i++) {missing ^= i ^ nums[i];}return missing;
}

338. Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

动态规划 + 最低有效位

思路

• 对于一个数 i，其二进制中 1 的个数等于去掉最低有效位后的数的 1 的个数加上最低有效位是否为 1。
• 例如，
  • 5 的二进制是 101，去掉最低有效位后是 10，即 2，所以 5 的 1 的个数是 ans[2] + 1 = 2；
  • 6 的二进制是 110，去掉最低有效位后是 11，即 3，所以 6 的 1 的个数是 ans[3] + 0 = 2。

步骤

• 初始化一个长度为 n + 1 的数组 ans，并设置 ans[0] = 0。
• 遍历 1 到 n 的每个数，更新 ans[i]。

代码

vector<int> countBits(int n) {vector<int> ans(n + 1);for (int i = 1; i <= n; i++) {ans[i] = ans[i >> 1] + (i & 1); // 动态规划}return ans;
}

复杂度分析

• 时间复杂度：O(n)，只需要遍历一次。
• 空间复杂度：O(1)，除了结果数组外，只使用了常数空间。

动态规划 + 最后设置位

思路

• 对于一个数 i，其二进制中 1 的个数等于去掉最后一个 1 后的数的 1 的个数加 1。
• 例如，5 的二进制是 101，去掉最后一个 1 后是 100，即 4，所以 5 的 1 的个数是 ans[4] + 1 = 2。

步骤

初始化一个长度为 n + 1 的数组 ans，并设置 ans[0] = 0。
遍历 1 到 n 的每个数，更新 ans[i]。

代码

vector<int> countBits(int n) {vector<int> ans(n + 1);for (int i = 1; i <= n; i++) {ans[i] = ans[i & (i - 1)] + 1; // 动态规划}return ans;
}

复杂度分析

• 时间复杂度：O(n)，只需要遍历一次。
• 空间复杂度：O(1)，除了结果数组外，只使用了常数空间。