一行代碼搞定整數二進位中的連續 1 判定！

作者 | veelion

責編 | 郭芮

碰到一個利用位元組位操作解決的問題，如何判斷一個整數的二進位是否含有至少兩個連續的1？

問題本身並不複雜，利用二進位的未操作即可完成，方法也有多種。不同方法的效率也差很多，下面我們分別利用Python和C來實現並對比一下。

方法一：從頭到尾遍歷一遍每一位即可找出是否有連續的1存在

這個方法是最普遍的、第一感覺就能想到的方法，下面我們看一下它的具體實現。

Python代碼：

上面的實現中，對於整數n先做取余運算（n % 2）。如果餘數為1，則n的最後一位是1，否則為0，並用this_is_one記錄當前位；然後判斷一下，這次和上次的最後一位是不是都是1。如果是，則可以判定該整數有兩個連續的1，否則把n向左移一位，繼續循環開始的取余操作。

方法二：無需遍歷每一位，但還是位操作：移一位（左移、右移皆可）然後和原數「位與」一下即可

這個原理不複雜，思考一下：

如果有兩個連續的位為1，原數和移為後的數「位與」操作，就是會發生這兩個連續的1進行「位與操作」，則結果中必出現至少一個位為1 (1&1 == 1)，結果不為零；

如果沒有至少兩個連續的位為1，則1的兩邊都是0，原數和移為後的數「位與」操作，就是1與兩邊的0進行「位與操作」，則所有的1都變成了0 (1&0 == 0)，結果必為零。

由以上推理，演算法就簡化了很多，只用一行代碼即可搞定。

Python代碼：

那麼，上面兩種方法的效率差多少呢，我們來測試一下看看：

Python代碼：

看一下運行結果，循環1百萬次，方法二的速度是方法一的4倍多：

接下來，用C實現一下看看效率如何：

C語言代碼：

編譯並運行以上C代碼：

從以上結果看，C語言實現的演算法二比演算法一塊十幾倍。

編譯優化後運行：

編譯器優化後的結果，演算法二比演算法一塊4倍多，但都比未優化的快了很多。

順便也「自黑」一下Python的性能，確實比起C來差很遠。但是合適的工具做適合的事情永遠是對的，不妨理解一下下面這段引文：

有個需要每天運行的Python程序，運行大概需要1.5秒。

我花了六小時用Rust重寫它，現在運行需要0.06秒。

效率的提升意味著，我要花41年零24天，才能找回我多花的時間......

作者：veelion，具有十年開發經驗，主要使用Python、C++語言，從事網路爬蟲、搜索引擎、自然語言理解處理等領域的研發工作。

聲明：本文為作者投稿，版權歸對方所有。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！