C++帮我们实现好了很多有用的函数，我们要避免重复造轮子。

1. 位运算 & | ~ ^ << >>

   与(AND)、或(OR)、非(NOT)、异或(XOR)、左移(* 2^k)、右移(/ 2^k)

   常用操作：

   1.1 求 x 的第 k 位数字 x >> k & 1

   #include <bits/stdc++.h>
   using namespace std;
   
   int main()
   {
       int a = 13;
   
       for (int i = 5; i >= 0; i -- ) cout << (a >> i & 1) << endl;	
   
       return 0;
   }
   

   1.2 lowbit(x) = x & -x ，返回 x 的最后一位 1

   #include <bits/stdc++.h>
   using namespace std;
   
   int main()
   {
       int a = 121212;
       int b = -a;
       int c = ~a + 1;
   
       cout << b << endl << c << endl;
   
       return 0;
   }
   

2. 常用库函数 #include <algorithm>

   2.1 reverse 翻转 O(n)

   翻转一个 vector ：

   reverse(a.begin(), a.end());

   翻转一个数组，元素存放在下标 1 ~ n ：

   reverse(a + 1, a + n + 1);

   #include <bits/stdc++.h>
   using namespace std;
   
   int main()
   {
       vector<int> a({1, 2, 3, 4, 5});
       reverse(a.begin(), a.end());
   
       int a[] = {1, 2, 3, 4, 5};
       reverse(a, a + 5);
   
       for (int x : a) cout << x << ' ';
       cout << endl;	
   
       return 0;
   }
   

   2.2 unique 去重

   前提有序，返回去重（只去掉相邻的相同元素）之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。

   把一个 vector 去重：

   int m = unique(a.begin(), a.end()) – a.begin();

   把一个数组去重，元素存放在下标 1 ~ n ：

   int m = unique(a + 1, a + n + 1) – (a + 1);

   #include <bits/stdc++.h>
   using namespace std;
   
   int main()
   {
       int a[] = {1, 1, 2, 2, 3, 3, 4};
       int m = unique(a, a + 7) - a;
   
       cout << m << endl;
       for (int i = 0; i < m; i ++ ) cout << a[i] << ' ';
       cout << endl;
   
       vector<int> a({1, 1, 2, 2, 3, 3, 4});
       a.erase(unique(a.begin(), a.end()), a.end());
   
       for (auto x : a) cout << x << ' ';
       cout << endl;
   
       return 0;
   }
   

   2.3 random_shuffle 随机打乱

   用法与 reverse 相同。

   #include <bits/stdc++.h>
   #include <ctime>
   using namespace std;
   
   int main()
   {
       vector<int> a({1, 2, 3, 4, 5});
   
       srand(time(0)); // 返回当前至1970.1.1的s 
   
       random_shuffle(a.begin(), a.end());
   
       for (int x : a) cout << x << ' ';
       cout << endl;
   
       return 0;
   }
   

   2.4 sort

   对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数，或者重载“小于号”运算符。

   把一个 int 数组（元素存放在下标 1 ~ n ）从大到小排序，传入比较函数：

   int a[MAX_SIZE];
   bool cmp(int a, int b)
   {
       return a > b;
   }
   sort(a + 1, a + n + 1, cmp);
   

   #include <bits/stdc++.h>
   #include <ctime>
   using namespace std;
   
   bool cmp(int a, int b) // a 是否应该排在 b 的前面
   {
       return a < b;
   } 
   
   int main()
   {
       vector<int> a({1, 2, 3, 4, 5});
   
       srand(time(0)); // 返回当前至1970.1.1的s 
   
       random_shuffle(a.begin(), a.end());
   
       for (int x : a) cout << x << ' ';
       cout << endl;
   
       sort(a.begin(), a.end());
   //	sort(a.begin(), a.end(), greater<int>()); // 从大到小
   //	sort(a.begin(), a.end(), cmp); // 自定义排序函数 
   
       for (int x : a) cout << x << ' ';
       cout << endl;
   
       return 0;
   }
   

   把自定义的结构体 vector 排序，重载“小于号”运算符：

   struct Rec
   {
       int id, x, y;
   
   bool operator< (const Rec &a, const Rec &b)
   {
        return a.x < b.x || a.x == b.x && a.y < b.y;
   }
   };
   
   vector<Rec> a;
   
   sort(a.begin(), a.end());
   

   #include <bits/stdc++.h>
   using namespace std;
   
   struct Rec
   {
       int x, y;	
   }a[5];
   
   bool cmp(Rec a, Rec b) // 写一个比较函数 
   {
       return a.x < b.x;
   } 
   
   int main()
   {
       for (int i = 0; i < 5; i ++ )
       {
    	   a[i].x = i;
    	   a[i].y = -i;
       }
   
       for (int i = 0; i < 5; i ++ ) printf("(%d,%d) ", a[i].x, a[i].y);
       cout << endl;
   
       sort(a, a + 5, cmp);
   
       for (int i = 0; i < 5; i ++ ) printf("(%d,%d) ", a[i].x, a[i].y);
       cout << endl;
   
       return 0;
   }
   

   2.5 lower_bound/upper_bound 二分

   lower_bound 的第三个参数传入一个元素 x ，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于 x 的元素的位置的迭代器（指针）。

   #include <bits/stdc++.h>
   using namespace std;
   
   int main()
   {
       int a[] = {1, 2, 4, 5, 6};
   
       int *p = lower_bound(a, a + 5, 3);
   
       cout << *p << endl;
   
       return 0;
   }
   

   upper_bound 的用法和 lower_bound 大致相同，唯一的区别是查找第一个大于 x 的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。

   在有序 int 数组（元素存放在下标 1 ~ n ）中查找大于等于 x 的最小整数的下标：

   int i = lower_bound(a + 1, a + 1 + n, x) - a;

   #include <bits/stdc++.h>
   using namespace std;
   
   int main()
   {
       int a[] = {1, 2, 4, 5, 6};
       int t = upper_bound(a, a + 5, 4) - a;
   
       vector<int> a(1, 2, 3, 4, 5, 6);
       int t = upper_bound(a.begin(), a.end(), 4) - a.begin();
   
       cout << a[t] << endl;
   
       return 0;
   }
   

   在有序 vector<int> 中查找小于等于 x 的最大整数（假设一定存在）：

   int y = *--upper_bound(a.begin(), a.end(), x);