美文网首页
二进制基础运算整理

二进制基础运算整理

作者: Horps | 来源:发表于2020-12-05 12:38 被阅读0次
  • 原码、反码和补码

    在正常的运算规则下,我们熟悉的十进制会转化成二进制在计算机中表示,这时的二进制就是原码表示,在计算机中,为了简化运算单元的逻辑处理、降低硬件电路复杂度和成本,只有加法器的硬件电路,计算机的减法是通过数学变换把其转化成加法运算,比如5-2,也就是5+(-2),但是如果用原码形式去运算5+(-2)得到的值却不是我们想要的值,所以经过探索,又出现了反码和补码,至于他们有什么作用,继续往下看。

    • 原码

      原码就是真值的二进制表示,最高位表示符号位,整数的符号位是0,负数的符号位是1。

      比如十进制真值是6,那么八位二进制的原码就是00000110,最高位是0表示正数;十进制的-3的八位二进制表示为10000011,最高位1表示负数。6-3 = 6+(-3) = 00000110+10000011 = 10001001 = -9,很显然它不是正确值3。

    • 反码

      反码的规则是正数的反码是它本身,负数的反码是符号位不变,其余位取反。

      还是上面的例子,6+(-3)的反码表示为00000110 + 11111100 = 100000010,最高位符号位溢出舍掉,即00000010 = 2 ,因为舍弃后的最高位是0,所以不需要再取反恢复成原码,但这也不是正确结果3,但是他们之间好像有点联系,-3原码10000011和其反码11111100,一个是-3,一个是-124,很多资料都是在补码的时候引入<font color="red">“同余”</font>的概念,但我觉得在反码的时候引入更合理,因为在我看过一些资料之后,我还是不明白为什么是从反码过渡到补码而不是直接从原码到补码。

      • 同余和模的概念

        那同余的概念就是两个数对同一个固定的值取余的结果是一样的,则说明这两个值是同余的关系,这里的固定值通常是指一个系统中的最大值,类比生活中的钟表,在钟表系统中,最大值就是12,过了十二就又会从1开始,如果此时的时间是3点整,那么要修改成6点有两种方式,一种是顺时针拨到6点,此时指针走了3圈,另一种是逆时针拨到6点,此时指针走了9圈,那么3和9就是对于12的一对同余数,12就是这个系统的模。

      • 思想带入二进制

        回到八位二进制,因为八位二进制的最高位是符号位,所以它的真值表示范围就是-127~127(即11111111~01111111),负数范围相当于逆时针,正数范围相当于顺时针,所以它的模应该是127,但并不是,因为相对于钟表,它多了一个0,钟表的12就等于0,0就等于12,所以它的模就是12,而这里的八位二进制的0和127不表示同一个值,所以它的模应该是127+1 = 128。

      • 按位取反就是得到同余数

        前面的-3和-124就是原码反码的关系,按照钟表环形系统的模定义来说,把0和-127两端连接起来,这个点假设叫x,那-3到x的距离在两个方向上的前进步径分别是-3和124(这里假设-3、-2、-1、0的方向是负方向,-3、-4、-5...-127的方向是正方向),所以按位取反就是取得同余数的绝对值。

      经过上面的分析,那么上面的-3的反码-124少加个一个值(0),所以应该是-125,也就是11111101,那最后的结果就是00000011 = 3,这正是我们的正确结果。

    • 补码

      正数的补码是它本身,负数的补码等于其反码+1,之所以加1就是因为二进制和钟表不一样的它是线性结构,-127和0不是同一个值,所以我觉得补码的补在于补差的那个0,同余的概念应该存在于反码的按位取反中,负数x的补码的绝对值也就是2的n次幂+x(注意x是负数)。

  • 逻辑位运算符&、|、~、^、<<、>>

    在很多源码的阅读中,较深入的部分、接近底层的部分都会看到一些二进制中的逻辑运算符,有的时候简单的逻辑运算符就能表达一种动作、一个含义,出于求知欲,这里整理一下基本的逻辑运算符的意义和在开发中他们通常来做些什么。

    • 与运算‘&’

      两个二进制位相与,二者都为1的时候才得1,比如1101&0111 = 0101。

    • 或运算‘|’

      两个二进制位相或,有一个为1即得1,比如1101 | 0001 = 1101。

    • 异或运算‘^’

      两个二进制位异或运算,二者不同才得1,比如1101 ^ 0111 = 1010。

    • 非运算‘~’

      单目运算符,一个二进制位非运算,本以为是按位取反,其实并没有这么简单,c语言中unsigned修饰的整型非运算就相当于按位取反,但是对于非unsigned修饰的整数来讲,比如java中的整型都是有符号的,这些有符号的整数进行非运算的结果却别有洞天,比如在java中~5得到的却是-6,而按照按位取反的逻辑它应该是010=2。

      原因在于无符号的数都是正数,相当于你取反的值就是你的真值,但是有符号数的运算是带着符号位一起做的,比如说有符号数5,二进制应该是0101,最高位0代表正数,~运算会转成1010,因为是正数,所以补码也是这个,计算机的有符号数都是通过补码运算的,无论是不是负数,所以这里会把1010当成负数补码对待,那它的真值就是1110=-6,这就是~5 = -6的由来。

    • 左移‘<<’

      二进制所有位整体左移若干位,若高位溢出则舍弃,低位补0。

      比如5 << 1= 101 << 1 = 1010 = 10,可以发现这里的10是5的2倍,101 << 2 = 10100 = 20,所以左移n位就是扩大至原来的2的n次幂倍。

    • 右移‘>>’

      和左移相反,整体右移n位,数值减小2的n次幂,如果是正数,左边补0,如果是负数左边补1,因为是整型,所以会舍弃小数点后面的,譬如5>>1 = 101>>1=10 = 2。

    • 无符号右移‘>>>’

      相比于>>,不同的是左边都是补0。

    • 实际开发场景应用

      现在考虑一个场景,Java中有4个int型变量NONE = 0 = 00、A = 1 = 01、B = 2 = 10、ANY = 3 = 11,他们分别代表不同的模式,可能需要通过switch根据这个模式去做不同的事情,ANY = A | B,NONE = A & B,那么假设现在传进来一个mode是x,我们要求x是A或者ANY,那么可以通过x & A != 0 来确定。这种方式就是通过按照不同的二进制位来代表不同的东西,通过逻辑运算判断属不属于。

      实际RxJava中requestFusion用到了这种方式:

      @Override
      public int requestFusion(int mode) {
          if ((mode & ASYNC) != 0) {
              outputFused = true;
              return ASYNC;
          }
          return NONE;
      }
      
    • LeetCode中的一个题

      给定一个包含n+1个整数的数组,其数字在1到n之间,内部存在唯一的一个重复数,请找出它。

      做法有很多种,我们这里使用位运算符来做:

      int test(int[] nums){
        int base = 0;
        for(i : nums){
          if(base == (base | (1 << i)))
            return i;
          base |= (1 << i);
        }
      }
      

      首先从第一个元素开始,比如是3,则1<<3 = 1000,base|1000 = 1000,不相等,所以base = 1000,此时第4位已经是1了,表示这个位置有过记录了,假如再次读到3的时候,还是只是会在第4位变成1,也就是说读到重复数的时候,同样位置的二进制位已经变成过1了,base | (1 << i)和之前的base才会相同。

相关文章

  • 二进制基础运算整理

    原码、反码和补码在正常的运算规则下,我们熟悉的十进制会转化成二进制在计算机中表示,这时的二进制就是原码表示,在计算...

  • LeetCode191——位1的个数(位运算)

    位运算基础 位运算基于整数的二进制表示进行运算。由于计算机内部就是以二进制来存储数据,因此位运算会很快。基本的位运...

  • Java基础-位运算

    1-1 Java基础-位运算什么是位运算?一个字节=8位二进制1k=1024字节1k=1024*8位二进制 位运算...

  • 按位与(&)按位或(|)按位异或(^)按位取反(~)左移

    看源码期间遇到了取反(~),就做个记录。 基础知识: 1. and(&)运算 (按位与) and运算通常用于二进制...

  • Java基础-位运算

    1-1 Java基础-位运算 什么是位运算? 一个字节=8位二进制1k=1024字节1k=1024*8位二进制 位...

  • 面试官:你真的搞清位运算了么?

    写在前面 二进制位运算是最贴近计算机真实运算操作,通过位运算,我们可以高效的完成各种基础运算(加减乘除取余等),我...

  • 算法总结-位运算

    位运算符用于二进制运算 与运算 & 二进制数 n & 1 的结果为n的末位 异或运算 ^ 长度为 L 的二进制数 ...

  • Java学习笔记-第一天

    位运算符 位运算是直接对二进制进行运算. 异或运算(^):相同二进制位进行运算,结果是0.不相同二进制位运算结果是...

  • 算法位运算总结

    在位运算之前,对二进制需要掌握的基础知识 正数的二进制,例如 5原码是 0000 0000 0000 0000 0...

  • 2020-04-14

    针对461 汉明距离,一看到,就应该想到位运算,而它的基础是二进制,以及反码,补码,及其运算 对于python 注...

网友评论

      本文标题:二进制基础运算整理

      本文链接:https://www.haomeiwen.com/subject/sshfwktx.html