侧边栏

二进制计算

发布于 | 分类于 数据结构和算法

虽然很早就接触了二进制，却一直没有正视这个问题，阅读《计算机科学导论》的时候，基本上是跳过了这一部分，总是以“这么基础的东西，反正工作中基本用不上”的理由给搪塞过去。

最近正在阅读《编码》和《程序员的数学思维修炼》，心想终究还是得面对的，于是记录了一点笔记，希望不再回避letcode上关于二进制计算的题目。

10对于我们来讲是一个很平常但又十分神奇的数字。

根据《编码》上面的解释，人类的双手非常适合数数，因而我们早已经适应了以10为基础的数字系统。也正是这个习惯，让我在刚接触二进制的时候，感到无比困惑，明明十分简单的概念，却始终不得要领。

十进制中以0-9这十个数码进行组合来表示数字，且赋予10的整数次幂重大的意义：十，百，千，万，亿...

那么，什么是二进制呢？

概念 ​

二进制就是使用0和1这两个数码进行组合来表示数字的一种计数方法。

计算机使用二进制的主要优点有：

  • 技术实现简单，计算机的逻辑电路只需要表示两个状态（电路的断开与连接），使用1和0表示就够了；如果使用十进制，则只能依靠电压的高低进行区分，这无疑会大大增加技术实现的难度
  • 运算规则简单，二进制的运算规则比十进制少了很多（不需要在文具盒上背诵加法表乘法表了），规则少意味着能够简化计算机的内容结构
  • 适合逻辑运算，计算机不仅需要进行算术运算，还需要进行逻辑元素，二进制只有两个数码，恰好与逻辑代数中的真和假完全吻合！

算术运算 ​

四则预算 ​

加 ​

逢二进一

跟十进制的加法一样，只是进位从10变成了2，这是第一个需要认清的问题

// 加法表
0 + 0 = 0;
1 + 0 = 0;
0 + 1 = 1;
1 + 1 = 1; // 进位1

比如计算111 + 101，从右往左利用基本规则进行计算

  • 第一位（从右往左的顺序）1 + 1 = 0;，进位1,
  • 第二位原本是1 + 0，由于进位变成了1 + 1 = 0，继续进位1,
  • 第三位原本是1 + 1 = 0并进位1，由于进位继续计算0 + 1 = 1，未再次进位
  • 最后结果1100

好吧，我放弃用语言描述这个过程了，老老实实拿笔在纸上算两次就好了，实际上跟十进制没有任何区别，只是需要背诵的加法表缩短为仅仅四条了（考虑到加法交换率，实际上只有3条）！

减 ​

借一当二

// 减法表
0 - 0 = 0;
1 - 1 = 0;
1 - 0 = 1;
0 - 1 = 1; // 借位为1

比如计算111 - 101，最后结果10

乘 ​

与十进制相比（九九八十一种），二进制的乘法要简单得多（只有四种），只有1 * 1 = 1，其余全为0

// 乘法表
0 * 0 = 0;
0 * 1 = 0;
1 * 0 = 0;
1 * 1 = 1;

运算过程也与十进制类似，用第二个乘数的每位依次乘以第一个乘数，最后运用加法规则将结果相加，就得到了两个二进制数的乘积，可以理解为：“0乘以任何数都等于0，而1乘以任意数都等于乘数本身”。 乘法实际上可以看作是加法与移位的操作，如111 * 101可转换为111 + 0000 + 11100 = 100011。

除 ​

// 除法表
0 / 0 = 0; // 无意义
1 / 0 = 0; // 无意义
0 / 1 = 0;
1 / 1 = 1;

除法可以使用试商法进行，先从被除数的最高位开始，将被除数（或中间余数）与除数相比较，若被除数（或中间余数）大于除数，则用被除数（或中间余数）减去除数，商为1，并得相减之后的中间余数，否则商为0。再将被除数的下一位移下补充到中间余数的末位，重复以上过程，就可得到所要求的各位商数和最终的余数。

除法实际上可以看作减法和移位的操作。如：111/101 = 1 余 10。

与十进制的转换 ​

二进制转十进制 ​

虽然只有0和1两个数码，但是在位置化数字系统中，数码所处的位置不同（位置被称为__权__），其代表的实际数据大小也不相同。如1101，在二进制中：

  • 第一个1表示1的个数
  • 第二个0表示2的个数
  • 第三个1表示4的个数
  • 第四个1表示8的个数

好吧，实际上这儿又被带进坑了。更准确的说法是2的0次幂，2的1次幂，2的2次幂，2的3次幂的个数，只是2的2次幂用十进制表示是4，2的3次方幂用十进制表示是8罢了。

可见，只需要计算1*1 + 2*0 + 4*1 + 8*1，就可以二进制转换成十进制的数字了，结果显而易见13。其他二进制转十进制同理。 实际上这种转换方式并不是二进制独有的，其他进制转10进制也可以采用同样的方法，只需要将__基数2__转换成对应进制的基数就行了。

十进制转二进制 ​

十进制转二进制看起来要麻烦一点，通常采用“除2取余，逆序排序的方法”。比如将数字23转换为二进制表示的过程可如下表示：

  • 23/2 = 11...1
  • 11/2 = 5...1
  • 5/2 = 2...1
  • 2/2 = 1...0
  • 最后结果逆序排序表示为1,0,1,1,1，所以23的二进制表示为10111;

上述过程用代码展示应该要清晰一些

javascript
function ten2bin(n){
	if (n == 0){
		return 0;
	}

    var res = "";
    while(n){
        res = n%2 + res;
        n = Math.floor(n/2);
    }
    return res;
}

逻辑运算 ​

计算机不仅执行算术运算，也可以执行逻辑运算。在逻辑代数中，只有__真__和__假__两种逻辑值，这跟二进制中的仅有的两个数码1和0完全吻合。下面整理了关于逻辑运算的一些东西

基本逻辑运算 ​

逻辑运算中，"与"、"或"、"非"是三种最基本的运算规则。

与 ​

使用&&表示__与__运算，参与运算的所有逻辑代数必须全部为真，整个结果才为真。 在电路中表示就是：所有串联的开关必须全部闭合，灯泡才会通电。

1 && 1 = 1
1 && 0 = 0
0 && 1 = 0
0 && 0 = 0

发现没，"与"规则表跟二进制算术运算中的乘法是一模一样的哦！

或 ​

使用||表示__或__运算，参与运算的所有逻辑代数只要有一个为真，整个结果就为真。 在电路中表示就是：所有并联的开关只要有一个闭合，灯泡就会通电。

1 || 0 = 1
1 || 1 = 1
0 || 1 = 1
0 || 0 = 0

同样地，"或"运算规则表跟二进制算术运算中的加法基本一样（逻辑运算中不存在进位的说法）。

非 ​

使用!表示__非__运算，整个逻辑表达式的结果与逻辑代数相反 在电路中表示就是：如果开关闭合，则灯泡被短路；开关断开，灯泡通电

!1 = 0
!0 = 1

复杂逻辑运算 ​

"与"、"或"、"非"是三种最基本的运算规则，其他复杂的逻辑运算都可以用基本运算组合而成。

  • 与非，运算中所有的逻辑代数都为真，则结果为假，!(a && b && c)
  • 或非，运算中只要有一个逻辑代数为真，则结果为假，!(a || b || c)
  • 异或，运算中的两个逻辑代数，有一个为真且另一个为假时，则结果为真，(a&&!b) || (!a && b)
  • 同或，运算中的两个逻辑代数，都为真或者都为假时，则结果为真，(a && b) || (!a && !b)

位运算 ​

大部分高级编程语言都提供了按位操作数字的功能。这一点似乎有些不合理，在日常生活中的计算都是按照某个数字具体代表的值来进行计算的。但是在计算机中，操作数字的某个特定位是很有意义的。下面我们来学习位运算。

位逻辑运算符 ​

位逻辑运算符与逻辑运算符有很大的区别：

  • 位逻辑运算符只操作位（位上的数码只可能是0或者1）
  • 逻辑运算符操作的是真或者假，这是由整个变量的值所决定的

位反 ​

按位取反也叫做二进制反码，使用~表示，指将操作数全部位中的1变成0，将每个0变成1

~1011) 
=0100

按位取反有个小技巧：a取反加一，再取反加一，还等于a 。更通俗一点将，如果操作数为-1，则按位取反结果为0。 这一点很有用处，很多接口都使用-1来表示程序未返回预期结果，比如JavaScript中的indexOf()，此时可以使用~idx来判断，比起idx === -1要好不少（看起来）。

位与 ​

二进制运算符与&通过对两个操作数逐位进行比较，对于每个位置，只有对应的位都为1时，结果对应位置的值才为1，否则为0

  1010
& 1100
= 1000

位于通常用来实现掩码。

位或 ​

二进制运算符或|通过对两个操作数逐位进行比较，对于每个位置，只要任意一个操作数对应位为1时，结果对应位置的值就为1，否则为0

  1010
& 1100
= 1110

位异或 ​

二进制运算符异或^通过对两个操作数逐位进行比较，对于每个位置，只要任意一个操作数对应位为1时，另一个位置为0，结果对应位置的值就为1。

  1010
^ 1100
= 0110

移位运算符 ​

移位运算符将位向左或向右移动。了解移位运算应当首先了解整数的存储形式，在C语言中，一个int类型的整数占4个字节，而通常一个字节包括8个位，即一个整数包含32位。移位运算就是移动整个操作数在32个位中的位置。

二进制中的移位运算类似于十进制中的移动小数点的操作，从而快速进行乘除法。

左移运算符 ​

左移运算符<<将其左侧操作数的值的每位向左移动，移动的位数由右侧操作数指定，空出的位由0填充，并丢弃移出左侧操作数左端的位（如果溢出的话）。

    1010 << 2
= 101000

在不溢出的情况下，左移n位会将操作数扩大2^n倍。

右移运算符 ​

右移运算符将其左侧操作数的值的每位向右移动，并丢弃移出左侧操作数右端的数（肯定会移出的）

  1010 >> 1
=  101

八进制与十六进制 ​

使用二进制存储数据带来的问题是：二进制数字的位数增长十分迅速，保存一个不是很大的数字就需要很长的位数。可见二进制并不适合在计算机外部保存数字，因此产生了八进制和十六进制

八进制 ​

八进制使用0~7这八个数码来表示数字，由于2^3 = 8，因此二进制和八进制的转换十分方便。 从二进制转八进制，只需要从右往将三个二进制分为一组（最左不足可用0填充），然后计算为对应的八进制数码，最后将结果拼接在一起就可以了。比如101110：

  • 将整个数字分为101和110
  • 101计算结果为2^2 + 1 = 5,110计算结果为2^2 + 2^1 = 6
  • 所以101110用八进制表示为56

同理，从八进制转二进制也十分简单，将八进制数字每位拆分成一个三个为二进制数（不足用0填充），然后将结果拼接在一起，比如76用二进制表示为111110，过程这里就不详细写了。

十六进制 ​

十六进制使用0~9加A~F这十六个数码来表示数字。由于2^4 = 16，加之有了八进制与二进制的相互转换规律，十六进制与二进制的相互转换就轻而易举了，无非是将二进制数按4个一组进行划分，或者将一个十六进制数码转换成4位二进制数

  • F2二进制表示为11110010
  • 101101十六进制表示为2D

相关题目 ​

小结 ​

关于二进制的运算先到这里了，另外还有浮点数等知识，先留个坑了。

#二进制

你要请我喝一杯奶茶？

版权声明：自由转载-非商用-保持署名和原文链接。

本站文章均为本人原创，参考文章我都会在文中进行声明，也请您转载时附上署名。