位运算
& 与
| 或
~ 非
^ 异或
>> 右移
<< 左移
常用操作:
(1) 求x的第k位数字 x >> k & 1
(2) lowbit(x) = x & -x,返回x的最后一位1 (其中-x = ~x + 1)
int a = 2;
cout << (a & -a) << endl; // 2
int a = 12;
cout << (a & -a) << endl; // 4
更多操作: 位运算技巧
常用库函数
基本都在
#include <algorithm>
reverse
翻转
reverse(a.begin(), a.end()); // 翻转一个vector
reverse(a, a + n); // 翻转一个数组
unique
去重(需保证相同元素挨边)
返回去重之后的尾迭代器(或指针),仍然为前闭后开,即这个迭代器是去重之后末尾元素的下一个位置。
该函数常用于离散化,利用迭代器(或指针)的减法,可计算出去重后的元素个数。
int m = unique(a.begin(), a.end()) – a.begin(); // 把一个vector去重
int m = unique(a, a + n) – a; // 把一个数组去重,元素存放在下标1~n
// 顺带删除 vector 后面的数
a.erase(unique(a.begin(), a.end()), a.end());
random_shuffle
随机打乱
#include <ctime>
// 初始化随机种子
srand(time(0));
random_shuffle(a.begin(), a.end());
sort
对两个迭代器(或指针)指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数,或者重载“小于号”运算符。
// 从小到大
sort(a.begin(), a.end());
// 从大到小
sort(a.begin(), a.end(), greater<int>());
// 自定义
bool cmp(int a, int b) {
// a 是否应该在 b的前面
return a < b;
}
sort(a.begin(), a.end(), cmp);
// sort函数的cmp必须只能是>或者<。
lower_bound/upper_bound
lower_bound 的第三个参数传入一个元素x,在两个迭代器(指针)指定的部分上执行二分查找,返回指向第一个大于等于x的元素的位置的迭代器(指针)。
upper_bound 的用法和lower_bound大致相同,唯一的区别是查找第一个大于x的元素。
当然,两个迭代器(指针)指定的部分应该是提前排好序的。
int a[] = {1,2,3,4,5};
int *p = lower_bound(a, a + 5, 3);
cout << *p << endl;
vector<int> a{1,2,3,4,5};
cout << lower_bound(a.begin(), a.end(), 4) - a.begin();
关于cctype头文件里的一些函数
// 判断一个字符是否是字母 A-Z、a-z
isalpha(c);
// 类似的有
islower(c);
isupper(c);
isalnum(c); // 字母大写小写+数字
isblank(c); // space和\t
isspace(c); // space、\t、\r、\n
// 转换字符大小写
tolower(c);
toupper(c);