做网站制作要多少费用,网站建设策划基本流程图,server 2012 做网站,网站内页降权 关键词排名下降关卡名 理解位运算的规则 我会了✔️ 内容 1.理解位运算的基本规则 ✔️ 2.理解移位的原理以及与乘除的关系 ✔️ 3.掌握位运算的常用技巧 ✔️
在学习位操作之前#xff0c;我们先明确数据在计算机中怎么表示的。我们明确原码、反码和补码的概念和表示方法#xff0c;之… 关卡名 理解位运算的规则 我会了✔️ 内容 1.理解位运算的基本规则 ✔️ 2.理解移位的原理以及与乘除的关系 ✔️ 3.掌握位运算的常用技巧 ✔️
在学习位操作之前我们先明确数据在计算机中怎么表示的。我们明确原码、反码和补码的概念和表示方法之后介绍位运算相关的问题。
1 数字在计算机中的表示
机器数 一个数在计算机中的二进制表示形式叫做这个数的机器数。机器数是带符号的在计算机用一个数的最高位存放符号正数为0负数为1。比如十进制中的数 3 计算机字长为8位转换成二进制就是00000011。如果是 -3 就是 10000011 。这里的 00000011 和 10000011 就是机器数。真值 因为机器数第一位是符号位所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000011其最高位1代表负其真正数值是 -3 而不是形式值13110000011转换成十进制等于131。所以为了好区别将带符号位的机器数对应的真正数值称为机器数的真值。例0000 0001的真值 000 0001 11000 0001的真值 –000 0001 –1。 计算机对机器数的表示进一步细化原码 反码 补码。原码 就是符号位加上真值的绝对值即用第一位表示符号其余位表示值 比如如果是8位二进制: [1]原 0000 0001 [-1]原 1000 0001 第一位是符号位因为第一位是符号位所以8位二进制数的取值范围就是: [1111 1111 , 0111 1111]也即 [-127 , 127]反码 的表示方法是正数的反码是其本身而负数的反码是在其原码的基础上符号位不变其余各个位取反。例如 [1] [00000001]原 [00000001]反 [-1] [10000001]原 [11111110]反 可见如果一个反码表示的是负数人脑无法直观的看出来它的数值通常要将其转换成原码再计算。 在应用中因为补码 能保持加和减运算的统一因此应用更广其表示方法是:
正数的补码就是其本身负数的补码是在其原码的基础上符号位不变其余各位取反最后1(即在反码的基础上1)。 [1] [00000001]原 [00000001]反 [00000001]补 [-1] [10000001]原 [11111110]反 [11111111]补 对于负数 补码表示方式也是人脑无法直观看出其数值的通常也需要转换成原码在计算其数值。拓展 为何会有原码反码和补码 既然原码就能表示数据那为什么实际软件中更多使用的是补码呢接下来我们就看一看。 现在我们知道了计算机可以有三种编码方式表示一个数对于正数因为三种编码方式的结果都相同: [1] [00000001]原 [00000001]反 [00000001]补 但是对于负数: [-1] [10000001]原 [11111110]反 [11111111]补 可见原码 反码和补码是完全不同的。既然原码才是被人脑直接识别并用于计算表示方式为何还会有反码和补码呢? 首先因为人脑可以知道第一位是符号位在计算的时候我们会根据符号位选择对真值区域的加减。但是计算机要辨别符号位就必须获得全部的位的数据才可以显然会让计算机的基础电路设计变得十分复杂 于是人们想出了将符号位也参与运算的方法。 我们知道 根据运算法则减去一个正数等于加上一个负数 即: 1-1 1 (-1) 0所以机器可以只有加法而没有减法这样计算机运算的设计就更简单了。于是人们开始探索 将符号位参与运算并且只保留加法的方法。 看个例子计算十进制的表达式: 1-10首先看原码的表示 1 - 1 1 (-1) [00000001]原 [10000001]原 [10000010]原 -2 如果用原码表示让符号位也参与计算显然对于减法来说结果是不正确的这也是为何计算机内部不使用原码表示一个数。 为了解决原码做减法的问题就出现了反码此时计算十进制的表达式为: 1-10 1 - 1 1 (-1) [0000 0001]原 [1000 0001]原 [0000 0001]反 [1111 1110]反 [1111 1111]反 [1000 0000]原 -0 可以看到用反码计算减法结果的真值部分是正确的但是0的表示有点奇怪0和-0是一样的而且0带符号是没有任何意义而且要浪费[0000 0000]原和[1000 0000]原两个编码来表示0。于是补码的出现解决了0的符号以及两个编码的问题: 1-1 1 (-1) [0000 0001]原 [1000 0001]原 [0000 0001]补 [1111 1111]补 [0000 0000]补[0000 0000]原 这样0用[0000 0000]表示 而以前出现问题的-0则不存在了而且可以用[1000 0000]表示-128 (-1) (-127) [1000 0001]原 [1111 1111]原 [1111 1111]补 [1000 0001]补 [1000 0000]补 -1-127的结果应该是-128我们正好可以用[1000 0000]来表示-128这样使用补码表示的范围为[-128, 127]这一点也比原码的[-127,127]好。拓展一下对于编程中常用到的32位int类型可以表示范围是: [-2^31, 2^31-1] 这也是我们在应用中经常见到的定义方式。
2 位运算规则
本节的内容很多你可能学过但是请再认真思考一遍因为大量的算法解决思路都是从这里引申出来的 计算机采用的是二进制二进制包括两个数码01。在计算机的底层一切运算都是基于位运算实现的所以研究清楚位运算可以加深我们对很多基础原理的理解程度。 在算法方面不少题目都是基于位运算拓展而来的而且还有一定的技巧如果不提前学一学面试时很难想到。 位运算主要有与、或、异或、取反、左移和右移其中左移和右移统称移位运算移位运算又分为算术移位和逻辑移位。
2.1 与、或、异或和取反
与运算的符号是 运算规则是对于每个二进制位当两个数对应的位都为 1 时结果才为 1否则结果为 0。 0 00 0 10 1 00 1 11 或运算的符号是 |运算规则是对于每个二进制位当两个数对应的位都为 0 时结果才为 0否则结果为 1。 0 ∣ 00 0 ∣ 11 1 ∣ 01 1 ∣ 11 异或运算的符号是 ⊕在代码中用∧ 表示异或运算规则是对于每个二进制位当两个数对应的位相同时结果为 0否则结果为 1。 0⊕00 0⊕11 1⊕01 1⊕10 取反运算的符号是 ∼运算规则是对一个数的每个二进制位进行取反操作0 变成 11 变成 0。 ∼01 ∼10 以下例子显示上述四种位运算符的运算结果参与运算的数字都采用有符号的 8 位二进制表示。
46 的二进制表示是 0010111051 的二进制表示是 00110011。考虑以下位运算的结果。4651的结果是34对应的二进制表示是 00100010。46|51 的结果是63对应的二进制表示是 00111111。46⊕51 的结果是29对应的二进制表示是 00011101。∼46 的结果是−47对应的二进制表示是 11010001。∼51 的结果是 −52对应的二进制表示是 11001100。
2.2 移位运算
移位运算按照移位方向分类可以分成左移和右移按照是否带符号分类可以分成算术移位和逻辑移位。 原始0000 0110 6 右移一次0000 0011 3 相当于除以2 左移一次0000 1100 12 相当于乘以2 6*3 6*(21) 6*26*1 66*3366*(321) 66*3266*1 左移运算的符号是 左移运算时将全部二进制位向左移动若干位高位丢弃低位补 0。对于左移运算算术移位和逻辑移位是相同的。 右移运算的符号是 。右移运算时将全部二进制位向右移动若干位低位丢弃高位的补位由算术移位或逻辑移位决定
算术右移时高位补最高位逻辑右移时高位补 0。
以下例子显示移位运算的运算结果参与运算的数字都采用有符号的 8 位二进制表示。
示例129 的二进制表示是 00011101。29左移 2 位的结果是 116对应的二进制表示是 0111010029 左移 3 位的结果是 −24对应的二进制表示是 11101000。示例250的二进制表示是 00110010。50 右移 1 位的结果是 25对应的二进制表示是 0001100150 右移 2 位的结果是 12对应的二进制表示是 00001100。对于 0和正数算术右移和逻辑右移的结果是相同的。示例3-50的二进制表示是 11001110(补码)。-50 算术右移 2 位的结果是 −13对应的二进制表示是 11110011−50 逻辑右移 2位的结果是 51对应的二进制表示是 00110011。
右移运算中的算术移位和逻辑移位是不同的计算机内部的右移运算采取的是哪一种呢
对于 C/C 而言数据类型包含有符号类型和无符号类型其中有符号类型使用关键字signed 声明无符号类型使用关键字 unsigned 声明两个关键字都不使用时默认是有符号类型。对于有符号类型右移运算为算术右移对于无符号类型右移运算为逻辑右移。对于 Java 而言不存在无符号类型所有的表示整数的类型都是有符号类型因此需要区分算术右移和逻辑右移。在Java 中算术右移的符号是 逻辑右移的符号是 。
2.3 移位运算与乘除法的关系
观察上面的例子可以看到移位运算可以实现乘除操作。由于计算机的底层的一切运算都是基于位运算实现的因此使用移位运算实现乘除法的效率显著高于直接乘除法的。 左移运算对应乘法运算。将一个数左移 k位等价于将这个数乘以 2^k。例如29 左移 2 位的结果是 116等价于 29×4。当乘数不是 2 的整数次幂时可以将乘数拆成若干项 2 的整数次幂之和例如a×6 等价于 (a2)(a1)。对于任意整数乘法运算都可以用左移运算实现但是需要注意溢出的情况例如在 8 位二进制表示下29 左移 3 位就会出现溢出。 算术右移运算对应除法运算将一个数右移 k 位相当于将这个数除以 2^k。例如50 右移 2 位的结果是 12等价于 50/4结果向下取整。 从程序实现的角度考虑程序中的整数除法是否可以说将一个数算术右移 k 位和将这个数除以 2^k等价对于 0 和正数上述说法是成立的整数除法是向 0 取整右移运算是向下取整也是向 0 取整。但是对于负数上述说法就不成立了整数除法是向 0 取整右移运算是向下取整两者就不相同了。例如(−50)2 的结果是 −13而 (−50)/4 的结果是 −12两者是不相等的。因此将一个数算术右移 k 位和将这个数除以 2^k是不等价的。算法出题这早就考虑到了这一点因此在大部分算法题都将测试数据限制在正数和0的情况因此可以放心的左移或者右移。
2.4 位运算常用技巧
位运算的性质有很多此处列举一些常见性质假设以下出现的变量都是有符号整数。
幂等律a aaa ∣ aa注意异或不满足幂等律交换律a bb aa ∣ bb ∣ aa⊕bb⊕a结合律(a b) ca (b c)(a ∣ b) ∣ ca ∣ (b ∣ c)(a⊕b)⊕ca⊕(b⊕c)分配律(a b) ∣ c(a ∣ c) (b ∣ c)(a ∣ b) c(a c) ∣ (b c)(a⊕b) c(a c)⊕(b c)德摩根律∼(a b)(∼a) ∣ (∼b)∼(a ∣ b)(∼a) (∼b)取反运算性质−1∼0−a∼(a−1)与运算性质a 00a (−1)aa (∼a)0或运算性质a ∣ 0a异或运算性质a⊕0aa⊕a0根据上面的性质可以得到很多处理技巧这里列举几个a (a−1) 的结果为将 a 的二进制表示的最后一个 1 变成 0(补码)a (−a)的结果为只保留 a 的二进制表示的最后一个 1其余的 1 都变成 0。处理位操作时还有很多技巧不要死记硬背理解其原理对解决相关问题有很大帮助。下面的示例中1s和0s分别表示与x等长的一串1和一串0 而如何获取、设置和更新某个位的数据也有固定的套路。例如
1.获取
该方法是将1左移i位得到形如00010000的值。接着堆这个值与num执行”位与“操作从而将i位之外的所有位清零最后检查该结果是否为零。不为零说明i位为1否则i位为0。代码如下
boolean getBit(int num,int i){return ((num(1i))!0);
}
2.设置将某一位设置为1
setBit先将1左移i位得到形如00010000的值接着堆这个值和num执行”位或“操作这样只会改变i位的数据。这样除i位外的位均为零故不会影响num的其余位。代码如下
int setBit(int num,int i){return num |(1i);
}
3. 清零将某一位设置为0
该方法与setBit相反首先将1左移i位获得形如00010000的值对这个值取反进而得到类似11101111的值接着对该值和num执行”位与“故而不会影响到num的其余位只会清零i位。
int clearBit(int num ,int i){int mask~(1i);return nummask;}
4.更新
这个方法是将setBit和clearBit合二为一首先用诸如11101111的值将num的第i位清零。接着将待写入值v左移i位得到一个i位为v但其余位都为0的数。最后对之前的结果执行”位或“操作v为1这num的i位更新为1否则为0
int updateBit(int num,int i,int v){int mask~(1i);return (nummask)|(vi);
}
