iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 15
1
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 15

【從面試題學邏輯-15】Java Integer.bitCount() 原理,當程式達到極致後……就看不懂了!?

今天是Extra系列!

由於前面有用到Java的Integer.bitCount(),我們也說會來講解一下

那今天就來講吧!/images/emoticon/emoticon08.gif

大家可能會想:它是不是就一個迴圈,跑N個位元累計一下就好?

事實上呢……

請看!

這是什麼!?!?!?!? /images/emoticon/emoticon04.gif

這就是程式效率達到極致的……………天書啊!

好啦,那我們逐一的講解下去

(以下會用到前幾篇講到的東西,還沒看過建議先去看一下)


簡單來說bitCount()的原理是這樣

  • 把原本二進位進行分組,把那組的數字變成表示原本小組中有幾個1
  • 把有幾個1的數字合併相加

變為表示幾個1的舉例,假設四個一組:

  • 1111 → 0100 [0100十進位是4,表示原本小組中有4個1]
  • 0010 → 0001 [0001十進位是1,表示原本小組中有1個1]
  • 0100 → 0001 [和上面一樣,1在哪個位置不影響]

接下來我們一行一行講解

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

這個步驟是兩兩分組,2個位元一組(參考上面的顏色)

  • 左邊的i代表的是很多小組合起來的數字,這些分組代表原本數字某個區塊中有幾個1
  • i >>> 1 → 向右移一位,代表原本是第二位的位元現在是第一位的位元
  • (i >>> 1) & 0x55555555代表只留下第一位的位元

所以為什麼要這樣做?好像有點抽象?接下來看例子

如果偶數位是1,在十進位代表2,所以要減掉向右位移的自己(變成1)才能取到1(反正2-1才會變成1啦)
簡單來說,就是變成說明原本小組中有幾個1的東西

i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

這一步驟就是各小組兩兩合併,變成4個位元一組
是相加而不是相減的原因是,這串數字已經是代表有幾個1的數字了,而不是原本的數字
(i >>> 2) & 0x33333333表示取出前面小組的數字,原理和上一步相同

有沒有覺得好像發現什麼規律了?

i = (i + (i >>> 4)) & 0x0f0f0f0f;

各小組兩兩合併成8個位元一組
& 0x0f0f0f0f 表示去掉前面小組的數字,因為你已經把前面小組加到後面小組了

i = i + (i >>> 8);

各小組兩兩合併成16個位元一組
大家可能會好奇,為什麼這裡沒有做Mask,後面會解釋(注意這步是兩個8位元一組的小組合併)

i = i + (i >>> 16);

最後兩組合併

return i & 0x3f;

0x3f → 00111111
32位元的數字最多就32個1,而32的二進位是00100000,所以這個1前面的必定是0
前面兩步驟不做Mask的原因是,在最後一次濾掉比較有效率(前面濾後面濾效果都一樣)
簡單來說就是 「前面的數字就隨便讓他加,反正最後都會刪掉」

整體步驟整理

  • 把原本數字變成代表小組內有幾個1的數字,並兩兩分組
  • 兩兩合併成4個位元一組,刪掉前面小組
  • 兩兩合併成8個位元一組,刪掉前面小組
  • 兩兩合併成16個位元一組
  • 最後兩組合併
  • 取有用的最後6個位元,return

還是很抽象怎麼辦?

個人建議再多思考一下,因為它本來就不是一下子就能想通的東西/images/emoticon/emoticon15.gif
過去曾經有實際講解過這個東西,那問題其實就在有沒有「想通」。它雖然是效率的極致,但了解背後原理就會發現,其實沒有想像中恐怖,反而還會覺得挺有趣的。/images/emoticon/emoticon14.gif


上一篇
【從面試題學邏輯-14】你看過灑可可粉,那你看過撒0和1嗎?(CTCI 5.1 在二進位中插入另一個二進位)
下一篇
【從面試題學邏輯-16】拔智齒可以不要寫鐵人賽嗎?好像不能這樣做诶(leetcode 78. Subsets)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言