Menu

Subscribe

从《编程之美》中的一道面试题开始谈谈位操作

on Program, Bit Manipulation

文章目录

在计算机的内部，数据都是使用二进制表示的，而对于计算机来说，进行基于二进制的位操作，效率要比进行除法、取余等操作高很多。最常见的对代码的优化就包含将乘除 2 的幂操作改为左右移位操作，很多时候编译器也会对代码自动执行这个优化。

我第一次在算法题的代码里见到位操作应该是在高二的时候，某个晚自习不想学习然后跑到机房去乱翻别人的博客发现这个，顿时就感觉如沐春风出神入化，所以一直印象挺深刻的。这个学期开学后不久在图书馆发现了《编程之美》这本书，虽然里面的好多内容都看不懂，其中有一道题感觉还蛮有趣的，就想从这道题出发，简单整理一下自己了解过的一些位操作相关的知识。

题目是这样的：

2.1 求二进制数中 1 的个数

对于一个字节（8 bits）的变量，求其二进制表示中 “1” 的个数，要求算法的执行效率尽可能地高。

Note：以下和题目相关的代码中，n 表示输入变量，ans 表示运算结果。

常规思路

直觉告诉我们，大概也许应该可能差不多需要先将变量值转化为二进制，然后统计这个二进制表示中有多少个 1，最直接的方式当然是每次除以二取余然后累加这个余数了：

while (n)  
{
    ans += n % 2;
    // Same as:
    // if (n % 2 == 1) ans++;
    n /= 2;
}

当然如果了解过位操作的话就可以直接把乘法换成右移，取余换成和 1 进行按位与操作：

while (n)  
{
    ans += n & 1;
    n >>= 1;
}

看起来代码并没有太大不同，但是正如文章开头所说，使用位操作的效率要比除法和取余高很多。尽管如此，优化只是作用在了常数上，两者的时间复杂度还是一样的 \(O(\log n)\)，其中 \(\log n\) 为 n 的二进制表示的位数。

降低时间复杂度

原理

书上给出了一种时间复杂度更低的解法，它基于这样的一个操作：

n &= (n - 1)

这个操作本身的作用是将 n 的最低位 1 置零，我们可以来看一下下面三个例子：

1011 - 0001 = 1010 (& 1011 = 1010)  
1010 - 0001 = 1001 (& 1010 = 1000)  
1100 - 0001 = 1011 (& 1100 = 1000)

稍微分析一下，不难看出为什么上述操作可以达到将最低位 1 置零的效果：

  • 如果 n 的末位就是 1，那么 n - 1 与 n 只有末位不同，与操作之后就保留了前面的所有位不变而将末位变为了 0。
  • 如果 n 的末位不是 1，那么减法也不会影响到最低位 1 前面的数，而只会将它及其后的所有位取反（因为有一个借位的逻辑）。这样相反的位再进行与操作后就自然全部都是 0 了，也就是说最低位 1 及其后的所有位都变为了 0，效果上就是最低位 1 被置零。

（不知道是不是描述得有点乱23333

应用

这个操作的特性在这道题上可以完美利用上，我们只需要每次将最低位 1 置零然后累加操作次数，最后的结果正好就是其二进制表示中含有的 1 的个数：

while (n)  
{
    n &= n - 1;
    ans++;
}

这个算法的时间复杂度降到了 \(O(M)\)，其中 \(M\) 为 ans 的大小，也就是 n 的二进制表示中含有的 1 的个数。现在算法的复杂度只与 1 的个数有关了，相对原来的与总位数有关算是降低了一些。

进一步了解执行效率

打表

写算法题代码的时候，有时为了效率会用空间换取时间，常见的一种骚操作就是打表，也就是预先算好所有的结果后放到一个数组中，运行的时候不需要进行计算而只需要访问对应下标的值即可，时间复杂度是 \(O(1)\)。

这个方法的代码我就不贴了233333，感觉面试的时候并不太敢这么做，怕是会被打死[捂脸]。不过这个题目给定了变量是一个字节的，可能也有让面试者往这个方向思考的意思，毕竟如果访问量巨大而输入范围很小的话，提前算好值然后查表取肯定是比每次重新计算的效率高很多的，所以还是取决于具体情景。

分支

关于执行效率，额外想谈一下书上提到的对另一种解法的分析，也就是用类似打表的方式罗列出所有的情况，但是使用分支语句进行执行而非直接通过下标访问数组，代码类似这样：

switch (n)  
{
    case 0x00: // 0
        ans = 0;
        break;
    case 0x01: // 1
    case 0x02: // 2
    case 0x04: // 4
    case 0x08: // 8
    case 0x10: // 16
    case 0x20: // 32
    case 0x40: // 64
    case 0x80: // 128
        ans = 1;
        break;
    // ...
}

乍一看感觉好像效率和上面的那个 \(O(1)\) 算法差不多，但是仔细思考一下就会发现问题：switch 语句是会将表达式的值与每个 case 后的值进行逐一比较的，那么如果输入的 n 在这段语句偏后的部分，就需要进行多次比较后才能得到结果，几乎相当于对输入范围进行了一遍枚举，所以实际的执行效率可能甚至会低于最开始提到的两个算法。

微小的拓展

将最低位 0 置一

有了将最低位 1 置零的操作，我们可能会考虑是不是应该也有将最低位 0 置一的操作（逃

其实对比分析一下两者的操作，然后又因为它们是相对的运算，很容易发现把各运算符取反一下就可以达到要求了：

n |= (n + 1)
判断 2 的幂

2 的幂的二进制表示显然有个特点就是有且只有一位是 1，那么在理解了 \(O(M)\) 那个解法后，其实也容易想到，如果将最低位 1 置零后与原数进行与操作，结果就能表示这个数是不是 2 的幂了：

bool isPowerOfTwo = (!(n & (n - 1))) && (n > 0)

核心的判断就在 n & (n - 1) 的运算结果，这个值如果为零就说明 n 只有一位是 1，也就代表 n 是 2 的幂。有趣的是在翻到下一题的最后有个“相关题目”一栏，里面也给出了这个题目和提示，当时看到的时候有种莫名的惊喜感hhh 明明是我先来的.jpg（

微大的拓展

谈及位操作，也顺带一提关于 ASCII 大小写字母转换的一个 trick。

我们知道大写字母 A 的 ASCII 码是 65，小写 a 是 97，两者相差 32，并且之后的所有字母大小写相差都是按顺序同步下去的。之前在看王爽老师的《汇编语言》时，7.4 节（第三版里面）就提出了关于字母大小写转换的问题。

很容易想到的转换实现方案就是对大写字母加上 32，对小写字母减去 32，但是这样又涉及到了一个判断的问题，有没有其它更简洁的解决办法呢？这里就可以用上位运算的一些特性了，32 正好是 \(2^5\)，也就是对应 ASCII 码二进制表示的右起第六位（从一开始计数 = =），那么把这一位设置为 1 就可以保证结果是小写字母而不用考虑它原来是什么，反之设置为 0 的结果就一定是大写字母了。

那如果要求就是把大写字母变成小写，小写字母变成大写的话，还可以不通过判断实现吗？如果理解了上面的操作，那么就很容易想到这个问题其实就等同于将某一个特定位置的二进制位的值进行反转的问题，而针对特定位的反转，取非操作相对来说还是麻烦了一点，直接通过和这个位对应的值进行异或操作来实现会简洁很多。

在给代码之前先 xjb 提一下针对右起第 n 个二进制位的设置操作，首先最简单的当然是设为 1 了，直接和 1 << n 进行按位或就行，同样地，反转一个位只需要直接和它进行按位异或：num ^ (1 << n)。将某一位设为 0 就需要用【第 n 位为 0 而其它位全为 1 】的数进行按位与操作，很显然我们需要的这个数和刚刚提到的数是每一位都相反的，所以中间进行一次取反操作即可获得，也就是结果为 num & ~(1 << n)。对应下来，字母大小写转换相关操作代码如下：

// 0x20 stands for 32 in decimal

char upper = code & ~(0x20);  
char lower = code | 0x20;  
char reverse = code ^ 0x20;

如果想让代码看起来更有趣（骚）一点的话，可以把 0x20 改成 ' '，毕竟空格的 ASCII 码正好就是 32，有没有觉得这个 ASCII 码表的设计好美妙嘿嘿嘿。

文章封面图片来自 VideoBlocks。

文章版权声明