跳到主要內容

variable precision SWAR算法

      計算二進制形式中1的數量這種問題，在各種刷題網站上比較常見，以往都是選擇最笨的遍歷方法"矇混"過關。在了解Redis的過程中接觸到了variable precision SWAR算法（以下簡稱VP-SWAR算法），算法異常簡潔，是目前已知的同類方法中最快的。但如果對於位運算不是很熟悉的話，卻不一定容易理解，所以有必要記錄一下。


      下面先看看VP-SWAR算法的完整實現，然後再逐行解釋。


  public int vpSWAR(int i){ 
     i = (i & 0x55555555) + ((i>>1) & 0x55555555); 
     i = (i & 0x33333333) + ((i>>2) & 0x33333333); 
     i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F); 
     i = (i * 0x01010101) >> 24; 
     return i; 
   }

      VP-SWAR算法分為四步，第一步


i = (i & 0x55555555) + ((i>>1) & 0x55555555);

      第一步的作用是計算每兩位為一組的二進制形式包含1的個數。要理解這句話，我們需要從二進制的角度看看到底發生了什麼。首先， 0x55555555 的二進製表示為 0101 0101 0101 0101 0101 0101 0101 0101 ，這個数字的規律是基數位為1，偶數位為0。為簡單起見，我們只考慮兩位，總共有四種情況，即：


 






























i b i & b 結果
00 01 00
01 01 01
10 01 00
11 01 01


       觀察發現， i & (0b01) 是i的基數位對應b的1位，i的偶數位對應着b的0位， i & (0b01) 的結果會將I的偶數位置為0，而基數位保持不變，得到的結果就是i的基數位包含1的個數。 (i >> 1) & 0x55555555 先將i右移一位，也就是將i的基數位對應b的0位，i的偶數位對應着b的1位，然後再與 0x55555555 按位與，計算出來的是i的偶數位包含1的個數。兩個計算結果相加就得到i每兩位為一組中包含的1的數量，我們最後需要的就是這每兩位一組的和。


      第二步是在第一步的基礎上，計算每四位為一組包含1的個數。按照每2位為一組分組用到了 0x55555555 這個數，那麼自然的，按照每4位為一組分組自然就需要 0b0011 這種形式，這就是使用 0x33333333 的原因。理論上， i & (0b0011) 總共有16種情況，但是四位二進制位最多包含4個1，用二進製表示為 0b0100 ，所以經過第一步之後，i最多有5種取值，如下：



































i b i & b 結果
0000 0011 0000
0001 0011 0001
0010 0011 0010
0011 0011 0011
0100 0011 0000

 


      觀察發現， i & (0b0011) 得到的是i的低兩位包含的1的個數，  (i >> 2) & 0b0011 )得到的是i的高兩位包含的1的個數，兩個結果相加得到每四位包含的1的個數。注意，這裏並不是說任何數與 0b0011 按位與得到的都是低兩位包含的1的個數，這裏的前提是第一步的計算，因為經過第一步計算之後，每兩位包含多少個1已經記錄了下來，再和 0b0011 按位與才得到正確的結果。例如， 0x0010 & 0x 0011=0x0010 ，但是我們不能說 0x0010 包含兩個1，但是如果 0x0010 是經過第一步的計算得來，那才說明 0x0010 記錄原始數據低兩位有兩個1。


      第三步在第二步基礎上，計算每8位有多少個1，由 0x01 和 0x0011 ，很自然想到 0x00001111 ，其對應的32位的十六進制數就是 0x0F0F0F0F 。


      第四步就很有意思了，它不再是計算每16位包含1的個數，而是直接計算32位包含1的個數。對於32位的數來說，可以將其按每8位一組分為4組，分別用ABCD表示，例如 0x01020304 用這種形式表示為：



 


 


      假設 0x01020304 是經過前三步計算之後得到的結果，那麼要計算其總共包含多少個1，只需計算A+B+C+D。而ABCD表示的是不同的位區間範圍，不能直接相加，該如何快速計算A+B+C+D的值呢？這裏又用到了移位運算，將B、C、D分別左移8位、16位、24位，使其分別與A對齊：



 


       我們發現，將数字i分別左移0位、8位、16位、24位然後相加的結果，就是 i * 0x01010101 ，因為 i + (i << 8) + (i << 16) + (i << 24) = i * (1 + 1 << 8 + 1 << 16 + 1 << 24) = i * 0x01010101 。對於32位数字來說，左移之後超過32位的部分會被捨棄，低位補0，將左移之後得到的四個数字相加，結果的高8位的值就是原32位數包含的1的個數，要得到這個值，只需要將結果右移24位，將值放在低8位即可。


      到這裏，整個算法就結束了，右移的結果就是1的數量。在Redis中，BITCOUNT命令同時使用了查表法和VP-SWAR這兩種方法。當要計算的位數小於128位時，使用查表法，否則使用VP-SWAR算法。其中查表法的做法是，程序先存一個256長度的表，按順序記錄從0-255（即 0b00000000 - 0b11111111） 數中二進制1的個數，然後對於輸入參數每8位查一次表。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!



※網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司，幫您輕鬆架站!



※想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!


Orignal From: variable precision SWAR算法

留言

張貼留言

這個網誌中的熱門文章

有了四步解題法模板，再也不害怕動態規劃！（看不懂算我輸）

導言 動態規劃問題一直是算法面試當中的重點和難點，並且動態規劃這種通過空間換取時間的算法思想在實際的工作中也會被頻繁用到，這篇文章的目的主要是解釋清楚 什麼是動態規劃 ，還有就是面對一道動態規劃問題，一般的 思考步驟 以及其中的注意事項等等，最後通過幾道題目將理論和實踐結合。 什麼是動態規劃 如果你還沒有聽說過動態規劃，或者僅僅只有耳聞，或許你可以看看 Quora 上面的這個 回答 。 How to explain dynamic 用一句話解釋動態規劃就是 " 記住你之前做過的事 "，如果更準確些，其實是 " 記住你之前得到的答案 "。 我舉個大家工作中經常遇到的例子。 在軟件開發中，大家經常會遇到一些系統配置的問題，配置不對，系統就會報錯，這個時候一般都會去 Google 或者是查閱相關的文檔，花了一定的時間將配置修改好。 過了一段時間，去到另一個系統，遇到類似的問題，這個時候已經記不清之前修改過的配置文件長什麼樣，這個時候有兩種方案，一種方案還是去 Google 或者查閱文檔，另一種方案是借鑒之前修改過的配置，第一種做法其實是萬金油，因為你遇到的任何問題其實都可以去 Google，去查閱相關文件找答案，但是這會花費一定的時間，相比之下，第二種方案肯定會更加地節約時間，但是這個方案是有條件的，條件如下： 之前的問題和當前的問題有着關聯性，換句話說，之前問題得到的答案可以幫助解決當前問題 需要記錄之前問題的答案 當然在這個例子中，可以看到的是，上面這兩個條件均滿足，大可去到之前配置過的文件中，將配置拷貝過來，然後做些細微的調整即可解決當前問題，節約了大量的時間。 不知道你是否從這些描述中發現，對於一個動態規劃問題，我們只需要從兩個方面考慮，那就是 找出問題之間的聯繫 ，以及 記錄答案 ，這裏的難點其實是找出問題之間的聯繫，記錄答案只是順帶的事情，利用一些簡單的數據結構就可以做到。 概念 上面的解釋如果大家可以理解的話，接    動態規劃 算法是通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞推（或者說分治）的方式去解決。它的幾個重要概念如下所述。    階段： 對於一個完整的問題過程，適當的切分為若干個相互聯繫的子問題，每次在求解一個子問題...
張貼留言
閱讀完整內容

計算機本地文件快要滅絕了

　　 編者按： 文件是数字世界的基石，是我們基本的工作單位。但是，隨着互聯網的雲化、平台化、服務化，文件日益變得可有可無。這樣一種改變究竟好不好呢？喜歡懷舊的 Simon Pitt 開始回顧各種文件的好處，哪怕這讓他顯得不合時宜。原文發表在 medium 上，標題是：Computer Files Are Going Extinct 　　我喜歡文件。我喜歡對文件重命名、移動、排序，改變它們在文件夾中的显示方式，去備份文件，將之上傳到互聯網，恢復它們，對其進行複製，甚至還可以對文件進行碎片整理。作為信息存儲方式的一種隱喻，在我看來文件是很出色的。我喜歡把文件當作一個工作單位。如果我要寫篇文章，文章會放在文件裏面。如果我要生成圖像，圖像會保存進文件裏面。 　　 謳歌 files.doc 　　文件是擬物化的。這是個很花哨的詞，只是用來表示文件是反映現實物品的一個数字概念。比方說，Word 文檔就像一張紙，躺在你的辦公桌上（desktop）。JPEG 就像一幅畫，等等。它們每個都有一個小圖標，圖標的樣子看起來像它們所代表的現實物品。一堆紙，一個畫框，一個馬尼拉文件夾。真的挺很迷人的。 　　我喜歡文件的一點是，不管裏面有什麼，跟文件的交互方式總是一致的。我上面提到的那些東西——複製、排序、碎片整理——我可以對任何文件進行那些處理。文件可能是圖像、遊戲的一部分、也可能是我最喜歡的餐具清單。碎片整理程序不在乎它是什麼。它不會去判斷內容。 　　自從我開始在 Windows 95 裏面創建文件以來，我就一直都很喜歡文件。但是我注意到我們已經開始慢慢地遠離把文件當作基本工作單位的做法。 Windows95。我的計算機 　　 services.mp3 的興起 　　十幾歲的時候，我開始痴迷於收集和管理数字音樂：我收藏 MP3 文件。一大堆的 128 kbps MP3 文件。如果你足夠幸運，有自己的 CD 刻錄機的話，就可以將它們刻錄到 CD 上，然後在朋友之間傳遞。一張 CD 可以容納 700 MB。這相當於將近 500 張軟盤！ 　　我會仔細端詳我的收藏，然後煞費苦心地給它們添加上 IDv1 和 IDv2 音樂標籤。隨着時間的流逝，大家開始開發可以在雲端自動獲取曲目列表的工具，這樣你就可以檢查和驗證 MP3 的質量。有時候我甚至會去聽那些該死的東西，儘管...
張貼留言
閱讀完整內容

純電動 Mini Cooper SE 將成為中國國產車，年產 16 萬輛

BMW 集團與中國長城汽車合資，將於江蘇建立新廠，專門投入生產 MINI Cooper SE 和部分長城品牌電動車，預計於 2022 年完工並投入生產，每年將可生產 16 萬輛電動車。 靈動可愛的 Mini Cooper，在許多車迷心中都有著特殊的地位，今年 7 月發表了首款純電動版本的 Mini Cooper SE 之後，獲得熱烈迴響，預訂數量已接近 8 萬台，顯示大家對於純電 Mini 的熱愛，因為油電版的 Mini Cooper Countryman 的全球總銷售量也才 3 萬出頭。 Mini Cooper SE 之前公布了官方定價，最低從 27,900 歐元起算，美國售價約 29,900 美元。相比現有的三門款，只貴了一成左右。然而，三年後，中國消費者將有機會買到最便宜的電動 Mini。 電動 Mini Cooper SE 最低價是 27,900 歐元，扣掉全額補助最低可以到 24,400 歐元。 BMW 集團與中國長城汽車集團於 2018 年宣布，將組建合資公司光束汽車，投入在中國的電動車生產計畫，而現在他們正式宣布啟動計畫，於江蘇張家港打造一個新工廠，全部投入電動車的製造，包括了 Mini Cooper SE 和其他長城汽車旗下的電動車。 目前的電動 Mini 只在英國牛津工廠製造，不難想像當產能轉移到中國後，Mini Cooper SE 的價格將有機會進一步調降，來競爭全球最大的電動車市場。這座屬於合資公司光束汽車的新工廠，採用一個新的產銷模式，由 BMW 和長城共同合作開發、設計、製造新產品，但是銷售通路完全沿用原本的品牌渠道。 換句話說，2020 年到 2022 年銷售的電動 Mini，將會是英國製造，而 2022 年後就會有中國製造版本開賣，考量到 Mini 在中國每年約有 30 萬輛的銷售額，同時油電版的 Coutryman 銷量更佔了全球將近五分之一，無怪乎 BMW 會想在最接近主要市場的地方蓋工廠囉。 外型完美復刻油車版 最後，簡單介紹一下 Mini Cooper SE 這台車。Mini 在電動化的路上，盡力保持著跟經典造型一致的設計，畢竟大家愛的就是它的設計。電動版的 Mini 車頭、車身跟車屁股都多了一個黃色的插頭標誌，車頭的氣壩則變成封閉式設計，除此之外，幾乎看不出來差別，連馬達...
張貼留言
閱讀完整內容