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

本文无意引战，只是陈述自己在学习 CS 过程中的感受。

声明如下

1. 本文观点通过对大多数情况的不完全归纳得到，CS 吊车尾和非 CS 怪物的存在并未纳入考虑范围。此外，非科班生和科班生的选取遵守对照原则和单一变量原则——在本文中具体体现为专业排名相近、智力相近、性别相同、性格相近等，评价指标为算法理解能力、工程代码能力。

2. 本文观点并不是建立在严谨的实验或推理上得到的，并不具备可信度，权当玩笑话。

3. 本文所讨论的 CS 科班生为系统学习了 CS 核心课程的人、并不局限于计算机专业

4. 图源来自网络，如果有侵犯您的权益，请联系作者以删除。

---

欢迎来到正文部分

随着对 CS 了解的加深，我愈发有这样一种感觉——计算机的学生学的真的是计算机，所有的课程、分支都是

在教你用得好（如软件工程）、用的新（如人工智能、图形学）、用的妙（如计组、算法）。这让我有些担心——计算机鲜明、 强烈的工具导向是否会逐渐磨灭我们那种 wow 的感觉和提问的乐趣呢？有失必有得，回报就是对计算机的理解的加深。

Matt Might 在 What every computer science major should know 中谈到如何学体系结构时，认为 Computer scientists should understand a computer from the transistors up.

在我刚入学的时候也常常听人说起：计算机学生大四毕业的时候所有学过的课程都会在脑海里串成一张相互联系的网络。

这种网络，是 CS 学生用自己的时间堆出来的，也是科班生与非科班生一个重大差异

下面本文就一道简单的算法题为例具体谈谈这种让人“舒服”的联系

这是 LeetCode 上的一道中等难度的位运算题

题目链接在这里：大家之后可以去刷一下

题目简介

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次 。请你找出并返回那个只出现了一次的元素。

示例：

输入：nums = [2,2,3,2] 输出：3

暴力算法

首先，能得到正确结果的算法 >> 优美但只能看的算法

循着这种思想，我们通常会写一个暴力算法理清思路

int singleNumber(vector
   
    & nums) {       unordered_map
    
      numTimes;    ...    for (int num : nums) {           ++numTimes[num];    }    ...}
    
   

不要抱有饶幸心理，暴力算法肯定不能通过的，实际中用暴力的情况也挺少，就算要用，都要加一大堆的优化

位运算优化

接下来要做的，就是应这道题的标签——位运算，从数字的二进制表示去找规律

如果你找不到，不妨把数字写下来，送给你认识的小学生的家长，他们的孩子可是这方面的能手

你看这些小学生多么认真，你过年过节好意思不送人一份试卷大礼包吗？

这道题的规律还是挺好找的，除了 1 个妖怪，其他的数字都出现了 3 遍。将情况进行极端简化就是 000 111 000 111 … 1 或者 000 … 0

如果没有妖怪的存在，那么 0 和 1 的个数都是 3 的整数倍。谁多了 1 个就代表那个数字是谁。

把这种思想推广到每一个位上，不难得到下面的代码

int singleNumber(vector
   
    & nums) {       int ans = 0;    for (int i = 0; i < 32; ++i) {           int cnt = 0;        for (int num : nums) {               // 这一步的等式右边是取出num的第i位二进制表示            cnt += ((num >> i) & 0x1);        }        if (cnt % 3 == 1) {               ans |= (0x1 << i);        }    }    return ans;}
   

非科班生做到这里基本上就准备收笔了。他们碰到位运算，一般就是找点数字表示规律加上一些数学性质（如余数的性质）就完了。

数电优化

但是，当看到问题的解可以伸到数据的二进制表示的时候，一名 CS 科班生他就兴奋起来了。耗子滴滴，向数电进发、向计组进发、向计算方法进发

由于本人知识浅薄，对计组层面的了解远远达不到实现有效率优化的地步，加之这个层面的优化涉及到不同的指令集。如针对 MIPS 和 X86 的改良版本不同，后面本文主要谈数电和计算方法层面的优化

如果从算法的角度来看，在位运算的区域里已经基本无法改进了。仔细分析，就会发现一个潜在的思路——1 位和 1 个整体有区别吗？是否可以直接对整体进行处理呢？这就引出了后面的数电方法

你的数电复习课来了

如何设计组合逻辑电路

1. 确定输入输出变量
2. 写真值表
3. 写逻辑表达式
4. 化解逻辑表达式
5. 用门器件或 MSI 实现（毕竟用不到那么多，就写到这里）
   …

输入变量当然是数组中的数了，那输出变量是什么呢？

回顾前面的思路，我们想得到的其实是最后结果每一位的二进制数。可以猜想输出变量是一个类似 (ai, bi, ci…)这种向量形式 的东西。由题意可得，输出变量应该是 $cn{t}_i$ mod 3 的结果，即 0 / 1 / 2。但二进制里可没 2 呀，这可咋整？难不成弄一个 3 进制？

这里就用到存储中经常出现的一种处理方法，范围不够、位数来凑。多了咋办，不要就完了呗

于是我们尝试以(ai, bi)为输入变量进行验证

• (0, 0)表示 0
• (0, 1)表示 1
• (1, 1)表示 2

这里需要注意一点：(ai, bi) 会以 00 -> 01 -> 10 -> 00 的顺序进行循环（“防串味”）

这里不对“防串味”做出具体解释，如果读者理解了前面的思路，那么这里不成问题；否则请读者返回前面思考算法的核心思想

当 nums[i] 为 0 时不做处理，当 nums[i] 为 1 的时候向后循环一步

注：这里还有一个和题有关的地方，因为题中是 3对1，所以（ai，bi）最后只能是 00/01（从 00 开始） 而 3 个 1/0 都会回到 00，而 0 和 1 分别对应 00 和 01，所以最后只需要返回 b

画真值表、写表达式

最后的结果为

之后我们就可以写出大家不喜欢看但计算机喜欢的代码了

int singleNumber(vector
   
    & nums) {       int a = 0, b = 0;    for (int num : nums) {           int ai = (~a & b & num) | (a & ~b & ~num);        int bi = ~a & (b ^ num);        a = ai;        b = bi;    }    return b;}
   

数值计算

聪明的同学会思考，ai的计算方法那么复杂，可不可以简化呢？

通过采用数值计算/凸优化里分别求解，利用新值加快收敛的思想对ai的更新方式进行改进

因为 b 的值好算，那么就先算 b 的值，然后用 bi_old 替代 bi 重新写真值表，列表达式（最后得到的结果确实漂亮）

int singleNumber(vector
   
    & nums) {       int a = 0, b = 0;    for (int num : nums) {           b = ~a & (b ^ num);        a = ~b & (a ^ num);    }    return b;}
   

文章到这里就完了。其实写这样一篇文章并不是想说科班生就比非科班的有优越感，毕竟不付诸实践的都是空中楼阁。

而且，在实际情况中，解决问题 >> 掌握知识

---

为了方便读者阅读和博客传播，我建了一个公众号 xioacd99

公众号还提供每周科技资讯精选（我一直想做终于去做的东西）