Re: [心得] Bitwise parallel
※ 引述《saka037 (蝙輻超人)》之銘言：
: 原文恕刪~
: 這份筆記寫得很好~本來要問的都有了~但....才疏學淺，看不懂
: 小弟也許觀念錯很大~請大家不吝指教~~
: : 假設給定一個32bit無號整數，如果以byte為單位切成四份，求這四份的數字總合。
: : 範例 0x09ABCDEF -> 0x09 + 0xAB + 0xCD + 0xEF
: : 直覺的方法就是
: : x & 0xFF + (x&0xFF00 >> 8) + (x&0xFF0000 >> 16) + (x&0xFF000000 >> 24)
: x& 0xFF
: 假設 x 01010101 ----------------32bits
: & 11111111 000000000000000032bits
: ---------------------------------------這樣可以取到前8bits沒錯
: x&0xFF00 >> 8
: x 01010101 10101010 ---------------
: & 11111111 00000000 ---------------
: ------------------------------------------------
: 01010101 00000000
: >> 00000000 01010101
: 這樣不也是只取到前8bits，沒記錯的話「&」和「>>」不是優先順序一樣，
: 所以會由左而右計算，但如果改成 x & (0xFF00 >> 8)是不是比較正確
: 0xFF00 11111111 00000000
: >> 00000000 11111111
: x 01010101 10101010
: ------------------------------------------
: 00000000 10101010 取到第9~16位元
就拿原PO舉的 0x09ABCDEF 來演示
00001001 10101011 11001101 11101111 (0x09ABCDEF)
& 00000000 00000000 00000000 11111111 (0x FF) (你把這個的位置給弄錯了)
---------------------------------------
00000000 00000000 00000000 11101111 (0x EF)
00001001 10101011 11001101 11101111 (0x09ABCDEF)
& 00000000 00000000 11111111 00000000 (0x FF00)
---------------------------------------
00000000 00000000 11001101 00000000 (0x CD00)
>> 00000000 00000000 00000000 11001101 (0x CD)
依此類推
你改成那樣反而和 x & 0xFF 才一樣...
: : 同樣的技巧，也可以用來做把整數中的bit反轉的動作
: : （簡單的實作需要16次的交換）
: : x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
: : x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
: : x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
: : x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
: : x = ( x >> 16 ) | ( x << 16);
: 哇~~這完全看不懂~還畫了32bits跟著照做~結果算到腦袋發空~
: 可否麻煩好心人士解釋一下原理~萬分感謝~
將這 32 bit 編號:
abcdefgh ijklmnop qrstuvwx yz@#$%&*
第一行 (x >> 1) & 0x55555555 和 (x & 0x55555555) << 1 :
abcdefgh ijklmnop qrstuvwx yz@#$%&*
>> 0abcdefg hijklmno pqrstuvw xyz@#$%&
& 01010101 01010101 01010101 01010101
---------------------------------------
0a0c0e0g 0i0k0m0o 0q0s0u0w 0y0@0$0%
abcdefgh ijklmnop qrstuvwx yz@#$%&*
& 01010101 01010101 01010101 01010101
---------------------------------------
0b0d0f0h 0j0l0n0p 0r0t0v0x 0z0#0$0*
<< b0d0f0h0 j0l0n0p0 r0t0v0x0 z0#0$0*0
0a0c0e0g 0i0k0m0o 0q0s0u0w 0y0@0$0%
| b0d0f0h0 j0l0n0p0 r0t0v0x0 z0#0$0*0
---------------------------------------
badcfehg jilknmpo rqtsvuxw zy#@%$*&
注意到這個結果是原來的 bit pattern 兩個一組反轉的結果
然後第二行 (演示略, 自己照著做)
就是原來的 bit pattern 兩bit一單位 兩單位一組反轉
所以會變成
dcbahgfe lkjiponm tsrqxwvu #@zy*&%$
這正好是一開始的 bit pattern 四個一組反轉
依此類推就行了
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ ＨＡＲＵＨＩ █████ ＜■┘ ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ ＩＳＭ By-gamejye ￠|\ ▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏ █ ⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主義 █▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92
推
03/27 17:13, , 1F
03/27 17:13, 1F
→
03/27 17:13, , 2F
03/27 17:13, 2F
→
03/27 17:14, , 3F
03/27 17:14, 3F
推
03/27 18:47, , 4F
03/27 18:47, 4F
推
03/28 00:44, , 5F
03/28 00:44, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：