文章目录
大概那么五六七个月之前，我看到《编程之美》中某道位操作相关的题目，觉得挺有意思，于是稍微整理了一下相关的知识瞎扯出了 从《编程之美》中的一道面试题开始谈谈位操作 这篇文章，今天突然心血来潮点进从来没用过的 LeetCode 发现有一个 Bit Manipulation 的分类专题，于是就挑了其中几道简单的题目做，因此导致了这篇和下篇文章的突然诞生。
首先有几题是可以直接用上前篇文章里面讲到的位操作技巧的，比如通过 n &= (n - 1) 来计算一个数的二进制表示中含有多少个 1，以及 ASCII 大小写字母转换的 trick，下面来看具体题目。
Problem 338. Counting Bits
题目很简单，输入一个非负整数 num，按顺序输出 \([0, num]\) 范围内每个数的二进制表达中含有 1 的个数，直接循环对每个数进行计算也能过：
class Solution {
public:
vector<int> countBits(int num) {
/* 1. Iterate Each Number */
vector<int> ans;
for (int i = 0; i <= num; i++) {
int n = i, cnt = 0;
while (n) {
n &= n - 1;
cnt++;
}
ans.push_back(cnt);
}
return ans;
}
};
当然它要数组的结果那摆明了是想提示计算过程中应该可以用上前面计算的值，要不然直接给一个数让求就够了。题面也有暗示这一点：
It is very easy to come up with a solution with run time \(O(n*sizeof(integer))\). But can you do it in linear time \(O(n)\)/possibly in a single pass?
用个输入为 100 的 Testcase 观察它的输出结果，可以很容易发现规律：
[00, 03]: 0, 1, 1, 2
[04, 07]: 1, 2, 2, 3
[00, 07]: 0, 1, 1, 2, 1, 2, 2, 3
[08, 15]: 1, 2, 2, 3, 2, 3, 3, 4
[00, 15]: 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
[16, 31]: 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
结合各个数字的二进制表达形式（参考 这里），实际上就是数字每次上升一次幂的话，就对应高一位多个 1 然后后面的几位从头开始，如此往复，所以只要从零开始每次把当前数组的各元素加 1 复制一遍进去就可以得到答案：
/* 2. Focus On The First Bit */
vector<int> ans(1, 0);
int sz = 1;
while (sz <= num) {
for (int i = 0; i < sz; i++) {
ans.push_back(ans[i] + 1);
// If the size satisfies the requirement
if (ans.size() > num) break;
}
sz = ans.size();
};
return ans;
从首位去考虑就是直接多了一个 1，那如果从末位去考虑的话，情况就是上一个幂对应的一组数字在当前幂中每个重复两遍并加上末尾的一个 1/0，比如：
[5, 7]: 100 | 101 | 110 | 111
[8, 15]: 1000 1001 | 1010 1011 | 1100 1101 | 1110 1111
每两个数字的前三位关联前一个区间对应数字的完整三位，所以一个 n 位二进制数包含的 1 的总个数就由【前 n-1 位包含 1 的个数】和【它自己的末位是否为 1 】决定，而前几位包含的个数在计算当前数字的时候是已知的，这样问题就可以用动态规划来解决了，两个决定因素的值可以用位运算来提取，代码长度骤减，逼格也高了很多：
/* 3. Focus On The Last Bit */
vector<int> ans(num + 1, 0);
for (int i = 1; i < ans.size(); i++) {
ans[i] = ans[i >> 1] + (i & 1);
}
return ans;
其实还有一个差不多的规律可以从结果集合里面发现，就是从 \([2, 3]\) 开始，每个 \(2^n(n \ge 1)\) 长度的区间，前一半数字都来自前一段区间，后一半数字是前一半数字各自加 1 所得：
[02, 03]: 1, 2
[04, 07]: 1, 2, 2, 3
[08, 15]: 1, 2, 2, 3, 2, 3, 3, 4
[16, 31]: 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
那这个其实是从第二个二进制位考虑了，也就是前半组的第二位为 0，后半组的第二位为 1，剩下三位拼接后还是和前一个区间对应数字的完整三位相同，所以基本的原理都差不多，不过这个的话写起来稍微有点啰嗦，我就不贴代码上来了。
Problem 784. Letter Case Permutation
这个题目要求就是把给定的一个字符串中每个字母的大小写情况进行排列然后输出所有的可能结果，因为它说了输入的字符串中只包含字母和数字，所以直接 ASCII 码判断，大于等于 65 的字符一定是字母，然后用深搜回溯就可以解决问题了：
class Solution {
public:
vector<string> ans;
vector<string> letterCasePermutation(string S) {
dfs(S, 0);
return ans;
}
void dfs(string S, int len) {
if (S.length() == len) {
ans.push_back(S);
return;
}
dfs(S, len + 1);
if (S[len] < 65) return;
S[len] ^= 0x20;
dfs(S, len + 1);
}
};
把这道题放进来是因为里面的字符大小写转换用到了前面一篇文章里提到的方法，也就是和 0x20 进行按位异或得到转换后的字符，这样就可以做到不通过判断而保证【回溯时去掉原本的字母并换上改变大小写之后的对应字母】的需求。
不过其实用判断的方式去写只是代码稍微长一点点而已，也没什么影响，毕竟这不是性能瓶颈 = =
因为字母只分大写和小写两种情况，可以用二叉树来理解这个搜索过程，每往下一层就相当于添加一个新的字符，父节点一定会和其中一个子节点值相同，最后生成的树的叶子节点就是所有的排列情况，树的高度正好是字符串的长度。
回溯的递归调用栈有时候可能会导致开销过大，这题其实可以直接用循环来做的，还是刚刚说的二叉树的思路，如果是数字那么直接进入只有一个子节点的下一层，也就是直接将当前字符拼接到字符串的末尾，而如果是字母的话就先复制一份到结果列表里，然后对这两个字符串分别加上大写和小写的当前字符，就相当于产生两个子节点，这样的操作一直到处理完整个输入字符串，也就是二叉树到了叶子节点，就得到了所有的排列情况：
class Solution {
public:
vector<string> letterCasePermutation(string S) {
vector<string> ans{""};
int sz;
for (char c : S) {
sz = ans.size();
for (int i = 0; i < sz; i++) {
if (c < 65) {
ans[i] += c;
} else {
ans.push_back(ans[i]);
ans[i] += c;
ans[i + sz] += c ^ 0x20;
}
}
}
return ans;
}
};
一个要注意的细节是 ans 数组需要一个空串作为初始值。以上两个解法在 LeetCode 上跑的时间都是 8ms，可能因为数据规模不大区分不出来？。
（话说越写越觉得这不是一道侧重位操作的题目 2333
Problem 476. Number Complement
题目要求是输出一个正整数二进制表达式从最高位 1 开始各位取反之后的数，这个在概念上是没有难度的，不过实现起来还是容易疏忽细节问题。比如说，按位取反 ~ 操作符取反的范围是整个数字的二进制表达形式，而不会去管在是不是最高位一之前，所以这样直接取反之后得到的数是不正确的，比如 101 如果存着的形式是 0000 0101，对它进行按位取反之后得到 1111 1010，而我们实际想要的是 0000 0010。
另外，这里因为题目是说给正整数，所以不用去考虑带符号整数相关的问题，举个简单例子：
unsigned int a = 11;
int b = 11;
std::cout << (~a) << " " << (~b);
// Outputs "4294967284 -12"
11 的二进制是 1011，在 4 字节存储下带有 28 个前导 0，取反之后得到的就是 1111 1111 1111 1111 1111 1111 1111 0100，作为无符号整数它的值是 4294967284，而作为带符号整数的话它就是 -12 了。
回到问题本身，既然不能整体一起取反，我们可以考虑分开一位位取反然后放进结果中，只要不断右移 n 然后取下最低位乘以当前次幂加进结果直到 n 为零也就是最高位 1 已经被处理过时停止：
class Solution {
public:
int findComplement(int num) {
int ans = 0, pos = 0;
while (num) {
ans += (!(num & 1)) << pos;
pos++;
num >>= 1;
}
return ans;
}
};
对一位比特进行的取反，因为刚刚提到的原因，同样不能够用按位取非操作来完成，毕竟计算机内部对这些数的处理都是以比特为最低单位的。但是逻辑取非就可以很好达到我们的需求：对 0 进行逻辑取非得 1，对被视为真的任何非零值（当然这里只会有 1 一个非零值）进行逻辑取非得到 false 也就是 0。
不过要注意这份代码是会对传入的 num 进行修改的，如果要求不能修改入参的话得加个临时变量来存。
这道题还有另一个思路，就是还是用对整体的取反来进行，但是是通过和一个低 n 位全为 1 的数字直接进行异或做到的，大致想法其实和掩码差不多，那么主要问题就变成了如何构造出这样一个数字。一个 n 位都为 1 的二进制数可以由 \(2^{n} - 1\) 得到，所以还是用原来的对入参值移位的方式我们就可以得到这个 n 的值，进而得到这个我们需要的数字。但是这次就必须得用个临时变量存入参了，不然拿到 n 之后就失去了异或操作的其中一个操作数。
int numdump = num, mask = 1;
while (numdump) {
mask <<= 1;
numdump >>= 1;
}
return num ^ (mask - 1);
亲测前后两种方法的 Runtime 分别是 0ms 和 4ms，看起来后者就多了一个异或而已，可是前者不是多了一次按位与吗，别的好像也没什么区别，难道又是因为测试数据规模小测不出差别。