跳到主要內容

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算法

留言

張貼留言

這個網誌中的熱門文章

架構設計 | 異步處理流程，多種實現模式詳解

本文源碼：GitHub·點這裏 || GitEE·點這裏 一、異步處理 1、異步概念 異步處理不用阻塞當前線程來等待處理完成，而是允許後續操作，直至其它線程將處理完成，並回調通知此線程。 必須強調一個基礎邏輯，異步是一種設計理念，異步操作不等於多線程，MQ中間件，或者消息廣播，這些是可以實現異步處理的方式。 同步處理和異步處理相對，需要實時處理並響應，一旦超過時間會結束會話，在該過程中調用方一直在等待響應方處理完成並返回。同步類似電話溝通，需要實時對話，異步則類似短信交流，發送消息之後無需保持等待狀態。 2、異步處理優點 雖然異步處理不能實時響應，但是處理複雜業務場景，多數情況都會使用異步處理。 異步可以解耦業務間的流程關聯，降低耦合度； 降低接口響應時間，例如用戶註冊，異步生成相關信息表； 異步可以提高系統性能，提升吞吐量； 流量削峰即把請求先承接下來，然後在異步處理； 異步用在不同服務間，可以隔離服務，避免雪崩； 異步處理的實現方式有很多種，常見多線程，消息中間件，發布訂閱的廣播模式，其根據邏輯在於先把請求承接下來，放入容器中，在從容器中把請求取出，統一調度處理。 注意 ：一定要監控任務是否產生積壓過度情況，任務如果積壓到雪崩之勢的地步，你會感覺每一片雪花都想勇闖天涯。 3、異步處理模式 異步流程處理的實現有好多方式，但是實際開發中常用的就那麼幾種，例如： 基於接口異步響應，常用在第三方對接流程； 基於消息生產和消費模式，解耦複雜流程； 基於發布和訂閱的廣播模式，常見系統通知 異步適用的業務場景，對數據強一致性的要求不高，異步處理的數據更多時候追求的是最終一致性。 二、接口響應異步 1、流程描述 基於接口異步響應的方式，有一個本地業務服務，第三方接口服務，流程如下： 本地服務發起請求，調用第三方服務接口； 請求包含業務參數，和成功或失敗的回調地址； 第三方服務實時響應流水號，作為該調用的標識； 之後第三方服務處理請求，得到最終處理結果； 如果處理成功，回調本地服務的成功通知接口； 如果處理失敗，回調本地服務的失敗通知接口； 整個流程基於部分異步和部分實時的模式，完整處理； 注意 ：如...
張貼留言
閱讀完整內容

.NET Core前後端分離快速開發框架(Core.3.0+AntdVue)

.NET Core前後端分離快速開發框架(Core.3.0+AntdVue) 目錄 引言 時間真快，轉眼今年又要過去了。回想今年，依次開源發布了 Colder.Fx.Net.AdminLTE(254Star) 、 Colder.Fx.Core.AdminLTE(335Star) 、 DotNettySocket(82Star) 、 IdHelper(47Star) ，這些框架及組件都是本着以實際出發，實事求是的態度，力求提高開發效率（我自己都是第一個使用者），目前來看反響不錯。但是隨着前端和後端技術的不斷變革，尤其是前端，目前大環境已經是前後端完全分離為主的開發模式，在這樣的大環境和必然趨勢之下，傳統的MVC就顯得有些落伍了。在這樣的背景下，一款前後端分離的.NET開發框架就顯得尤為必要，由此便定了框架的升級目標： 前後端分離 。 首先後端技術的選擇，從目前的數據來看，.NET Core的發展遠遠快於.NET Framework，最簡單的分析就是Colder.Fx.Core.AdminLTE發布比Colder.Fx.Net.AdminLTE晚，但是星星卻後來居上而且比前者多30%，並且這個差距在不斷擴大，由點及面的分析可以看出我們廣大.NET開發人員學習的熱情和积極向上的態度，並不是某些人所認為的那麼不堪（ 走自己的路，讓別人說去吧 ）。大環境上微軟积極擁抱開源，大力發展.NET Core， 可以說前途一片光明。因此後端決定採用 .NET Core3.0 ，不再浪費精力去支持.NET Framework。 然後是前端技術選擇，首選是三大js框架選擇，也是從實際出發，Vue相對其它而言更加容易上手，並且功能也毫不遜色，深得各種大小公司喜歡，如果偏要說缺點的話，那就是對TS支持不行，但是即將發布Vue3.0肯定會改變這一缺陷。選擇了Vue之後，然後就是UI框架的選擇了，這裏的選擇更多了，我選擇了Ant Design Vue，理由便是簡潔方便，十分符合我的設計理念。 技術選型完畢之後便...
張貼留言
閱讀完整內容

台北市住宅、社區建創儲能設備 最高可獲600萬元補助

為了推廣分散式發電，台北市環保局預計補助1億元供住宅社區設置創能、儲能設備，計有3種方案可供選擇。環保局說明，每案補助額度不超過建制總經費49％，社區每案最高可獲200萬至600萬元補助，住宅每案補助上限100萬元，5月1日起開放申請。 環保局說明，台北市溫室氣體排放量7成以上來自住商部門，其中以使用電力造成間接溫室氣體排放為大宗，台北市平均年用電量約159.86億度，1度電約等同排放0.5公斤二氧化碳，若想達成2050年淨零排放目標，僅靠節能減碳無法達成，必須發展綠色創能、儲能，並且參考歐洲、日本的做法，採分散式發電方式，推廣到社區、住家、商辦，達到供電自給自足目標。 因此，環保局推出「台北市住宅社區創能儲能及節能補助計畫」，補助對象為台北市轄內房屋所有權人及社區管理委員會，補助方案共計3種，每一申請人或每一場址僅能獲1次補助，每案補助額度不超過建置總經費49％為限，5月1日到7月31日開放申請，但補助經費用完即停止申請。 環保局說明，方案A補助對象以社區為主，公共區域申請創能儲能及節能項目，每案補助上限新台幣600萬元；方案B分為住宅或社區公共區域申請創能搭配儲能項目（創能或儲能方案不得單獨申請），社區每案補助上限新台幣400萬元，住宅每案補助上限100萬元。方案C補助對象也是社區，公共區域申請節能項目，每案補助上限新台幣200萬元。 網頁設計 最專業,超強功能平台可客製,窩窩以「數位行銷」「品牌經營」「網站與應用程式」「印刷品設計」等四大主軸，為每一位客戶客製建立行銷脈絡及洞燭市場先機,請問 台中電動車 哪裡在賣比較便宜可以到台中景泰電動車門市去看看總店：臺中市潭子區潭秀里雅潭路一段102-1號。 電動車補助 推薦評價好的 iphone維修 中心擁有專業的維修技術團隊，同時聘請資深iphone手機維修專家，現場說明手機問題，快速修理，沒修好不收錢住家的頂樓裝 太陽光電 聽說可發揮隔熱功效一線推薦東陽能源擁有核心技術、產品研發、系統規劃設置、專業團隊的太陽能發電廠商。 網頁設計 一頭霧水該從何著手呢? 回頭車 貨運收費標準宇安交通關係企業，自成立迄今，即秉持著「以誠待人」、「以實處事」的企業信念 台中搬家公司 教你幾個打包小技巧,輕鬆整理裝箱!還在煩惱搬家費用要多少哪？台中大展搬家線上試算搬家費用，從此不再擔心「物品怎麼計費」、「多...
張貼留言
閱讀完整內容