位运算全面总结，关于位运算看这篇就够了 |
您所在的位置：网站首页 › 负数按位左移怎么算 › 位运算全面总结，关于位运算看这篇就够了 |
位运算全面总结，关于位运算看这篇就够了
|
文章目录
1 位运算概述2 位运算的性质2.1 运算符的优先级2.2 位运算符的运算律
3 位运算高级操作4 负数的位运算5 位运算的一些应用6 位运算例题6.1 更新二进制位6.2 A+B问题6.3 O(1)时间检测2的幂次
1 位运算概述
我们知道，计算机中的数在内存中都是以二进制形式进行存储的 ，而位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。 那么，涉及位运算的运算符如下表所示： 符号描述运算规则实例（以四位二进制数为例）&与两个位都为1时，结果才为1。 0001 & 0001 = 1 , 0001 & 0000 = 0 , 0000 & 0000 = 0000 0001\&0001=1,0001\&0000=0,0000\&0000=0000 0001&0001=1,0001&0000=0,0000&0000=0000|或两个位都为0时，结果才为0。 0001 ∣ 0001 = 0001 , 0001 ∣ 0000 = 0001 , 0000 ∣ 0000 = 0000 0001|0001=0001,0001|0000=0001,0000|0000=0000 0001∣0001=0001,0001∣0000=0001,0000∣0000=0000^异或两个位相同为0，相异为1。 0001 ∧ 0001 = 0000 , 0001 ∧ 0000 = 1 , 0000 ∧ 0000 = 0 0001 \wedge0001=0000,0001\wedge0000=1,0000\wedge 0000=0 0001∧0001=0000,0001∧0000=1,0000∧0000=0~取反0变1，1变0。 ∼ 0 = 1 , ∼ 1 = 0 \sim0=1,\sim 1 = 0 ∼0=1,∼1=0k=0001，k=2 0100>>k=0001，k=2， k k k是右移的位数，这里 k = 2 k=2 k=2看完，你可能会觉得挺简单的，但位运算的难点并不在这，而在于其性质、高级操作和它的应用。 2 位运算的性质 2.1 运算符的优先级优先级需要弄清楚，如果不太清楚可以加小括号确保是想要的运算顺序，这里只是相对优先级，即只是和一些常用的算术运算符做比较。 优先级运算符结合方向1 − （符号运算符） , ∼ （取反运算符）， + + （自增）， − − （自减） -（符号运算符）,\sim（取反运算符）， ++（自增），--（自减） −（符号运算符）,∼（取反运算符），++（自增），−−（自减）从右到左2 ∗ （乘） , / （除） , % （取余） *（乘）,/（除）,\%（取余） ∗（乘）,/（除）,%（取余）从左到右3 + （加） , − （减） +（加）,-（减） +（加）,−（减）从左到右4 < < （左移）， > > （右移） （右移） （右移）从左到右5 > （大于） , < ( 小于 ) , > = ( 大于等于 ) , < = ( 小于等于 ) >（大于）,=(大于等于),（大于）,=(大于等于), 0010 0100->0010 0100−>0010 x > > 1 x>>1 x>>1在最后加一个 0 0 0 0100 − > 1000 0100->1000 0100−>1000 x < < 1 x0100 0101−>0100，这里实际上就是先确保最低位变为 1 1 1，再减去 1 1 1。 ( x ∣ 1 ) − 1 (x|1)-1 (x∣1)−1最后一位取反 0100 − > 0101 0100->0101 0100−>0101 ，利用异或性质，其中除最后一位其余不变。 x ∧ 1 x\wedge1 x∧1把右数的第 k k k位变为 1 1 1 0001 − > 1001 , k = 4 0001->1001,k=4 0001−>1001,k=4 x ∣ ( 1 < < ( k − 1 ) ) x|(1(k-1)\&1 x>>(k−1)&1把末 k k k位全变为 1 1 1 1000 − > 1111 , k = 3 1000->1111,k=3 1000−>1111,k=3 x ∣ ( ( 1 < < k ) − 1 ) x|((10111 0011−>0111 x ∣ ( x + 1 ) x|(x+1) x∣(x+1)把右起连续的 0 0 0变为 1 1 1 1000 − > 1111 1000->1111 1000−>1111，注意是右起连续的 0 0 0 x ∣ ( x − 1 ) x|(x-1) x∣(x−1)取右边连续的 1 1 1 1011 − > 0011 1011->0011 1011−>0011 ( x ∧ ( x + 1 ) ) > > 1 (x\wedge (x+1))>>1 (x∧(x+1))>>1去掉右起的第一个 1 1 1的左边 1101 − > 0001 1101->0001 1101−>0001 x & ( x ∧ ( x − 1 ) ) x\&(x\wedge (x-1)) x&(x∧(x−1))当然，这里只是一些常用的，并不是全部，位运算的神奇远不止于此。 4 负数的位运算首先，我们要知道，在计算机中，运算是使用的二进制补码，而正数的补码是它本身，负数的补码则是符号位不变，其余按位取反，最后再 + 1 +1 +1得到的， 例如： 15 15 15,原码: 00001111 00001111\space 00001111 补码: 00001111 00001111 00001111 − 15 -15 −15,原码: 10001111 10001111\space 10001111 补码: 11110001 11110001 11110001 那么对于负数的位运算而言，它们的操作都是建立在补码上的，得到的运算结果是补码，最后将补码结果转化成一个普通的十进制数结果。 但需要注意的是，对于有符号数的右移操作，不同的处理器架构可能有不同的规定。在某些架构中（如x86），如果对有符号数执行算术右移（arithmetic right shift），则高位空出来的位置会补上符号位；对于无符号数的右移操作，所有架构都遵循相同的规则：高位空出来的位置会补0。例如对于 − 15 -15 −15，其补码为 11110001 , 11110001, 11110001,右移一位 ( − 15 > > 1 ) (-15>>1) (−15>>1)得到的是 11111000 11111000 11111000，即 − 8 -8 −8，其他的同理。 在大多数现代处理器上，无论是有符号数还是无符号数，左移操作总是将空出来的低位补0。 这里我们介绍几个特殊的性质： 快速判断是否为 − 1 -1 −1 在链式前向星中，我们初始化 h e a d head head数组为 − 1 -1 −1，最后判断是否遍历完 u u u的所有边时，即判断 i i i是否为 − 1 -1 −1，我们直接用 ∼ i \sim i ∼i即可。原因就在于 − 1 -1 −1的补码是 11111111 11111111 11111111，按位取反就变为 00000000 00000000 00000000，这实际上就是 0 0 0。 取最低位的 1 1 1，lowbit函数 也就是 x & ( − x ) x\&(-x) x&(−x)，这在树状数组中起着巨大作用，这里指路一篇树状数组讲解 b l o g blog blog:点这里，我们来证明一下，这里取 x = 15 x=15 x=15，对于 15 & ( − 15 ) 15\&(-15) 15&(−15)，我们知道，在补码上进行运算得到的是 00000001 00000001 00000001，需要注意二元运算的符号位我们需要进行运算。 5 位运算的一些应用位运算实现乘除法 将 x x x左移一位实现 × 2 \times 2 ×2，将 x x x右移一位实现 ÷ 2 \div2 ÷2。 a < < 1 ≡ a ∗ 2 a1 \equiv a/2 a>>1≡a/2 位运算交换两整数 void swap(int &a,int &b){ a ^= b; b ^= a; a ^= b; }这效率非常高，我们来剖析其原理，对于 a = a ∧ b a=a\wedge b a=a∧b，则 b = b ∧ ( a ∧ b ) b = b\wedge(a\wedge b) b=b∧(a∧b)，根据交换律以及异或性质，得 b = b ∧ b ∧ a = 0 ∧ a = a b=b\wedge b\wedge a=0\wedge a=a b=b∧b∧a=0∧a=a，同理 a = ( a ∧ b ) ∧ a = 0 ∧ b = b a=(a\wedge b)\wedge a=0\wedge b=b a=(a∧b)∧a=0∧b=b。这样就实现了交换操作。 位运算判断奇偶数 我们知道，在二进制中，最低位决定了是奇数还是偶数，所以我们可以提取出最低位的值，即与 1 1 1相与即可实现目的，为 0 0 0则是偶数，为 1 1 1则是奇数。 位运算改变正负性和求绝对值 int change(int a){ return ~ a + 1; }对于正数而言，补码就是原码，所以按位取反再 + 1 +1 +1则得到对应真值负数的补码，而对于负数，其补码进行按位取反再 + 1 +1 +1则得到对应真值正数的补码，变为原码。那么知道这个我们就可以特判是否为负数 （这里通过右移 31 31 31位，若为正数，则得到的是 0 0 0，若为负数，则得到的是 − 1 -1 −1，而 0 0 0的补码为 0000 0000 0000, − 1 -1 −1的补码为 1111 1111 1111，根据异或性质即可判断感谢读者 （恢。）指出错误，这里应该是要进行按位取反操作，这样如果为负数判断结果才为0 。） ，利用条件表达式就可以根据判断结果求绝对值了。如下： int abs(int a){ return ~(a >> 31) ? a : ~a + 1; } 位运算实现对 p p p取余（p为 2 k 2^k 2k） int mod(int a,int p){ return a & (p - 1); }取余实际上就是舍去大于等于 p p p的位数，所以我们只需要保留在 p p p范围内的数。由于我们限定了 p p p为 2 k 2^k 2k，所以 ( p − 1 ) (p - 1) (p−1)一定是将小于 p p p的最高位全部变为了 1 1 1，这样再进行与操作即可得到余数。 位运算统计二进制数 1 1 1的个数 int count(int x){ int cnt = 0; while(x){ x = x & (x - 1); cnt ++; } return cnt; }对于任意的 x x x，转换成二进制后，是形如这样的数字： a a . . . a a 10...00 aa...aa10...00 aa...aa10...00，从右向左数有任意多个 0 0 0，直到遇见第一个 1 1 1，字母 a a a用来占位，代表 1 1 1左边的任意数字。 x − 1 x-1 x−1转换成二进制后，是形如这样的数字： a a . . . a a 01...11 aa...aa01...11 aa...aa01...11，从右向左数，原来的任意多个 0 0 0都变成 1 1 1，原来的第一个 1 1 1，变成 0 0 0，字母 a a a部分不变。对 x x x 和 x − 1 x-1 x−1 进行 按位与 计算，会得到： a a . . . a a 00...00 aa...aa00...00 aa...aa00...00，从右向左数，原来的第一个 1 1 1变成了 0 0 0，字母a部分不变。所以 x & ( x − 1 ) x \& (x-1) x&(x−1)相当于消除了 x x x 从右向左数遇到的第一个 1 1 1。那么， x x x转换成二进制后包含多少个 1 1 1，count函数里的循环就会进行多少次，直到 x x x所有的 1 1 1都被“消除”。 6 位运算例题 6.1 更新二进制位题面 给出两个32位的整数N和M，以及两个二进制位的位置i和j。写一个方法来使得N中的第i到j位等于M（M会是N中从第i为开始到第j位的子串） 样例： 输入: N=(10000000000)2 M=(10101)2 i=2 j=6 输出: N=(10001010100)2 输入: N=(10000000000)2 M=(11111)2 i=2 j=6 输出: N=(10001111100)2解题思路 结合所学，我们的思路应该就是先将第 i i i位到第 j j j位全部变为 0 0 0，再将与左移 i i i位的 M M M进行或操作。 AC代码 class Solution { public: int updateBits(int n, int m, int i, int j) { // 循环遍历从第 i 位到第 j 位 for(int pos = i; pos public: int aplusb(int a, int b) { // 当没有进位需要处理时循环结束 while(b != 0){ // temp_a 存储 a 和 b 的按位异或结果，这相当于不带进位的加法 int temp_a = a ^ b; // temp_b 存储 a 和 b 的按位与结果并左移一位，这相当于计算进位 // 因为只有两个位都是1时才会产生进位 int temp_b = (a & b) // 检查 n 是否大于 0 // 2 的幂必须是正数，因为 0 和负数都不是 2 的幂 // 检查 n 和 n - 1 的按位与操作是否为 0 // 如果 n 是 2 的幂，则其二进制表示中只有一个 1 // 例如 2 (10), 4 (100), 8 (1000) // 当 n 是 2 的幂时，n - 1 的二进制表示是 n 的最高位 1 变为 0， // 其余位从 0 变为 1，例如 2 (10) - 1 = 1 (01), 4 (100) - 1 = 3 (011) // 因此 n & (n - 1) 将得到 0 return n > 0 && (n & (n - 1)) == 0; } }; |
【本文地址】
今日新闻 |
推荐新闻 |