作者liwmewmew (如果大海能夠)
看板C_and_CPP
標題[問題] 請教一段奇怪的位反轉函式
時間Mon Feb 26 15:41:37 2018
開發平台(Platform): (Ex: Win10, Linux, ...)
Linux
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
GCC
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
無
問題(Question)：
我看到了一個奇怪的位反轉程式
看他用for loop跑得很忙
但看一看感覺他實際效果只是將代入的x值往右shift一次
然後將第31位元開始的左邊都濾掉，最後將結果餵給y去return
為何他不乾脆簡單的寫return (x >> 1) & 4294967295就好了呢? 卻要寫得這麼複雜?
(而且，這樣的動作也不是位反轉吧?...這函式如此命名，但一點注解都沒有...)
請問我是不是誤會了什麼? 或是沒注意到這function的真正意義?
真的非常謝謝各位
程式碼(Code)：(請善用置底文網頁, 記得排版)
好讀版:
http://codepad.org/pzWWrf55
純文字版:
unsigned long bitreverse(unsigned long x)
{
int i;
unsigned long y = 0;
for (i = 0; i < 32; i++) {
y <<= 1;
y |= (x >> (32 - i)) & 1;
}
return y;
}
補充說明(Supplement)：
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.130.45.196
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1519630902.A.AA8.html
1F：→ asilzheng: 你人腦在跑程式時是不是忘了做for-loop？ 02/26 16:02
大大我有個疑問
既然這function並不需要可變的loop之類(過程很固定)，寫成for loop也沒有更容易讀
為何不寫成
#define SET_BIT_32_TO_63_BE_ZERO 4294967295
return x >> 1 & SET_BIT_32_TO_63_BE_ZERO
這樣是不是效率更好且易懂呀?
我也擔心我這樣理解這個function是不是錯誤的? 如果改寫會出現BUG?
2F：推 cutekid: y |= (x >> (31 - i)) & 1; 是不是要 31 - i 才對 ? 02/26 16:10
大大，我一開始也一直在思考，他應該是要反轉吧? 0001變1000這樣
如果要反轉，就不應該位移32個bit，也就是大大提到的，應該是31 - i不是32 - i
又如果他是要反轉，也不該是31或32 - i，直接使用i就達到反轉效果了
而且unsigned long在我的平台已經是64 bit了，所以他只想搞前32 bit XDD?
但我目前認了，就當做他不是要反轉了...
就當做他目前for loop的動作就是他刻意設計的，結果也是他要的
那我就在想，過程是不是也可以寫簡單一點?
這function目前寫法的真正行為，是不是就return (x >> 1) & SET_BIT_32_TO_63_BE_ZERO
※ 編輯: liwmewmew (220.130.45.196), 02/26/2018 16:56:01
3F：→ Hazukashiine: 先不管哪樣的寫法是對的 02/26 17:06
4F：→ Hazukashiine: 基本上這個 code 看到我就會先給一個大問號 02/26 17:06
5F：→ Hazukashiine: 首先 hard-code 32 在程式碼裡面 02/26 17:07
6F：→ Hazukashiine: 但是 unsigned long 並沒有保證一定是 32-bit 02/26 17:07
7F：→ Hazukashiine: 是不是應該用 uint32_t 或是用自定義 typedef? 02/26 17:08
8F：→ Hazukashiine: 另外一件事這個 function 的名稱: bitreverse 02/26 17:09
9F：→ Hazukashiine: 給我的第一印象就是：「有這麼多步驟嗎？」 02/26 17:09
10F：→ Hazukashiine: 我第一個直覺做 reverse 就是 x ^= ~(type)0; 02/26 17:10
11F：噓 sharkbay: 你是說 inverse 取反向 02/27 08:06
12F：→ sharkbay: Bit Twiddling Hacks 02/27 08:10
13F：→ sharkbay: 餵狗看看 02/27 08:10
14F：→ Hazukashiine: 喔喔喔喔 我弄錯了 感冒到腦子壞了 02/27 10:24