Powered by GitBook

algorithm-reading

Bit Manipulation

位操作有按位与、或、非、左移n位和右移n位等操作。

XOR - 异或

异或：相同为0，不同为1。也可用「不进位加法」来理解。

异或操作的一些特点：

x ^ 0 = x
x ^ 1s = ~x // 1s = ~0
x ^ (~x) = 1s
x ^ x = 0 // interesting and important!
a ^ b = c => a ^ c = b, b ^ c = a // swap
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c // associative

移位操作

移位操作可近似为乘以/除以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/321/32.
下面代码定义了一个100万大小的类图，setbit和testbit函数

#define N 1000000 // 1 million
#define WORD_LENGTH sizeof(int) * 8 //sizeof返回字节数，乘以8，为int类型总位数

//bits为数组，i控制具体哪位，即i为0~1000000
void setbit(unsigned int* bits, unsigned int i){
  bits[i / WORD_LENGTH] |= 1<<(i % WORD_LENGTH);  
}

int testbit(unsigned int* bits, unsigned int i){
  return bits[i/WORD_LENGTH] & (1<<(i % WORD_LENGTH));
}

unsigned int bits[N/WORD_LENGTH + 1];

Reference