網路城邦
上一篇 回創作列表 下一篇  字體:
So you are a computer dude, can you better this? No assembly, please.
2008/10/04 07:58:26瀏覽2023|回應4|推薦4

#include

#include

#define MAX 12

#define TBLSZE 0x100

#define uchar unsigned char

#define ulong unsigned long

static uchar rev_tbl[TBLSZE];

static uchar rev(uchar u) {

uchar ur = 0, u2 = u, bit;

for (bit = 0; bit < 8; (u2 & 1)?

      (ur |= 1 << (7 - bit)):0,

      bit++, u2 >>= 1);

return (ur);

}

int main(void) {

uchar in[MAX], i;

ulong num, u, mun;

// Construct the static table

if (rev_tbl[0] == '\0') {

      for (u = 0; u < TBLSZE;

            rev_tbl[u] = rev((uchar)u), u++);

}

// Prompt for user entry

printf("Enter a number in hexadecimal(0x~ or 0X~), "

      "octal(0~), or decimal: ");

// Process user input

if (fgets(in, MAX, stdin)) {

      num = strtoul(in, NULL, 0);

      // This one statement completes the reversal

      for (i = 0, mun = 0, u = num; i < 4;

            (mun |= rev_tbl[(uchar)(u & 0xff)] <<

            ((3 - i) * 8)), i++, u >>= 8);

      // Display the header banner

      printf("                   hex        dec        oct          bin\n");

      // Show the original number

      printf("reversal of number 0x%08x %-10u 0%-011o ",

            num, num, num);

      for (i = 0; i < 32; (num & (1 << (31 - i)))?

            printf("1"):printf("0"), i++);

      // Print the reversed number

      printf("\nis 0x%08x %-10u 0%-011o ",

            mun, mun, mun);

      for (i = 0; i < 32;

            (mun & (1 << (31 - i)))?

            printf("1"):printf("0"), i++);

      }

}

( 知識學習科學百科 )
回應 推薦文章 列印 加入我的文摘
上一篇 回創作列表 下一篇

引用
引用網址:https://classic-blog.udn.com/article/trackback.jsp?uid=GolfNut&aid=2270358

 回應文章


等級:
留言加入好友
2010/10/26 09:10

查表的方式一般而言應該是最快的了. (假設是要快而不是要省 memory?)
http://efreedom.com/Question/1-746171/Best-Algorithm-Bit-Reversal-MSB-LSB-LSB-MSB-C 這邊有一些簡單的討論
其它的就是從 architecture 下手了, 比如說 L1 cache 夠大, 那就可以試看看用 64K-entry 的 table (link 裡頭有提到的, 假如 cache size 不夠大會增加 cache miss rate, 可能會變更慢)
或是利用現代 CPU 的 SIMD instruction (不過這就沒辦法用純 C 來寫, 不然就要看看有沒什麼 compiler 有這種 optimization), 讓查表的動作可以同時進行.

此外就是單純轉換一個 32 bits, 再慢大概也無所謂, 只有要 reverse 一堆的時候會比較有所謂. 而現在的 PC 幾乎都是 SMP, 各別 data 的轉換也跟彼此無關, 所以就可以把資料拆成幾份, 每個 core 分一部份來做.

Cache 的部份, 又可以再延伸討論一下. 理想狀態, 最好是能夠永遠都不會 cache miss, 這樣就可以不用浪費時間在 access low level memory 上, 可是往往都是要第一次去讀資料時, 才會把資料 load 到 cache, 或以假如是要轉換一堆資料, 其實有一直在 cache miss. 不過近代的 CPU 幾乎都有設計 Cache preload 的功能. 通常是一個特別的指另 + address, 當做是一個給 CPU 的 hint (只是一個可做可不做的請求, 不是非做不可的 command). 當 CPU 在情況許可時, 就會把該 address 的 data 給 preload 到 cache line 裡頭去, 所以晚點真的要 access data 時東西就已經在 cache 裡.

GolfNut — 無心的邂逅(GolfNut) 於 2010-10-26 14:16 回覆:
這個厲害,的是行家!我都忘了幹嘛會有這篇出現在此。
你説對了,如果表不太大,查表一定是最快的。
謝謝回應。真是不厭其煩啊。

SCFtw2
等級:8
留言加入好友
別刪別刪!
2008/10/11 15:46

"沒什麼營養的話過兩天我就刪掉。"

So far so 有營養!

GolfNut — 無心的邂逅(GolfNut) 於 2008-10-11 16:03 回覆:

你們這些傢伙真討厭,我要刪掉了。

不過下一個更大更長,等我測試完很快就會出來。

等我把版面改寬之後就知道最長一行可以容納多少。

最近沒什麼靈感,寫寫 C 營養價值會更高。



等級:
留言加入好友
這就是為什麼應該淘汰 C
2008/10/07 04:57
寫得人家看不懂不是值得誇耀的事。 

普希金 酷不停囉
等級:7
留言加入好友
what is this ?
2008/10/06 02:21
It looks like my long lost C...
I am a Java and C# dude now... :-)
By saying knowing C, it actually like a stigma in this Web 3.x world, sigh !

GolfNut — 無心的邂逅(GolfNut) 於 2008-10-07 08:40 回覆:

對不起,不慎觸動大家最敏感的一條神經 :-)

沒那麼嚴重啦。我的原始碼有說明,有範例,有解釋,還有一行一行分得好好的、規規矩矩的 coding style。只是在 copy-and-paste 之後,不料因為部落格的 window 太窄,所有較長的行都給折轉回來不成個樣子,沒法看,所以才把太長的說明、範例、解釋去掉,還把 printf() 放進 for() 裡。沒想到讓麵怪認為我在誇耀什麼。我要誇耀的話,至少一萬行。

這是我認為最好的,reverse a 32-bit word 的方法,想看看有沒有人有更好的 ideaCopy and paste 一下,編一編(cc foo.c -o foo),一跑就知道了。

沒什麼營養的話過兩天我就刪掉。