计算机数据存储方式
例:当(int)x = 10
注:int类型整数共计有32位,不足的位数在前面补0
原码
对于一个
表示原本的二进制数:x = 000…1010
反码
将二进制数的每一位进行取反运算:x = 111…0101
补码
对于x,除符号位不变之外进行~x + 1
的操作:x = 111…0110
进制转换
10进制转2进制: 短除法,逆序取余
2进制转10进制: 乘权求和
二进制转八进制: 取二进制的三位
八进制转二进制
同理,二进制与十六进制之间的转换也可以类比以上的方法,每四位转换为一个十六进制
一张模板走天下
注:在此62进制的数中
0 ~ 9 表示 0 ~ 9
A ~ Z 表示 11 ~ 35
a ~ z 表示 36 ~ 61
另外,此模板使用了高精度,可以适用于所有情况
此题可以简化为两个目标:
- $a$ 进制转十进制(秦九韶迭代)
- 十进制转 $b$ 进制
图解:
1 |
位运算
按位与 &
0 & 0 = 0, 1 & 0 = 0, 1 & 1 = 1
与运算的应用:
取出某一数的后某位
判断一个整数的奇偶性
x & 1 = 0 偶数, x & 1 = 1 奇数
- 返回n的最后一位1以及之后的0:
lowbit(n)
lowbit
实现方式:
1 | int lowbit(int x) |
按位或 |
0 | 0 = 0, 1 | 0 = 1, 1 | 1 = 1
按位异或 ^
0 ^ 0 = 0, 1 ^ 0 = 1, 1 ^ 1 = 0
值得注意的是,按位异或满足交换律和结合律,因此:
一个非常巧妙的解法
1 | int n; |
取反 ~
返回n的第k位数字: n >> k + 1
位运算内建函数
1 | int __builtin_ffs(int x); |
返回 $x$ 的二进制末尾最后一个 $1$ 的位置,位置的编号从 $1$ 开始(最低位编号为 $1$ )。当 $x$ 为 $0$ 时返回 $0$
1 | int __builtin_clz(unsigned int x); |
返回 $x$ 的二进制的前导 $0$ 的个数。当 $x$ 为 $0$ 时,结果未定义 ($ub$)。
1 | int __builtin_ctz(unsigned int x); |
返回 $x$ 的二进制末尾连续 $0$ 的个数。当 $x$ 为 $0$ 时,结果未定义 ($ub$)。
1 | int __builtin_clrsb(int x); |
当 $x$ 的符号位为 $0$ 时返回 $x$ 的二进制的前导 $0$ 的个数减一,否则返回 $x$ 的二进制的前导 $1$ 的个数减一。
1 | int __builtin_popcount(unsigned int x); |
返回 $x$ 的二进制中 $1$ 的个数。