Try   HackMD

課前測驗參考解答: Q1

( contributed by coldnew, riversnow, 黃鈺盛 )

  • 考慮以下 C99 程式，解釋其具體作用，並用 for/while 迴圈改寫，隨後提供 uint16_t 的版本。在什麼場合會用到下方的程式碼？
    #include <stdint.h>
    uint32_t func(uint32_t x) {
        uint32_t n = x;
        n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);
        n = ((n & 0xff00ff00) >>  8) | ((n & 0x00ff00ff) <<  8);
        n = ((n & 0xf0f0f0f0) >>  4) | ((n & 0x0f0f0f0f) <<  4);
        n = ((n & 0xcccccccc) >>  2) | ((n & 0x33333333) <<  2);
        n = ((n & 0xaaaaaaaa) >>  1) | ((n & 0x55555555) <<  1);
        return n;
    }

想法 & 思考

一開始看到這樣的題目可能不知道怎樣解，所以我們可以套用個數值 0x12345678 進去一行一行的測試:

    uint32_t n = 0x12345678;
    n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);
    printf("0x%x\n", n); // =>     0x56781234

可以發現到第一行是前後 2byte 進行對換的動作，即 0xAABBCCDD => 0xCCDDAABB 。

接下來讓我們看第二組:

    uint32_t n = 0x56781234;
    n = ((n & 0xff00ff00) >>  8) | ((n & 0x00ff00ff) <<  8);
    printf("0x%x\n", n); // =>  0x78563412

可以注意到這一組命令，會做出 0xAABBCCDD => 0xBBAADDCC 這樣的運作，也就是對兩個兩個 byte 進行 swap。

接下來看第三組，這一組則是將 4 位元 (半個 byte, 英文為 nibble ) 進行了 swap。

    uint32_t n = 0x78563412;
    n = ((n & 0xf0f0f0f0) >>  4) | ((n & 0x0f0f0f0f) <<  4);
    printf("0x%x\n", n); // => 0x87654321

到此，我們已經將原本的 0x12345678 轉換成 0x87654321 了。

接下來這一組直接看看不懂

    uint32_t n = 0x87654321;
    n = ((n & 0xcccccccc) >>  2) | ((n & 0x33333333) <<  2);
    printf("0x%x\n", n); // => 0x2d951c84

因為看不懂，所以我們用二進制來觀察

          從: 0x87654321 => 1000 0111 0110 0101 0100 0011 0010 0001
          到: 0x2d951c84 => 0010 1101 1001 0101 0001 1100 1000 0100

可以看到是對續的兩個 bit 進行對調，用這樣的圖來看就好懂了:

終於到了最後一組，來跑看看

    uint32_t n = 0x2d951c84;
    n = ((n & 0xaaaaaaaa) >>  1) | ((n & 0x55555555) <<  1);
    printf("0x%x\n", n); // => 0x1e6a2c48

因為看不懂，所以我們一樣用二進位來觀察

          ？: 0xaaaaaaaa => 1010 1010 1010 1010 1010 1010 1010 1010
          ？: 0x55555555 => 0101 0101 0101 0101 0101 0101 0101 0101
    
          從: 0x2d951c84 => 0010 1101 1001 0101 0001 1100 1000 0100
          到: 0x1e6a2c48 => 0001 1110 0110 1010 0010 1100 0100 1000
    
          原: 0x12345678 => 0001 0010 0011 0100 0101 0110 0111 1000

在這邊，我們可以透過 0xaaaaaaaa 和 0x55555555 發現到這邊的運算是對奇數/偶數的位元進行 swap 的動作。

此外，如果仔細看可以看出，原本的 0x12345678 經過這一系列的運作，變成了 0x1e6a2c48 ，而從 2 進制來看， 0x12345678 將所有的 bit 進行反轉，就會得到 0x1e6a2c48 。

於是我們知道了這個函式用途是作位元的反轉，此函式在將變數做 LSB->MSB 和 LSB->MSB 之間的轉換，也就是revserse bit。
我們可以整理前面的分析並將註解加回原始題目去:

    #include <stdint.h>
    uint32_t reverse_bits_32 (uint32_t n) {
    	/* swap 2-byte long pairs  0xAABBCCDD => 0xCCDDAABB */
    	n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);
    	/* swap bytes              0xAABBCCDD => 0xBBAADDCC */
    	n = ((n & 0xff00ff00) >>  8) | ((n & 0x00ff00ff) <<  8);
    	/* swap nibbles            0x12345678 => 0x21436587*/
    	n = ((n & 0xf0f0f0f0) >>  4) | ((n & 0x0f0f0f0f) <<  4);
    	/* swap consecutive pairs */
    	n = ((n & 0xcccccccc) >>  2) | ((n & 0x33333333) <<  2);
    	/* swap odd/even bits */
    	n = ((n & 0xaaaaaaaa) >>  1) | ((n & 0x55555555) <<  1);
    	return n;
    }

for/while 迴圈版本

先建立函式原型

    uint32_t reverse_bits_32(uint32_t x)
    {
    	/* FIXME: return the reverse_bits result */
    }

接下來需要一個暫存用的變數，我命名為 reverse_x (輸入到這函式的變數為 x)

    uint32_t reverse_x = 0;

那要怎樣處理我們的迴圈呢? 我們知道要進行反轉的目標字元數是 32 , 因此這個迴圈要跑 32 次, 所以作個簡單的雛形如下:

    for (int i = 0; i < 32; i++) {
    	/* FIXME: How to do ? */
    }

在這個迴圈裡面，我們檢查每一次要被處理的位元，假設他是 1 的話，再去更新 reverse_x 的內容。(reverse_x 預設是 0)

更新的方法很簡單，透過 or 運算子 | 來進行處理，由於我們要做的是字元反轉，因此假如我們 bit[3] 是 1 的話，則

          從: 0000 0000 0000 0000 0000 0000 0000 1000  <- bit[3]  = 1
          到: 0001 0000 0000 0000 0000 0000 0000 0000  <- bit[28] = 1, bit[32 - 1 - 3]
    
          從: 0000 0000 0000 0000 0000 1000 0000 0000  <- bit[11]  = 1
          到: 0000 0000 0001 0000 0000 0000 0000 0000  <- bit[20] = 1, bit[32 - 1 - 11]

所以可以知道，當要被處理的位元為 1 的時候，我們要這樣處理:

    for (int i = 0; i < 32; i++) {
    	if((x & (1 << i)))
    		reverse_x |= 1 << ((32 - 1) - i);
    }

因此最後的程式如下:

    #include <stdint.h>
    
    uint32_t reverse_bits_32(uint32_t x)
    {
    	uint32_t reverse_x = 0;
    	for (int i = 0; i < 32; i++) {
    		if((x & (1 << i)))
    			reverse_x |= 1 << ((32 - 1) - i);
    	}
    	return reverse_x;
    }
    
    int main(int argc, char *argv[])
    {
    	uint32_t reverse1 = reverse_bits_32( 0x12345678 );
    	uint32_t reverse2 = reverse_bits_32( reverse1   );
    
    	printf("0x12345678 -> 0x%x -> 0x%x\n", reverse1, reverse2);
    	return 0;
    }

而這程式其實可以再簡化，省掉 if 的判斷:

    #include <stdint.h>
    
    uint32_t reverse_bits_32(uint32_t x)
    {
    	uint32_t reverse_x = 0;
    	for (int i = 0; i < 32; i++){
    		reverse_x |= ( x >> ( ( 32 - 1 ) - i ) & 1 ) << i;
    	}
    	return reverse_x;
    }

uint16_t 版本: 目標為 32-bit 系統或是以上

假如目標平台本身就是 32-bit 系統或是更高位元 (64-bit, 128-bit … etc)，則我們可以直接使用題目的版本作點 shift 就可以得到 uint16_t 的版本:

    #include <stdint.h>
    
    uint32_t reverse_bits_32(uint32_t n) {
    	n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);
    	n = ((n & 0xff00ff00) >>  8) | ((n & 0x00ff00ff) <<  8);
    	n = ((n & 0xf0f0f0f0) >>  4) | ((n & 0x0f0f0f0f) <<  4);
    	n = ((n & 0xcccccccc) >>  2) | ((n & 0x33333333) <<  2);
    	n = ((n & 0xaaaaaaaa) >>  1) | ((n & 0x55555555) <<  1);
    	return n;
    }
    
    uint16_t reverse_bits_16(uint16_t x) {
    	return (uint16_t) (reverse_bits_32(x) >> 16);
    }

這樣子的程式，一樣是可以順利運作的:

          從:  0x1234 => 0001 0010 0011 0100
          到:  0x3c48 => 0010 1100 0100 1000

uint16_t 版本: 目標為 16-bit 系統

假設今天的目標為 16-bit 系統，我們就不能用 uint32_t 的版本，因為系統最大的位元數是 16-bit ，如果要用軟體先做到模擬 32-bit 系統，在將其轉換回來這中間的損耗是划不來的。

因此我們要考慮自己改寫 uint32_t 的版本成 uint16_t, 其結果如下: (其實大部分都可以直接套用 32-bit 版本的演算法)

    #include <stdint.h>
    uint16_t reverse_bits_16(uint16_t n) {
    	/* swap bytes */
    	n = ((n & 0xff00) >> 8) | ((n & 0x00ff) << 8);
    	/* swap nibbles */
    	n = ((n & 0xf0f0) >> 4) | ((n & 0x0f0f) << 4);
    	/* swap bit pairs */
    	n = ((n & 0xcccc) >> 2) | ((n & 0x3333) << 2);
    	/* swap odd/even bits */
    	n = ((n & 0xaaaa) >> 1) | ((n & 0x5555) << 1);
    	return n;
    }
    
    int main(int argc, char *argv[])
    {
    	uint16_t reverse1 = reverse_bits_16( 0x1234   );
    	uint16_t reverse2 = reverse_bits_16( reverse1 );
    
    	printf("0x1234 -> 0x%x -> 0x%x\n", reverse1, reverse2);
    	return 0;
    }
    // => 0x1234 -> 0x2c48 -> 0x1234

uint16_t 版本: 目標為 16-bit 系統 (迴圈)

承上，目標一樣是 16-bit 的系統，這時候我們的迴圈版本就變成這樣了 (其實和 for/while 迴圈版本 差不多):

    #include <stdint.h>
    
    uint16_t reverse_bits_16(uint16_t x)
    {
    	uint16_t reverse_x = 0;
    	for (int i = 0; i < 16; i++) {
    		reverse_x |= ( x >> ( ( 16 - 1 ) - i) & 1 ) << i;
    	}
    	return reverse_x;
    }
    
    int main(int argc, char *argv[])
    {
    	uint16_t reverse1 = reverse_bits_16( 0x1234 );
    	uint16_t reverse2 = reverse_bits_16( reverse1 );
    
    	printf("0x1234 -> 0x%x -> 0x%x\n", reverse1, reverse2);
    	return 0;
    }

    // => 0x1234 -> 0x2c48 -> 0x1234

原本的數字為(0xC6A5)_16 = (50863)_10 = (1100 0110 1010 0101)_2
顛倒後的數字(0xA563)_16 = (42339)_10 = (1010 0101 0110 0011)_2
程式碼視覺化 這網頁要讓他跑一下

shift if (orig & (0x01 << shift)) result
0 1 (32768)_10 = (1000 0000 0000 0000)_2
1 0 (32768)_10 = (1000 0000 0000 0000)_2
2 1 (40960)_10 = (1010 0000 0000 0000)_2
3 0 (40960)_10 = (1010 0000 0000 0000)_2
… … …
14 1 (42338)_10 = (1010 0101 0110 0010)_2
15 1 (42339)_10 = (1010 0101 0110 0011)_2

硬體指令支援

ARMCortex-M3也有提供RBIT的指令，用來支援FFT運算效能。

應用場景 LSB <-> MSB轉換

位元反轉與Big/Little Endian的問題類似，常聽到的是指 byte 儲存在記憶體位址的順序，其實Bit也是依照相同順序儲存，在Intel x86架構下，Bit和Byte順序是Little Endian，由LSB (Least Significant Bit First)優先；Sun Sparc則是Big Endian，由MSB (Most Significant Bit First )優先，ARM則是兩種都支援。

Bit Reverse相關問題也出現在Data Transmission Order時，舉例來說，Ethernet Transimission在Byte順序是 Big Endian(leftmost byte is sent first)，在Bit順序是 little-endian ( LSB Least Significant Bit)，舉MAC為例說明

傳送4bytes的MAC位址，是由LSB開始傳送：

11100001 00001111 10101010 10010011
Byte1 Byte2 Byte3 Byte4

因此接收MAC位址時，每個Byte會是反轉的：

10000111 11110000 01010101 11001001
Byte1 Byte2 Byte3 Byte4

在開發網路、匯流排、序列埠…應用等，都會遇到類似的問題。

最原始的通訊介面 — RS232與UART的差別

例如CS4215 Audio Codec晶片，當驅動程式透過Short Pipe傳送資料時，Short Pipe是以LSB優先，然而CS4215在接受資料時是用MSB，因此在傳送音樂訊號前，需要先將程式反轉。

// sound/sparc/dbri.c

static __u32 reverse_bytes(__u32 b, int len)
{
	switch (len) {
	case 32:
		b = ((b & 0xffff0000) >> 16) | ((b & 0x0000ffff) << 16);
	case 16:
		b = ((b & 0xff00ff00) >> 8) | ((b & 0x00ff00ff) << 8);
	case 8:
		b = ((b & 0xf0f0f0f0) >> 4) | ((b & 0x0f0f0f0f) << 4);
	case 4:
		b = ((b & 0xcccccccc) >> 2) | ((b & 0x33333333) << 2);
	case 2:
		b = ((b & 0xaaaaaaaa) >> 1) | ((b & 0x55555555) << 1);
	case 1:
	case 0:
		break;
	}
	return b;
}

/* DBRI short pipes always transmit LSB first */
if (dbri->pipes[pipe].sdp & D_SDP_MSB)
    data = reverse_bytes(data, dbri->pipes[pipe].length);

使用到的場合: 快速傅利葉轉換

背景知識: Wave

  • 運用正向傅立葉轉換分解一個波，運用逆向傅立葉轉換合成一個波，運用頻譜解讀波的詳細內容。傅立葉轉換是一對一函數，一種波對應一種頻譜。頻譜的左側到右側，是低頻到高頻。
  • 把一個波實施正向傅立葉轉換，將低頻數值或者高頻數值改成零，再實施逆向傅立葉轉換，改造原本的波。這是十分常用的技巧。
  • 頻譜是非常實用的分析工具。凡是學習科學的人，都有必要了解頻譜！各種物質的振動或振盪，皆可求得頻譜，發掘其特性。例如震譜是震波的頻譜，光譜是光波的頻譜，聲譜是聲波的頻譜。世間萬物皆有譜，應用無限廣泛。

在進行快速傅利葉轉換(Fast Fourier Transform, FFT)之前，我們會需要進行位元反轉 (bit reverse)，從 FAST BIT-REVERSAL ALGORITHM 論文一開頭的描述來看:

足以知道位元反轉 (bit reverse) 對於快速傅利葉轉換(FFT)的重要性。因為只使用到bitwise operator與data move，這個函式的時間複雜度是O(1)，換言之，程式碼執行時間是 deterministic (明確的、已確定的)。

(註: Unscrambling for fast DFT algorithms

此外，在 Bit Reversal on Uniprocessors 這篇文章也列舉了 30 種用來作位元反轉(bit reverse)的演算法，用來測試在不同硬體上面的效能比較。

使用到的場合: 加解密運算

透過本題的程式，可以將 0x12345678 轉變成 0x1e6a2c48 ，而這動作是可以反向的, 我們一樣可以將此函式套用在 0x1e6a2c48 從而得到 0x12345678 這樣的答案，也就是說將東西丟給這個函式，再把結果丟給這函式，可以得到原本的輸入:

    0x12345678 == reverse_bits( reverse_bits(0x12345678) ) /* 兩者相等 */

利用這種特性，我們可以實作簡單的加解密程式 rcf.c ，如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdint.h>
    
    uint32_t reverse_bit(uint32_t x) {
    	x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);
    	x = ((x & 0xff00ff00) >>  8) | ((x & 0x00ff00ff) <<  8);
    	x = ((x & 0xf0f0f0f0) >>  4) | ((x & 0x0f0f0f0f) <<  4);
    	x = ((x & 0xcccccccc) >>  2) | ((x & 0x33333333) <<  2);
    	x = ((x & 0xaaaaaaaa) >>  1) | ((x & 0x55555555) <<  1);
    	return x;
    }
    
    int main(int argc, char *argv[])
    {
    	if (argc < 3) {
    		printf( "\nUsage:"
    			"\t %s input.txt output.txt\n\n"
    			"This is a simple encrypt/decrypt app "
    			"based on reverse_bit algorithm.\n\n"
    			, argv[0]);
    		return 0;
    	}
    
    	const char *input_path = argv[1];
    	FILE *fin = fopen(input_path, "rb");
    	if (!fin) {
    		fprintf(stderr,
    			"ERROR: failed to open input file %s\n", input_path);
    		exit(-1);
    	}
    
    	const char *output_path = argv[2];
    	FILE *fout = fopen(output_path, "wb");
    	if (!fout) {
    		fclose(fin);
    		fprintf(stderr,
    			"ERROR: failed to open output file %s\n", output_path);
    		exit(-1);
    	}
    
    	uint32_t ch;
    	int nread;
    	while((nread = fread(&ch, 1, sizeof(uint32_t), fin)) > 0) {
    		/* if read size less than sizeof(uint32_t), just write it */
    		if (nread < sizeof(uint32_t)) {
    			fwrite(&ch, 1, nread, fout);
    		}
    		else {
    			uint32_t chn = reverse_bit(ch);
    			fwrite(&chn, 1, nread, fout);
    		}
    	}
    
    	fclose(fin);
    	fclose(fout);
    	return 0;
    }

這個程式可以使用以下命令進行編譯:

    gcc rcf.c -o rcf

那要如何使用呢? 我們可以建立一個名為 hello.txt 的文字檔，有以下內容:

    hello, this is a test

接下來使用這隻加密程式產生新的檔案叫做 hello_enc.txt

    ./rcf hello.txt hello_enc.txt

打開可以看到內容如下: (是不是成功加密了!)

    66¦^V.^D4ö^DÎ<96>^V<86>^DÎ<96>Φ.^Dt

而這個檔案我們一樣可以透過這隻程式進行解密成 hello_dec.txt

    ./rcf hello_enc.txt hello_dec.txt

打開 hello_dec.txt 看看，內容是不是和原來的一樣 ?

    hello, this is a test

使用到的場合: CRC-32 運算

從 使用到的場合: 加解密運算 這邊可以知道僅僅只是反轉一下位元就可以製作加解密程式，循環冗餘校驗 (CRC) 的實作也可以用到 位元反轉 (bit reverse) 的部分。

具體實作可以參考:

使用到的場合: Linux Kernel

Linux kernel 裡面有實作 bitrev32 等位元反轉的命令，可以在 bitrev.h 看到，最常用到的用途，則是在 ether_crc() 這個函式上:

    /*
     * Helpers for hash table generation of ethernet nics:
     *
     * Ethernet sends the least significant bit of a byte first, thus crc32_le
     * is used. The output of crc32_le is bit reversed [most significant bit
     * is in bit nr 0], thus it must be reversed before use. Except for
     * nics that bit swap the result internally...
     */
    #define ether_crc(length, data)    bitrev32(crc32_le(~0, data, length))
    #define ether_crc_le(length, data) crc32_le(~0, data, length)

使用到的場合: redis

補充: Clang 與 GCC 支援

Clang 是有內建 字元反轉 的函式的，然而根據 BUG 50481 來看 GCC 是尚未支援內建這功能。

以下為 Clang 內建的版本說明如下:

補充: C 語言實作 2 進制的 print 函式

以下提供以將 uint32_t 型別的輸入，以二進制的形式顯示出來的工具函式:

#include <stdint.h>
    
void print_binary(uint32_t x)
{
    unsigned char *p = (unsigned char *) &x;
    unsigned char byte;
    
    for (int i = sizeof(uint32_t) -1; i >= 0; i--) {
        for (int j = 7; j >= 0; j--) {
            byte = (p[i] >> j) & 1;
            printf("%u", byte);
            if (0 == (j % 4))
                printf(" ");
        }
    }
    printf("\n");
}
    
int main(int argc, char *argv[])
{
    print_binary(0x12345678);
    return 0;
}

// => 0001 0010 0011 0100 0101 0110 0111 1000

延伸閱讀

Last changed by 
 
sysprog
System Software Programming
8
24124

Read more

留意浮點數運算的陷阱

科學、工程與統計等領域往往離不開浮點數的運用，因此，如何趨吉避凶，正是每位經常處理浮點數的程式開發者應具備的基本素養。儘管妥善運用浮點數是門深奧的學問，學校課程中對此著墨不多，頂多在數值方法這門課中略有涉及，其涵蓋的廣度與深度皆有限。本文探討操作浮點數的基本觀念，不涉及理論分析，並使用直覺的詞彙，刻意避開過於嚴謹或艱澀的定義，以降低理解門檻，閱讀本文所需的預備知識僅限於基礎的程式設計概念，例如單精度與倍精度浮點數的表示方式，預期多數讀者皆可順利閱讀。

Mar 29, 2025
位元旋轉實作和 Linux 核心案例

針對 2021 年暑期「Linux 核心」課程先決測驗題的測驗 $\alpha$ 共筆貢獻者: jserv, ekangmonyet, ChinYikMing, henrybear327, dmefs, JingWangTW, mickey30606, tanchihpin0517, ccs100203, RinHizakura, st9540808, yian02, 2011eric, alan23273850 位元旋轉 位元旋轉 (bitwise rotation 或 bit rotation) 的操作展示如下圖: 位元旋轉也稱為循環移位運算 (circular shift operation)，其作用是移動位元，但不捨棄位元或增加位元。分二種操作: 循環右移運算 (向右旋轉): 向右移動每個位元一個位置，最右邊的位元被循環成為最左邊的位元

Mar 29, 2025
圖解傅立葉分析

傅立葉 (Fourier) 分析不僅是個數學工具，更是種徹底顛覆一個人以前世界觀的思維模式。但不幸的是，傅立葉分析的公式看起來太複雜，很多人囫圇吞棗，並對它深惡痛絕。這麼有意思的東西居然成了大學裡的殺手課程，因此，筆者希望撰寫科普文章來解釋傅立葉分析，甚至讓高中生也能看懂，體會到藉由傅立葉分析看到世界的另一個樣貌。對於已有一定數理基礎的朋友，細讀後也會有新的發現。

Mar 29, 2025
你所不知道的 C 語言: 浮點數運算

工程領域往往是一系列的取捨結果，浮點數更是如此，在軟體開發有太多失誤案例源自工程人員對浮點數運算的掌握不足，本議程希望藉由探討真實世界的血淋淋案例，帶著學員思考 IEEE 754 規格和相關軟硬體考量點，除了關注浮點數原理，我們也會用 C 程式來操作浮點數內部，並談及定點數運算。最後也會探討在深度學習領域為了改善資料處理效率，而引入的 BFloat16 這樣的新標準。

Mar 29, 2025
Read more from sysprog
Published on HackMD