就 計算機 而言，為什么大多數情況下非科班生 比不上 科班生

本文無意引戰，只是陳述自己在學習 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 上的一道中等難度的位運算題

題目鏈接在這里：大家之后可以去刷一下
只出現一次的數字 II

題目簡介

給你一個整數陣列 nums ，除某個元素僅出現一次外，其余每個元素都恰出現三次 ，請你找出并回傳那個只出現了一次的元素，

示例：
輸入：nums = [2,2,3,2]
輸出：3

暴力演算法

首先，能得到正確結果的演算法 >> 優美但只能看的演算法
循著這種思想，我們通常會寫一個暴力演算法理清思路

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

不要抱有饒幸心理，暴力演算法肯定不能通過的，實際中用暴力的情況也挺少，就算要用，都要加一大堆的優化

位運算優化

接下來要做的，就是應這道題的標簽——位運算，從數字的二進制表示去找規律

如果你找不到，不妨把數字寫下來，送給你認識的小學生的家長，他們的孩子可是這方面的能手

你看這些小學生多么認真，你過年過節好意思不送人一份試卷大禮包嗎？

這道題的規律還是挺好找的，除了 1 個妖怪，其他的數字都出現了 3 遍，將情況進行極端簡化就是 000 111 000 111 … 1 或者 000 … 0

如果沒有妖怪的存在，那么 0 和 1 的個數都是 3 的整數倍，誰多了 1 個就代表那個數字是誰，

把這種思想推廣到每一個位上，不難得到下面的代碼

int singleNumber(vector<int>& 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…)這種向量形式 的東西，由題意可得，輸出變數應該是 c n t i cnt_i cnti? 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<int>& 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<int>& nums) {
    int a = 0, b = 0;
    for (int num : nums) {
        b = ~a & (b ^ num);
        a = ~b & (a ^ num);
    }
    return b;
}

文章到這里就完了，其實寫這樣一篇文章并不是想說科班生就比非科班的有優越感，畢竟不付諸實踐的都是空中樓閣，
而且，在實際情況中，解決問題 >> 掌握知識

為了方便讀者閱讀和博客傳播，我建了一個公眾號 xioacd99

公眾號還提供每周科技資訊精選（我一直想做終于去做的東西）