close

在開始之前，我們來複習一些很重要的知識，

先不管你有沒有計算機概論的基礎，麻煩，就先看這邊一下，謝謝。

 

電腦的最小單位為 Bit (位元)，以下是所有數量單位的說明與其英文全名：

  • 1 Byte = 8 Bits
  • 1 Kilobyte (KB) = 1024 Bytes
  • 1 Megabyte (MB) = 1024 KB
  • 1 Gigabyte (GB) = 1024 MB
  • 1 Terabyte (TB) = 1024 GB
  • 1 Petabyte (PB) = 1024 TB
  • 1 Exabyte (EB) = 1024 PB
  • 1 Zettabyte (ZB) = 1024 EB
  • 1 Yottabyte (YB) = 1024 ZB

 

位元 ( bit , b )

我們從bit開始講，bit ( 指二進位中的一位 ) ，也是電腦裡面最小的單位。

 

位元組 ( byte , B )

將八個bit組合成一個位元組(byte), 通常英語系或歐語系的字母或0~9的數字都是用一個位元組來表示，而這個我們稱為字元(character)。

 

字組( word )

中文使用兩個字元組( 16位元 )才能表示。

 

 

整理 :

bit 可以代表 0 或 1

1 byte = 8 bits

1 word = 2 bytes = 16 bits

 

 

 

 

基礎 - 位元運算

 image

 

 #include <iostream>  
 using namespace std;  
 int main()  
 {  
      puts("AND運算：");  
      printf("0 AND 0\t\t%d\n", 0 & 0);  
      printf("0 AND 1\t\t%d\n", 0 & 1);  
      printf("1 AND 0\t\t%d\n", 1 & 0);  
      printf("1 AND 1\t\t%d\n\n", 1 & 1);  
      puts("OR運算：");  
      printf("0 OR 0\t\t%d\n", 0 | 0);  
      printf("0 OR 1\t\t%d\n", 0 | 1);  
      printf("1 OR 0\t\t%d\n", 1 | 0);  
      printf("1 OR 1\t\t%d\n\n", 1 | 1);  
      puts("XOR運算：");  
      printf("0 XOR 0\t\t%d\n", 0 ^ 0);  
      printf("0 XOR 1\t\t%d\n", 0 ^ 1);  
      printf("1 XOR 0\t\t%d\n", 1 ^ 0);  
      printf("1 XOR 1\t\t%d\n\n", 1 ^ 1);  
      puts("NOT運算：");  
      printf("NOT 0\t\t%d\n", !0);  
      printf("NOT 1\t\t%d\n\n", !1);  
 }

 

 

 

 

為什麼要使用邏輯運算呢? 因為，我們在程式撰寫的時候，其實可以透過邏輯運算，來增加不少程式的效率，這也是我們下面要繼續深入的東西( 反轉吧 UINT32 的做法 )，這裡提供一個簡單的程式 [ 判斷奇偶數 ]

 

 

 



int main()
{
	int n = 0; 
	while (1)
	{
		cin >> n;
		n & 1 ? cout << "奇數" : cout << "偶數";
		cout << endl;
	}
}

image

 

解釋 : 

9 =

0x00001001 & 1 =

0x00001001 & 0x00000001  = 0x00000001 =1

 

2 =

0x00000010 & 1 =

0x00000010 & 0x00000001 = 0x00000000 = 0

 

 

 

 

 

擁有這些基本知識之後，接下來我們就來解題吧，先看看以下的例子 :
 

  #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

 

 

 

arrow
arrow
    文章標籤
    計算記概論 邏輯運算 bit byte word bytes C++ 面試考題 Bitwise operator 位元運算子
    全站熱搜
    創作者介紹
    創作者 Eric 的頭像
    Eric

    一個小小工程師的心情抒發天地

    Eric 發表在 痞客邦 留言(1) 人氣()

    E-mail轉寄