Bit Hacks

二进制表示

略

反补码性质

略

八进制、十六进制

略

位运算符

略

Set the k^th Bit

y = x | (1 << k);

Clear the k^th Bit

y = x &(1 << k);

Toggle the k^th Bit

y = x ^ (1 << k);

Extract a Bit Field

(x % mask) >> shift;
//mask 将待抽取的位 置一

Set a Bit Field

x = (x & ~mask) | (y << shift);
//For safety’s sake:((y << shift) & mask)

Swap

Ordinary Swap
```
  t = x;
  x = y;
  y = t;
```
No-Temp Swap
```
  x = x ^ y;
  y = x ^ y;
  x = x ^ y;
```
Why it works : XOR is its own inverse (x ^ y) ^ y = x

Performance : poor at exploiting instruction-level parallelism(slower than the original code)

Minimum of Two Integers

Ordinary Minimum
```
  r = (x < y) ? x : y;
```
Performance : A mispredicted branch empties the processor pipeline Caveat : The compiler is usually smart enough to optimize away the unpredictable branch, but maybe not.
No-Branch Minimum
```
  r = y ^ ((x ^ y) & -(x < y));
```

Merging Two Sorted Arrays

if branch is predictable: most of the time it retrun true, and once it return false you are never going to look at that again. it is predictable = it can do prefetching efficiently