一、位操作
基本的位运算符
名称 | 符号 | 运算规则 |
---|---|---|
与 | & | 当且仅当两位均为1时输出1 |
异或 | ^ | 两位**相同输出0,相异输出1 ** |
或 | | | 当且仅当两位**均为0时输出0 ** |
取反 | ~ | **输入0输出1,输入1输出0 ** |
左移 | << | 各二进位左移若干位,低位补0 |
右移 | >> | 各二进位右移若干位,高位补0或符号位 |
注意事项
1、取反为单目运算符,表达式为~expr
,其余均为双目运算符,表达式为expr1 & expr2
等。
2、位运算符优先级由大到小:取反、左移/右移、与、异或、或。除取反以外的运算符优先级低于加减运算,使用时注意有时需要加括号。
3、位操作只能用于整形数据,对其他类型进行位操作会被编译器报错。
4、对有符号整型的位移操作对于不同编译器表现不同;主要体现在右移之后补位的操作,部分编译器会在高位补0而不是符号位。(也就是算术右移和逻辑右移的差别)对于无符号整型,高位均补符号位。
5、位运算支持复合操作符,即&=
、^=
、|=
、~=
、<<=
和>>=
。
二、二进制常规变换操作
部分功能来自Matrix67的博客。
功能 | 示例 | 位运算 |
---|---|---|
去掉最后一位 | (101101->10110) | x >> 1 |
在最后加一个0 | (101101->1011010) | x << 1 |
在最后加一个1 | (101101->1011011) | (x << 1) + 1 |
把最后一位变成1 | (101100->101101) | x | 1 |
把最后一位变成0 | (101101->101100) | (x | 1) - 1 |
最后一位取反 | (101101->101100) | x ^ 1 |
把右数第k位变成1 | (101001->101101,k=3) | x | (1 << (k-1)) |
把右数第k位变成0 | (101101->101001,k=3) | x & ~(1 << (k-1)) |
右数第k位取反 | (101001->101101,k=3) | x ^ (1 << (k-1)) |
取末三位 | (1101101->101) | x & 7 |
取末k位 | (1101101->1101,k=5) | x & ((1 << k) - 1) |
取右数第k位 | (1101101->1,k=4) | x >> (k-1) & 1 |
把末k位变成1 | (101001->101111,k=4) | x | ((1 << k) - 1) |
末k位取反 | (101001->100110,k=4) | x ^ ((1 << k) - 1) |
把右边连续的1变成0 | (100101111->100100000) | x & (x+1) |
把右起第一个0变成1 | (100101111->100111111) | x | (x+1) |
把右边连续的0变成1 | (11011000->11011111) | x | (x-1) |
取右边连续的1 | (100101111->1111) | (x ^ (x+1)) >> 1 |
去掉右起第一个1的左边 | (100101000->1000) | x & (x ^ (x-1)) |
三、原码 反码 补码
概念
原码:即该数的二进制表示,用首位来表示符号:正数为0,负数为1。
反码:正数的反码等于其原码;负数的反码等于其原码符号位不变,其他位取反。
补码:正数的补码等于其原码;负数的补码等于其反码加1。
表示
注意,这里为了演示方便,使用8位二进制数表示。实际上的(int)类型为4个字节,即32位。
原码的表示:
([+11] = [0000 1011]_原)
([-11] = [1000 1011]_原)
因此,原码8位二进制数的表示范围为([1111 1111, 0111 1111]),即([-127, 127])。
反码的表示:
([+45] = [0010 1101]_原 = [0010 1101]_反)
([-45] = [1010 1101]_原 = [1101 0010]_反)
补码的表示:
([+14] = [0000 1110]_原 = [0010 1111]_补)
([-45] = [1000 1110]_原 = [1111 0010]_补)
特殊地,补码的表示范围为([1111 1111, 0111 1111]_补),即([-128, 127])。
如果只是准备初赛知识点或者不打算深入了解的话,将上面三条背下来就可以跳至第四节了。如果想要深入学习,也建议在开始下面的内容前先记牢这三条概念。
使用反码、补码的原因
由于效率原因,计算机在运算时并不会特别对符号位进行辨别。这就需要一种方式来进行符号位的调整。
例如,
如果只用原码运算的话:
结果为([-2]),显然是错误的。
但如果用反码来处理减法运算:
结果为([-0]),在数值上来看看似是正确的,但是([-0]=[1000 0000])与([0]=[0000 0000])事实上是不同的机器码。
于是可以用补码来处理运算:
这样的话,就可以修复([0])和([-0])编码不同的问题。另外,如同上一段“表示”中所说,补码的可表示范围比原码和反码略大,可以多表示一个最小值。
此外,使用补码的更深入的原因可以从数学上的同余角度来说明。简单地说,由于符号位也参与计算,正好能够和溢出的最高位形成正确的运算结果。因此,将负数部分转化为补码可以大幅减少运算的处理难度。
四、掩码/位掩码(Mask/BitMask)
掩码事实上和前面介绍的位运算关系不是很大,但是掩码的思想在OI中较常用,因此介绍一下。
概念
掩码是利用一段二进制掩码来处理原数据,经过按位运算或逻辑运算,达到屏蔽指定位数的目的。
应用
如前面“二进制常规变换操作”中介绍过的“把右数第3位变成1”操作,可以看作一种掩码操作。如:
原数据:([1101 1010])
由于要屏蔽后三位,构造一个掩码:([0000 0111]),
对原数据和掩码进行按位或运算:
即可达到将后三位变为1的目的。
素数筛的一个常用优化中,用二进制数代替bool数组存储信息时,取出特定一位的信息的操作即可看作一种掩码运算。
如一段原数据:([1101 1010]),我们想知道它的从右数第3位是1还是0:
构造一个掩码:([0000 0100])
注意,由于取出第三位的操作相当于屏蔽其他所有位的操作,只将第三位置为1即可。
将原数据与掩码进行按位与运算:
由于计算结果中唯一可能不为0的位即是我们要判断的位置,只要判断计算结果是否为0即可。
五、总结
实际上,位运算可读性和健壮性都不如常规运算好,但是在某些情形下的确可以提高代码的时空效率。
在许多古老的微处理器上,位运算比加减运算略快,通常位运算比乘除法运算要快很多。在现代架构中,情况并非如此:位运算的运算速度通常与加法运算相同(仍然快于乘法运算)。
而且,位运算的进一步使用可以很快地处理一些特殊情况下的问题。因此,对于OIer来说,学习位运算至少是没有坏处的。
此外,位运算作为不加转义的直接运算,对了解计算机的计算原理很有帮助。这一点对以后的进一步深造会奠定很好的基础。