进制转换与位运算
注意事项
- 比赛时 ide 中编译选项写
-std=c++14
进制转换
进制
- 进制：X 进制用 0~X-1 来计数
- 如果进制超过十进制，那么用字符表示 10 及以上的整数
- 重点：二进制、八进制、十六进制（0~F）
- 二进制 Binary
- 由 0，1 组成，逢二进一
- 二进制在代码中的表示：如十进制 7 写成 0b111
- 八进制 Octal
- 由数码 0~7 组成，每个数码正好对应三位二进制
- 以 0 为前缀书写八进制，如十进制 12 写成 014
- 十六进制 Hexadecimal
- 由数字 0~9 加上字母 A~F 组成，每个数码正好对应四位二进制
- 十六进制在代码中的表示：如十进制 15 写成 0xf
- 十进制 Decimal
进制转换
- X 进制整数转十进制
- \((a_1a_2...a_n)_X=a_1X^{n-1}+a_2X^{n-2}+...+a_nX^0\)
- 从低位枚举到高位进行计算累加答案
- X 进制小数转十进制
- \((a_1a_2...a_nb_1b_2...b_m)_X=a_1X^{n-1}+a_2X^{n-2}+...+a_nX^0+b_1X^{-1}+b_2X^{-2}+...+b_mX^{-m}\)
- 从低位枚举到高位进行计算累加答案
- 负数次幂运算法则：\(X^{-a}=\cfrac{1}{X^a}\)
- 十进制整数转 X 进制
- 使用短除法，每次记下余数
- 把余数反着排列得到最终结果
- 十进制小数转 X 进制
- 整数部分和小数部分分离
- 整数部分正常转换
- 小数部分将除法改为乘法，如：
- \(0.375 * 2 = 0.75\) \((0)\)
- \(0.75 * 2 = 1.5\) \((1)\)
- \(0.5 * 2 = 1\) \((1)\)
- 所以 \((0.375)_{10}=(0.011)_2\)
进制输出
- printf 无法输出二进制
- %d,%i 十进制
- %o 八进制
- %x 十六进制
位运算（只针对整数）
按位与
- 符号：
& - 数学：\(and\)
- 应用
- 将某些二进制位清零而其他位不变
- 判断 \(n\) 从低到高第 \(3\) 位是否是 \(1\)：
n & 4
x & -x求lowbitx & -x = x - (x & x - 1)x -= p, x += x >> 31 & p实现x %= p
按位或
- 符号：
| - 数学：\(or\)
- 应用
- 将某些二进制位置 \(1\) 而其他位不变
- 注意：
||是bool类型的逻辑或，5 || 0 = true || false = true
按位异或
- 符号：
^ - 数学：\(xor\)
- 不同为 1，相同为 0（不进位加法）
按位非（取反）
- 符号：
~ - 特点：单目运算符
- 通过编码可知
~x=-(x+1) if (~x)与if(x != -1)等价short类型最大值：\(2^{15}-1\)
左移
- 符号：
<< - 高位丢弃，低位补 \(0\)
- 左移效果：乘以 \(2\)
右移
- 符号：
>> - 最右边的位丢弃，高位补 \(0\)
- 右移效果：除以 \(2\) 后向下取整
基本运算符优先级
- 算术运算
- 位运算（注意
~优先级很高） - 逻辑运算
- 左移右移 优先级比 按位或 高
- 按位与、按位异或 优先级比 按位或 高
- 按位与 优先级比 按位异或 高
不要相信自己的运算符优先级记忆，根据运算顺序加括号！