title: 位运算和常用库函数
tags: acm算法
categories: acm算法
位运算
与 &
- 0&0 == 0
- 0&1 == 0
- 1&1 == 1
或 |
- 0|0 == 0
- 1 | 0 == 1
- 0 | 1 == 1
- 1 | 1 == 1
非 ~
- ~0 == 1
- ~1 == 0
异或 ^ XOR
- 不进位加法
- 0 ^ 0 == 0
- 1 ^ 1 =0
- 1 ^ 0 == 1
- 0 ^ 1 == 1
- 按照每一位进行按位异或
右移 >>
- 求x的第k位数字:x >> k & 1
- 右移k位相当于除以2的k次方
左移 <<
- 左移k位相当于乘以2的k次方
求一个数的二进制表示方法:
int a = 13;
for(int i = n;i >= 0;i --){
cout << (a >> i & 1)
}
这里的5是最大求到2的多少次方的位数,0是2的0次方,从n到2的0次方依次提出来
返回x的最后一位1:
- lowbit(x) = x & -x