位操作

1. 改变符号：取反+1

2. 与0异或保持不变，与-1(0xffffffff)异或相当于取反。

3. 负数右移可以认为是补符号位（当然也有机器不是这样子）。负数右移31位就是-1.

 1 int sign(int n) {
 2     return ~n + 1;
 3 }
 4 
 5 int abs(int n) {
 6     int s = n >> 31; // if n >= 0, s = 0, n ^ s = n; if n < 0, s = -1, n ^ s = ~n;
 7     return (n ^ s) - s; // if n >= 0, return n - 0; if n < 0, return ~n - (-1);
 8 }
 9 
10 int swap(int &a, int &b) {
11     a ^= b;
12     b ^= a;
13     a ^= b;
14 }

求小于等于n的素数；

 1 void set(int &n, int p) {
 2     n |= 1 << p;
 3 }
 4 
 5 bool check(int n, int p) {
 6     return n & (1 << p);
 7 }
 8 
 9 void getPrimes(int n, vector<int> &ret) {
10     int* visited = new int[n >> 5 + 1];
11     memset(visited, 0, sizeof(int) * (n >> 5 + 1));
12 
13     for (int i = 2; i <= n; ++i) {
14         if (!check(visited[i >> 5], i & 0x1f)) {
15             ret.push_back(i);
16             for (int j = i * i; j <= n; j += i) { //start from i * i, check chapter 7 in careercup
17                 set(visited[j >> 5], j & 0x1f);
18             }
19         }
20     }
21 
22     delete[] visited;
23 }

反转二进制串:

1 int reverseBinary(int n) {
2     n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
3     n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
4     n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
5     n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
6     n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);
7     return n;
8 }

计数1的个数：

 1 int calculateOnes(int n) {
 2     n = ((n & 0xaaaaaaaa) >> 1) + (n & 0x55555555);
 3     n = ((n & 0xcccccccc) >> 2) + (n & 0x33333333);
 4     n = ((n & 0xf0f0f0f0) >> 4) + (n & 0x0f0f0f0f);
 5     n = ((n & 0xff00ff00) >> 8) + (n & 0x00ff00ff);
 6     n = ((n & 0xffff0000) >> 16) + (n & 0x0000ffff);
 7     return n;
 8 }
 9 
10 int calculateOnes2(int n) {
11     int c = 0;
12     for (; n; c++) n &= n - 1;
13     return c;
14 }
15 
16 int calculateOnes3(int n) {
17     int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
18     return ((tmp + (tmp >> 3)) & 030707070707) % 63;
19 }

这个问题还有其他解法：http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html

最后一个方法，mod 63是利用到了这个性质：

(a + b) % p = (a % p + b % p) % p