Bit Manipulation

位操作有按位與(bitwise and)、或(bitwise or)、非(bitwise not)、左移n位和右移n位等操作。

XOR - 異或(exclusive or)

異或：相同為0，不同為1。也可用「不進位加法」來理解。

異或操作的一些特點：

  1. x ^ 0 = x
  2. x ^ 1s = ~x // 1s = ~0
  3. x ^ (~x) = 1s
  4. x ^ x = 0 // interesting and important!
  5. a ^ b = c => a ^ c = b, b ^ c = a // swap
  6. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c // associative

移位操作(shift operation)

移位操作可近似為乘以/除以2的冪。0b0010 * 0b0110等價於0b0110 << 2. 下面是一些常見的移位組合操作。

  1. 將x最右邊的n位清零 - x & (~0 << n)
  2. 獲取x的第n位值(0或者1) - x & (1 << n)
  3. 獲取x的第n位的冪值 - (x >> n) & 1
  4. 僅將第n位置為1 - x | (1 << n)
  5. 僅將第n位置為0 - x & (~(1 << n))
  6. 將x最高位至第n位(含)清零 - x & ((1 << n) - 1)
  7. 將第n位至第0位(含)清零 - x & (~((1 << (n + 1)) - 1))
  8. 僅更新第n位，寫入值為v; v為1則更新為1，否則為0 - mask = ~(1 << n); x = (x & mask) | (v << i)

實際應用

位圖(Bitmap)

位圖一般用於替代flag array，節約空間。

一個int型的陣列用位圖替換後，占用的空間可以縮小到原來的1/32.(若int類型是32位元)

下面代碼定義了一個100萬大小的類圖，setbit和testbit函數

  1. #define N 1000000 // 1 million
  2. #define WORD_LENGTH sizeof(int) * 8 //sizeof返回字節數，乘以8，為int類型總位數
  4. //bits為陣列，i控制具體哪位，即i為0~1000000
  5. void setbit(unsigned int* bits, unsigned int i){
  6.     bits[i / WORD_LENGTH] |= 1<<(i % WORD_LENGTH);  
  7. }
  9. int testbit(unsigned int* bits, unsigned int i){
  10.     return bits[i/WORD_LENGTH] & (1<<(i % WORD_LENGTH));
  11. }
  13. unsigned int bits[N/WORD_LENGTH + 1];

Reference