网站开发过程总结,深圳市深企在线技术开发有限公司,网站开发资质要求,个人短信接口wordpress目录 数字在计算机中的表示#xff1a;机器数、真值对机器数进一步细化#xff1a;原码、反码、补码为何会有原码、反码和补码为何计算机中的按位运算使用的是补码#xff1f;位运算规则与、或、异或和取反移位运算移位运算与乘除法的关系位运算常用技巧⭐️ 操作某个位的数… 目录 数字在计算机中的表示机器数、真值对机器数进一步细化原码、反码、补码为何会有原码、反码和补码为何计算机中的按位运算使用的是补码位运算规则与、或、异或和取反移位运算移位运算与乘除法的关系位运算常用技巧⭐️ 操作某个位的数据⭐️获取设置清零更新 数字在计算机中的表示机器数、真值 机器数 一个数在计算机中的二进制表示形式叫做这个数的机器数。机器树时带符号的在计算机中用一个数的最高位存放符号正数为0负数为1. 比如 计算机字节长为8位下面二进制就是机器数
十进制的 3,转换成二进制就是 00000011
十进制的 -3,转换成二进制就是 10000011真值 因为机器数第一位是符号位所以机器数的形式值就不等于真正的数值。 所以为了好区别将带符号位的机器数对应的真正数值称为机器数的真值。 比如 0000 0001 的真值 000 0001 1
1000 0001 的真值 -000 0001 -1对机器数进一步细化原码、反码、补码 原码 就是符号位加上真值的绝对值即用第一位表示符号其余位表示值。比如如果是8位二进制 [1] 原码 0000 0001
[-1] 原码 1000 0001第一位是符号位因为第一位是符号位所以8位二进制的取值范围是 [1111 1111, 0111 1111]即[-127, 127] 反码 正数的反码是其本身而负数的反码是在其原码的基础上符号位不变其余各个位取反。比如 [1] [0000 0001]原 [0000 0001]反
[-1] [1000 0001]原 [1111 1110]反可见如果一个反码表示的是负数人脑无法直观的看出来它的数值通常要将其转换成原码再计算。 补码 在应用中因为补码能保持加减运算的统一因此应用更广其表示方法是 正数的补码就是其本身负数的补码是在其原码的基础上符号位不变其余各位取反最后1即在反码的基础上1 [1] [0000 0001]原 [0000 0001]反 [0000 0001]补
[-1] [1000 0001]原 [1111 1110]反 [1111 1111]补对于负数补码表示方式也是人脑无法直观看出其数值的通常也需要转换成原码再计算其数值。
为何会有原码、反码和补码
看个例子计算十进制的表达式: 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] 这也是我们在应用中经常见到的定义方式。
为何计算机中的按位运算使用的是补码
对于计算机中的按位运算包括与操作AND、或操作OR、异或操作XOR等使用补码表示是最为常见的因为补码可以统一处理正数和负数而且在进行数值运算时能够保持一致性。
统一性和一致性补码表示法允许我们用同一种方式处理正数和负数。在补码中负数的表示是通过正数的按位取反再加1来得到的。这就意味着无论是正数还是负数在计算机内部都是用相同的机制进行表示和运算的不需要针对正负数分别编写不同的逻辑。溢出处理在进行二进制运算时可能会出现溢出。使用补码可以更方便地处理溢出情况。例如当两个正数相加得到负数的情况或者两个负数相加得到正数的情况在补码中能够更自然地处理无需额外的特殊逻辑。零的表示使用补码表示法零的表示是唯一的即所有位都是0不管是正数还是负数的零。这样进行与操作时如果某一位是零与任何数进行与操作都不会改变那一位的值。简化硬件逻辑使用补码可以简化硬件逻辑设计。在计算机内部进行补码的加法、减法、与操作等都可以使用相同的电路结构从而降低了硬件设计的复杂度。
综上所述补码在计算机内部的数值表示和运算中具有很多优势可以统一处理正数和负数、简化逻辑设计并且处理溢出等情况更为方便。因此在计算机中的位运算如与操作通常都是使用补码表示来进行的。
位运算规则
位运算主要有与、或、异或、取反、左移和右移。其中左移和右移统称为移位运算移位运算又分为算数移位和逻辑移位。
与、或、异或和取反 与运算符 运算规则是对于每个二进制位两个数对应的位都是1时结果为1否则结果为0。都是1为1否则是0 0 0 0
0 1 0
1 0 0
1 1 1或运算符| 运算规则是对于每个二进制位两个数对应的为都是0时结果为0否则结果为1。都是0为0为否是1 0 | 0 0
0 | 1 1
1 | 0 1
1 | 1 1异或运算符⊕在代码中用∧ 表示异或运算规则是对于每个二进制位两个数对应的位相同时结果为 0否则结果为 1。相同为0不同为1 0 ⊕ 0 0
0 ⊕ 1 1
1 ⊕ 0 1
1 ⊕ 1 0取反运算符~ 运算规则是对一个数的每个二进制位进行取反操作0变成1,1变成0。每个位 0变1,1变0 ~0 1
~1 0移位运算 左移运算符 将全部二进制位向左移动若干位高位丢弃低位补 0。对于左移运算算术移位和逻辑移位是相同的。 右移运算符 将全部二进制位向右移动若干位低位丢弃高位的补位由算术移位或逻辑移位决定 算术右移时高位补最高位逻辑右移是高位补0。
原始 0000 0110 6
右移一次0000 0011 3 相当于除以2
左移一次0000 1100 12 相当于乘以2移位运算与乘除法的关系
观察上面的例子可以看到移位运算可以实现乘除操作。由于计算机的底层的一切运算都是基于位运算实现的因此使用移位运算实现乘除法的效率显著高于直接乘除法的。
左移运算对应乘法运算。将一个数左移 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的情况因此可以放心的左移或者右移。 位运算常用技巧⭐️
位运算的性质有很多此处列举一些常见性质假设以下出现的变量都是有符号整数。 幂等律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) −1~0
在计算机中负数的表示通常使用二进制的补码表示法。
-1 [1000 0001]原 [1111 1110]反 [1111 1111]补
0 [0000 0000]原 [0000 0000]反 [0000 0000]补~0 [1111 1111]补
在这种特定情况下-1与~0的二进制表示是相同的。−a~(a−1)
假设a的二进制表示是00000101即十进制的5。考虑等式的右边~(a - 1)
那么(a - 1)的二进制表示就是00000100即十进制的4。
对(a - 1)的每一位按位取反得到11111011。计算等式的左边-a
首先取a的每一位按位取反得到11111010。
然后再加1得到11111011与等式右边的结果相同。这个等式的成立是基于补码运算和按位取反的性质。与运算性质a 00a (−1)aa (∼a)0 a (−1)a
在二进制补码表示中-1 的所有位都是1即所有位取反后加1。
-1 [1000 0001]原 [1111 1110]反 [1111 1111]补
无论 a 的某一位是0还是1在与 -1 进行与操作后结果的对应位都会保持不变。a (~a)0
对于任意整数 a按位取反操作 ~a 将 a 的每一位取反0 变 11 变 0
如果 a 的某一位是 0那么 ~a 的对应位是 1所以在 运算中结果位为 0。
如果 a 的某一位是 1那么 ~a 的对应位是 0所以在 运算中结果位也为 0。或运算性质a ∣ 0aa ∣ (∼a)−1 a ∣ (~a)−1
对于任意整数 a按位取反操作 ~a 将 a 的每一位取反0 变 11 变 0
如果 a 的某一位是 0那么 ~a 的对应位是 1所以在 | 运算中结果位为 1。
如果 a 的某一位是 1那么 ~a 的对应位是 0所以在 | 运算中结果位也为 1。异或运算性质a⊕0aa⊕a0
处理位操作时还有很多技巧不要死记硬背理解其原理对解决相关问题有很大帮助。下面的示例中1s和0s分别表示与x等长的一串1和一串0
操作某个位的数据⭐️
如何获取、设置和更新某个位的数据也有固定的套路。例如
获取
该方法是将1左移 i 位得到形如00010000的值。接着对这个值与num执行”位与“操作从而将 i 位之外的所有位清零最后检查该结果是否为零。不为零说明 i 位为1否则 i 位为0。代码如下
func getBit(num int, i int) bool {return num (1 i) ! 0
}设置
setBit先将1左移 i 位得到形如00010000的值接着堆这个值和num执行”位或“操作这样只会改变 i 位的数据。这样除 i 位外的位均为零故不会影响num的其余位。代码如下
func setBit(num int, i int) int {return num | (1 i)
}清零
该方法与setBit相反首先将1左移 i 位获得形如00010000的值对这个值取反进而得到类似11101111的值接着对该值和num执行”位与“故而不会影响到num的其余位只会清零 i 位。
func clearBit(num int, i int) int {mark : ~(1 i)return num mark
}更新
这个方法是将setBit和clearBit合二为一首先用诸如11101111的值将num的第 i 位清零。接着将待写入值 v 左移 i 位得到一个 i 位为 v 但其余位都为0的数。最后对之前的结果执行”位或“操作v为1这num的 i 位更新为1否则为0
func updateBit(num int, i int, v int) int {mark : ~(1 i)return (num mark) | (v i)
}
