位运算的奇技淫巧（二） |
您所在的位置：网站首页 › 如何判断数字位数 › 位运算的奇技淫巧（二） |
|
位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。 之前有总结过位运算的技巧，但稍微对以前写的文章不太满意，所以重新总结一下 常用的运算符共 6 种，分别为与（ & ）、或（ | ）、异或（ ^ ）、取反（ ~ ）、左移（ ）。 与、或、异或与（ & ）或（ | ）和异或（ ^ ）这三者都是两数间的运算，因此在这里一起讲解。 它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。 运算符 解释 & 只有两个对应位都为 1 时才为 1 ` ` ^ 只有两个对应位不同时才为 1异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 \(a \text{^} b \text{^} b = a\) 。 举例： \[\begin{aligned} 5 &=(101)_2\\ 6 &=(110)_2\\ 5\&6 &=(100)_2 =\ 4\\ 5|6 &=(111)_2 =\ 7\\ 5\text{^}6 &=(011)_2 =\ 3\\ \end{aligned} \]取反取反是对一个数 \(num\) 进行的计算，即单目运算。 ~ 把 \(num\) 的补码中的 0 和 1 全部取反（0 变为 1，1 变为 0）。有符号整数的符号位在 ~ 运算中同样会取反。 补码：在二进制表示下，正数和 0 的补码为其本身，负数的补码是将其对应正数按位取反后加一。 举例（有符号整数）： \[\begin{aligned} 5&=(00000101)_2\\ \text{~}5&=(11111010)_2=-6\\ -5\text{ 的补码}&=(11111011)_2\\ \text{~}(-5)&=(00000100)_2=4 \end{aligned} \]左移和右移num > i 表示将 \(num\) 的二进制表示向右移动 \(i\) 位所得的值。 举例： \[\begin{aligned} 11&=(00001011)_2\\ 112&=(00000010)_2=2 \end{aligned} \]在 C++ 中，右移操作中右侧多余的位将会被舍弃，而左侧较为复杂：对于无符号数，会在左侧补 0；而对于有符号数，则会用最高位的数（其实就是符号位，非负数为 0，负数为 1）补齐。左移操作总是在右侧补 0。 复合赋值位运算符和 += , -= 等运算符类似，位运算也有复合赋值运算符： &= , |= , ^= , = 。（取反是单目运算，所以没有。） 关于优先级位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符，所以使用时需多加注意，在必要时添加括号。 位运算的应用位运算一般有三种作用： 高效地进行某些运算，代替其它低效的方式。 表示集合。（常用于 状压 DP 。） 题目本来就要求进行位运算。 需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。（但像“乘 2 的非负整数次幂”和“除以 2 的非负整数次幂”就最好使用位运算，因为此时使用位运算可以优化复杂度。） 乘 2 的非负整数次幂 int mulPowerOfTwo(int n, int m) { // 计算 n*(2^m) return n > m; }!!! warning 我们平常写的除法是向 0 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 0 时两种方法等价，当数小于 0 时会有区别，如： -1 / 2 的值为 \(0\) ，而 -1 >> 1 的值为 \(-1\) 。 判断一个数是不是 2 的正整数次幂 bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } 对 2 的非负整数次幂取模 int modPowerOfTwo(int x, int mod) { return x & (mod - 1); } 取绝对值在某些机器上，效率比 n > 0 ? n : -n 高。 int Abs(int n) { return (n ^ (n >> 31)) - (n >> 31); /* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1 若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1) 需要计算 n 和 -1 的补码，然后进行异或运算， 结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */ } 取两个数的最大/最小值在某些机器上，效率比 a > b ? a : b 高。 // 如果 a>=b,(a-b)>>31 为 0，否则为 -1 int max(int a, int b) { return b & ((a - b) >> 31) | a & (~(a - b) >> 31); } int min(int a, int b) { return a & ((a - b) >> 31) | b & (~(a - b) >> 31); } 判断符号是否相同 bool isSameSign(int x, int y) { // 有 0 的情况例外 return (x ^ y) >= 0; } 交换两个数 void swap(int &a, int &b) { a ^= b ^= a ^= b; } 获取一个数二进制的某一位 // 获取 a 的第 b 位，最低位编号为 0 int getBit(int a, int b) { return (a >> b) & 1; } 表示集合一个数的二进制表示可以看作是一个集合（0 表示不在集合中，1 表示在集合中）。比如集合 {1, 3, 4, 8} ，可以表示成 \((100011010)_2\) 。而对应的位运算也就可以看作是对集合进行的操作。 操作 集合表示 位运算语句 交集 \(a \cap b\) a & b 并集 \(a \cup b\) `a 补集 \(\bar{a}\) ~a （全集为二进制都是 1） 差集 \(a \setminus b\) a & (~b) 对称差 \(a\triangle b\) a ^ b 二进制的状态压缩二进制状态压缩，是指将一个长度为 \(m\) 的 \(bool\) 数组用一个 \(m\) 位的二进制整数表示并存储的方法。利用下列位运算操作可以实现原 \(bool\) 数组中对应下标元素的存取。(xor 等价于 ^) 操作 运算 取出整数 n 在二进制表示下的第 k 位 (n >> k) & 1 取出整数n 在二进制表示下的第 0 ~ k - 1 位 (后 k 位) n & ((1 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |