字节
位运算
二进制实现加减乘除
讲一下四则运算表达式
字符编码
Bas64编解码
URL encoding
字节
0 或 1
1byte = 8位
一个字节的范围-128~127, 2^8 = 256
在计算机中，一个字节是由8位二进制组成，例如：1100 1111
字节通常写为"B"，位通常写为"b"，计算机存储器的大小通常用字节表示
带宽及码率通常是位表示，例如：kbps，mbps，一秒钟传输所需的带宽大小，这个单位是"位"，对比我们平常所说流量大小需要单位/8
例如：家的网络带宽是100mbps=100*1000kbps，为什么我的下载流量没有达到那么高，这里需要说明的是，下载的流量是存储单位，在计算机中是用字节表示的，是位单位的1/8。也就是：100M的带宽，对应的实际流量是100/8 = 12.5M
带宽分为上/下行，一般的路由上/下行带宽分配比例是1:8，也就是说，上行是占总带宽的1/9，下行是占总带宽的8/9（可以通过路由器自定义调整），那么对应的100mbps带宽，实现下载流量大约是11M左右，上行流量大约是1.5M左右
位运算
& 与运算：两个位都为1时，结果才是1
| 或运算：两个位都为0时，结果才是0
^ 异或运算：两个位相同为0，相异为1
~ 取反：0变1，1变0
<< 左移：各个二进位全部移动若干位，低位补零
>> 右移：各个二进位全部移动若干位，高位补零
与运算
清零（所有位都和0做与运算）
取一个数的指定位（例如：1010 1110，取低四位的数，和 0000 11111做与运算，得出1110）
判断奇偶（根据末尾进行判断，0是偶数，1是奇数，if（x&1 == 0））
if (x & 1 == 0) return TURE;return FALSE;
或运算
用来对一个数据某些位置设置为1（例如：1010 1110，低四位设置为1，和0000 1111做或运算，得出1010 1111）
异或运算
总结：如果两个相应位相同为0，相异为1
特性：交换（a=a^b;b=a^b;a=a^b;）结合（(a^b)^c = a^(b^c)）对于任何数，都符合(a^a = 0, a^0=a)自反（a ^ 1, 末尾取反，0是不变，1是取反）
翻转指定位（例如：1010 1110，将其低四位进行翻转，和0000 1111做异或运算，得到1010 0001）
交换两个数，且无需引用多余的指针（a=a^b;b=a^b;a=a^b;）
void swap(int &a, int &b){ if (a !=b)
{
a = a^b;
b = a^b;
a = a^b; // 注意此时的a=a^b;此时的b=a;
}
}取反运算
总结：对一个二进制数位取反，0变1，1变0
~1 = 0； ~0 = 1；
使一个数的最低位为0（例如：1010 0001 & ~1 = 1010 0000，~运算符的优先级高于其它符号）
左/右移运算
左移1位（相当于乘以2，1010 0001 << 2 = 10 1000 0100）
右移1位（相当于除以2，1010 0001 >> 2 = 10 1000 00）
用于进位操作
二进制实现加减乘除
加法
首先来说一下，十进制的相加方法：
例如1：14 + 7 = 21 ， 首先不考虑进位等于11，由于4+7需要进位10，那么11 + 10 = 21；
例如2：136 + 967 = 1103，首先不考虑进位等于093，需要进位1010，那么093 + 1010 = 1103；
136 + 967 进位说明：
个位 6 + 7 进位 10
十位 3 + 9 不进位 0
百位 9 + 1 进位 100
需要进位的值10+1000 = 1010
例如3：9176 + 967 = 10143，不考虑进位等于9033，需要进位1110，那么9033 + 1110 = 10143；
9176 + 967 进位说明：
个位 6 + 7 进位 10
十位 7 + 6 进位 100
百位 1 + 9 进位 1000
千位 9 + 0不进位 0
需要进位的值10+100+1000 = 1110
证明：两个数字相加的时候，不考虑进位的值相加，最后再加上进位的值，得出最终的结果；
二进制，每位相加，逢二进一；例如：01 + 01 = 10
同理二进制，亦是如此，符合不考虑进位相加，再加上进位的值，但是二进制需要做一下逻辑运算的转换；
首先不考虑进位的情况下
1 + 1 = 0 （1 ^ 1 = 0） 1 + 0 = 1 （1 ^ 0 = 1） 0 + 1 = 1 （0 ^ 1 = 1） 0 + 0 = 0 （0 ^ 0 = 0） 规律如下：位值相同，相加为0；位值相异，相加为1再不考虑进位的情况下，符合"异或运算"； a ^ b
2.接着考虑进位的问题
1 + 1 = 1（1 & 1 = 1）1 + 0 = 0 （1 & 0 = 0）0 + 1 = 0 （0 & 1 = 0）0 + 0 = 0 （0 & 0 = 0）规律如下：符合与运算
3.相加 a + b
不进位值相加 = a ^ b
进位的值相加 = a & b << 1累计相加 = a ^ b + a & b << 1递归循环调用，直至进位的值相加为0，也就是说无需再次进位
a + b = a ^ b + a & b << 1int add(int a, int b){ if (b == 0 ) return a; return add(a ^ b,a & b << 1);
}减法
减法思考，将减法做成加法，例如：9176 + 967 = 9176 +（-967）
那么，在二进制中，如何将一个值表达为负数，例如：0000 1000 = 8，那么-8 = 1000 1000
通过2的补码，它是一种用二进制表示有号数的方法，也是一种将数字的正负号变号的方式，其实现的步骤如下：
1、每一个二进制位取反值，0变1，1变0（即反码）
2、将反码加1
对于负值的表示方法，其实就是取反加一// a 是减数 // b 是被减数int subtraction(int a, int b){ int negative = addition(~b,1); //取反加1，得到的负数
return add(a,negative);
}乘法
乘法思考，将乘法做成加法，例如：16 * 15 , 就相当于16个15相加，或是15个16相加
int multiplyAction(int a, int b){ // 首先取绝对值
int a1 = a < 0 ? subtraction(0,a) : a;
int b1 = b < 0 ? subtraction(0,b) : b; int product = a1; while(--b1)
{
product = addition(product,a1);
} // 判断正负
if (a < 0 | b < 0)
{ // 取反加1，得到负数
return addition(~product,1); // return subtraction(0,product)
} return product;
}除法
除法思考，将除法做成减法，例如：120 / 23 = 5.217 (四舍五入 = 5) ，就当于减去了5次23，剩下的值是余数，判断余数是否大于23的一半，进而判断是否是需要四舍五入
int division(int a, int b){ // 首先取绝对值
int a1 = a < 0 ? subtraction(0,a) : a;
int b1 = b < 0 ? subtraction(0,b) : b; int productCount = 0; while(true)
{
a1 = subtraction(a1,b1); // 判断余数，计算四舍五入
if (a1 < b1)
{ if ((b1 >> 2) > a1){ break;
}
}
productCount = addition(productCount,b1);
} // 判断正负
if (a < 0 | b < 0)
{ // 取反加1，得到负数
return addition(~productCount,1); // return subtraction(0,product)
} return productCount;
}// 此方法的效率比较低，如果除数比被除数大很多的时候，就增加了很多次的遍历，通过算法相减的方法// 目前是按照1倍被除数相减，当然了也可以按照2倍，3倍甚至多倍的思路来实现// 有兴趣的同学，可以再此算法上做继续的优化讲一下四则运算表达式
计算器的加减乘除是如何实现的（数学表达式的求值方式）
计算规则：先乘除，后加减，从左到右，先括号后括号外
20世纪50年代，波兰逻辑学家提出"一种不需要括号的后缀表达式"，称值为逆波兰（Reverse Polish Notaiton， RPN）
首先看一下中缀表达式
中缀表达式如何转后缀表达式
后缀表示是如何计算结果的
我们平常使用的表达式就中缀表达式，例如：3-5*(6/3)+2/(3*8)
那么如何将中缀表达式转换为后缀表达式呢？
规则：从左到右遍历数字和符号，如是数子输出；如是符号，则判断与栈顶符号的优先级，右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次输出，并将当前符号进栈，直至全部输出。
例如：3-5*(6/3)+2/(3*8)
1、初始化一个空栈，用来对符号进行出栈使用
2、第1个字符是3，直接输出；【输出：3】
3、第2个字符是-，栈顶为空，入栈 【栈：- 】
4、第3个字符是5，直接输出，【栈：- 】【输出：3 5】
5、第4个字符是*，对比栈顶-，*优先级高于栈顶，入栈，【栈：- *】
6、第5个字符是(，直接入栈，【栈：- * (】
7、第6个字符是6，直接输出，【输出：3 5 6】
8、第7个字符是/，因为还没有找到)，所以入栈，【栈：- * ( / 】
9、第8个字符是3，直接输出，【输出：3 5 6 3】
10、第9个字符是），匹配栈里面的（，【输出：3 5 6 3 /】 【栈：- * 】
11、第10个字符是+，对比栈顶*，优先级低于栈顶，全部出栈，【输出：3 5 6 3 / * -】【栈：+ 】
12、第11个字符是2，直接输出，【输出：3 5 6 3 / * - 2】
13、第12个字符是/，对比栈顶+，优先级高于栈顶，所以入栈，【栈：+ /】
14、第13个字符是(，直接入栈，【栈：+ / （】
15、第14个字符是3，直接输出，【输出：3 5 6 3 / * - 2 3】
16、第15个字符是*，对比栈顶元素（，直接入栈，【栈：+ / （ *】
17、第16个字符是8，直接输出，【输出：3 5 6 3 / * - 2 3 8】
18、第17个字符是），匹配（， 左括号和右括号中间依次出栈，【输出：3 5 6 3 / * - 2 3 8 *】 【栈：+ / 】
19、剩余栈中元素，依次出栈 【输出：3 5 6 3 / * - 2 3 8 * / +】
后缀表达式是如何进行计算的
规则：从左到右边依次遍历表达式，遇到数字就进栈，遇到符号，就将处于栈顶两数字出栈，进行运算（注意：栈顶2 计算符号 栈顶1元素，注意顺序），运算结果进栈，一直最终获得结果
例如：3 5 6 3 / * - 2 3 8 * / +
1、第1个字符是3，入栈【栈：3】
2、第2个字符是5，入栈【栈：3 5】
3、第3个字符是6，入栈【栈：3 5 6】
4、第4个字符是3，入栈【栈：3 5 6 3】
5、第5个字符是/，取得栈顶2个元素进行计算（3 和 6 出栈），6 / 3 = 2 ，将2入栈【栈：3 5 2】
6、第6个字符是*，取得栈顶2个元素进行计算（2 和 5 出栈），5 * 2 = 10 ，将10入栈【栈：3 10】
7、第7个字符是-，取得栈顶2个元素进行计算（3 和 10 出栈），3 - 12 = -7 ，将-7入栈【栈：-7】
8、第8-10个字符是2 3 8，依次入栈【栈：-7 2 3 8】
9、第11个字符是*，取得栈顶2个元素进行计算（3 和 8 出栈），8 * 3 = 24，，将24入栈【栈：-7 2 24】
10、第12个字符是/，取得栈顶2个元素进行计算（2 和 24 出栈），2 * 24 = 1/12，，将1/12入栈【栈：-7 1/12】
11、第13个字符是+，取得栈顶2个元素进行计算（1/12 和 -7 出栈），-7 * 1/12 = -83/12，入栈
12、字符变量结束，最后一个元素出栈得出结果:-83/12
再举一个复杂的表达式：5 + [ ( 3 - 7 ) / ( 9 * 3 + 2 ) ] * 4 - 6
中缀表达式转化后缀表达式的过程（简化版）
1、5 【栈：+ [ (】
2、5 3【栈：+ [ ( -】
3、5 3 7【栈：+ [ ( - )】 再次输出5 3 7 -【栈：+ [ 】
4、5 3 7 - 9【栈：+ [ / ( *】
5、5 3 7 - 9 3【栈：+ [ / ( *】 再次输出5 3 7 9 3 * 【栈：+ [ / ( +】
6、5 3 7 - 9 3 * 2 + 【栈：+ [ / ( + ）】，【栈：+ [ / ] 】
7、5 3 7 - 9 3 * 2 + /【栈：+ 】
8、5 3 7 - 9 3 * 2 + / 4【栈：+ *】
9、5 3 7 - 9 3 * 2 + / 4 * + 【栈：-】
10、5 3 7 - 9 3 * 2 + / 4 * + 6【栈：-】
11、5 3 7 - 9 3 * 2 + / 4 * + 6 -
最终得到后缀表达式：5 3 7 - 9 3 * 2 + / 4 * + 6 -
总结
四则表达式，其实就运用了栈的思想，实现了后缀表达式
1、将中缀表达式转化为后缀表达式（按照加减乘除优先级来运算符号，去除了括号）
2、将后缀表达式进行运算得出结果（进行运算数字，注意运算的顺序）
编码
ASCII码
在计算机中，所有的数据在存储和运算时都要使用二进制表示，就像a,c,d26个字母以及0-9数字及一些常用的符号，在计算机中存储也要使用二进制来表示；
而具体的要那些二进制来表示那些符号，那么就提出了ASCII编码，是由美国标准信息交换代码制定的，用于文本数据
ASCII码用指定的7位或8位二进制组合来表示128或256种的可能字符；使用7位表示二进制（剩下一位二进制为0），也就是一个字节大小的存储来表示。
0～31及127(共33个)是控制字符或通信专用字符（不可显示的字符），例如：换行，回车，删除等。
32～126(共95个)是字符(32是空格），其中48～57为0到9十个阿拉伯数字。
65～90为26个大写英文字母，97～122号为26个小写英文字母，其余为一些标点符号、运算符号等。
例如：一串字符"abc123$&"，通过ASCII编码存储后的样子是
十进制：97 98 99 49 50 51 44 46
二进制：01100001 01100010 01100011 00110001 00110010 00110011 00100100 00100110
在计算机中存储的样式就是，上面的二进制信息
ASCII码扩展问题
加上一些特殊的字符，127个肯定是无法满足的，ASCII码扩展到255个字符
注意这8个位，最高位是1开头的，取值范围128~255
例如：
128 10000000 € 欧盟符号
131 10000011 ƒ 拉丁小写字母f
255 11111111 ÿ
大小规则的定义：
常见ASCII码的大小规则：0~9<A~Z<a~z。
1）数字比字母要小。如 “7”<“F”；
2）数字0比数字9要小，并按0到9顺序递增。如 “3”<“8” ；
3）字母A比字母Z要小，并按A到Z顺序递增。如“A”<“Z” ；
4）同个字母的大写字母比小写字母要小32。如“A”<“a” 。
几个常见字母的ASCII码大小： “A”为65；“a”为97；“0”为 48
Unicode码
虽然ASCII码做了扩展，但是最多也就是256个字符，如果考虑到汉字，一个字节来表示字符肯定是不够的，这样就必须引入2个字节来表示一个汉字；
那么有没有一种编码，可以容纳所有的字符类型？
Unicode就是一个很大的集合，目前规模可容纳100多万个符号；
Unicode（统一码、万国码、单一码）是计算机科学领域里的一项业界标准，包括字符集、编码方案
Unicode本身是一个符号集，它只规定了符号的二进制代码，但是没有规定二进制代码如何存储，这样的话就导致了一个问题，一些字符是一个字节，两个字节，三个字节，甚至更多。
这样就带来了2个问题
1、如何区分Unicode和AscII编码，计算机是如何知道三个字节表示一个符号，而不是表示三个符号呢？
2、存储空间的浪费，Ascll编码一个字符占8位也就是一个字节，Unicode每个符号用4个，5个字节表示，对于每个英文字符前面必然有4个，5个字节，甚至更多个字节，这样给存储带来极大的浪费
UTF-8
UTF-8是一个非常好的编码方式，完美的对接了AscII码，同时也解决了Unicode的问题，需要说明的是UTF-8是Unicode编码方式的一种
可以用1-4个字符来表示一个字符，根据字符的不同变化不同的长度
编码规则如下：
1、对于单个字节的字符，第一位设为0，后面7位对应Unicode的码点，也就是0-127号符号，与ASCII完全相同，这也就是用UTF-8可以完美打开ASCII的编码。
2、对于N个字节来表示的字符（N>1），第一个字节的前N位都设为1，第N+1位设为0，剩余的N-1个字节的前两位都设位10，剩下的二进制位则使用这个字符的Unicode的码点填充。
针对第二条编码规则进一步做说明：
如果第一个字节的第一位是0，就说明这个字节对应一个字符
如果第一个字节的第一位是1，那么连续有多少个1（假设有N个1），就表示该字符占用了多少个字符，第N+1位是0，剩余的N-1个字节前两位都是10开头，剩下的二进制对应Unicode的码点填充（依次从后向前填充，多出来的位补零）
Unicode 二进制码点范围 UTF-8 二进制
1个字节范围
2个字节范围 110xx xxxx 10xx xxxx
3个字节范围 1110x xxxx 10xx xxxx 10xx xxxx
4个字节范围 1111 0xxx 10xx xxxx 10xx xxxx 10xx xxxx
例如："计"的 Unicode 码点是 0x8ba1（1000 1011 1010 0001）
对应的UTF-8编码模式是： 1110x xxxx 10xx xxxx 10xx xxxx ， 然后将0x8ba1依次从后向前填充
得到最终的UTF-8编码是： 1110 1000 1010 1110 1010 0001
例如："汉"的 Unicode 码点是 0x6c49（110 1100 0100 1001）
对应的UTF-8编码模式是： 1110x xxxx 10xx xxxx 10xx xxxx ， 然后将0x8ba1依次从后向前填充
得到最终的UTF-8编码是： 1110 0110 1011 0001 1000 1001
UTF-16
是UTF-16也是Unicode编码方式的一种，Unicode本身一个大的字典集合包含所有的字符集。
这么多的字符是分区定义的，每个区可以存放65536个字符（2个字节大小）称为一个"平面"，目前有17个平面，也就是说整个Unicode字符集的大小是2^21个
最前面的65536（0-2^16 -1）个字符，称为基本平面，剩余的字符都放到辅助平面
UTF-16编码介于UTF-32与UTF-8之间，同时结合了定长和变长两种编码方法的特征；
UTF-16的编码规则比较简单：基本平面的字符占2个字节，辅助平面字符占用4个字节，UTF-16编码长度要么是2个字节，要么是4个字节；
这样就带来了1个问题：
当遇到两个字节如何如何区分是一个字符还是与后面的两个字节当成一个字符？
这里用了一个很巧妙的地方，在基本平面内，1101 1000 0000 0000（55296）到 1101 1111 1111 1111（57343）是一个空段，用十六进制来表示（0xD800 到 0xDFFF），这些码点不对应任何的字符，这个空段用来映射辅助平面的字符
这段的空位，前半部分映射辅助平面的高位，后半部分映射辅助平面的地位，具体范围如下：
高位：1101 1000 0000 0000（55296 0xD800） 到 1101 1011 1111 1111（56319 0xDBFF）
低位：1101 1100 0000 0000（56320 0xDC00）到 1101 1111 1111 1111（57343 0xDFFF）
这就说明，一个辅助平面的字符，被拆分两个基本平面的字符表示
当遇到两个字节，发现他的码点在0xD800 到 0xDBFF 之间，就可以断定，紧跟在后面的两个字节码点应该在0xDC00 到 0xDFFF之间，这四个字节就必须放在一起解码
例如："宋" Unicode 0x5b8b（01011011 10001011），这个范围没有超过了基本平面的范围（2个字节的长度）
汉字"宋'的UTF-16的编码是：0x5b8b
例如："吉" Unicode 0x20BB7（101 1011 10001111），这个范围没有超过了基本平面的范围（2个字节的长度）
首先将0x20BB7 - 0x10000（去掉前2个字节），然后将其用20个二进制表示（不足前面补0）
得到0001000010 1110110111 20位二进制
前10位映射到0xD800-0xDBFF：填充到11011000 00000000得到11011000 01000010（0xD842）
后10位映射到0xDC00-0xDFFF：填充到11011100 00000000得到11011111 10110111（0xDFB7）
因此得到的汉字"宋'的UTF-16的编码是：0xD842 0xDFB7
UTF-16 辅助平面字符转换公式：// Math.floor 即对浮点数向下取整// c 是对应的Unicode码位// 0x400 1024 2^10次方H = Math.floor((c-0x10000) / 0x400) + 0xD800L = (c - 0x10000) % 0x400 + 0xDC00
Base64编解码
在进行Http传输的时候，为什么需要把Byte数组进行base64编码呢？
答案：Http协议是文本协议，不同于二进制协议，无法直接传输二进制
在数据或参数的参数过程中，经常遇到一些情况：使用全英文没有问题，一旦涉及到中文就乱码，还有一些网络上传输的字符并不是全可打印的，比如：二进制文件，图片等等，Base64就是解决了此问题，是基于可打印的字符来表示二进制的数据的一种方法
早期的一些传输协议，例如传输邮件的SMTP协议，只能传输可打印的ASCII字符，ASCII的范围是0-127，比如：当邮件传输图片资源的时候，某一个Byte的值是10111011（187）不属于ASCII码的范围，因此不支持传输，这个时候，Base64编码就应运而生了，他是用6位表示原来的8位，稍等下面会仔细说明。
Base64是一种用64个字符表示任意二进制数据的方法
Base64的原理很简单，其实就是64个字符["A","B","C","...Z","a","b","c","...z","0","...9","+","/"]
26个大小写字符，加上10个数字，以及"+"和"/"，一共64个字符
Base64编码1、3个字节一组，形成24位2、将24位分为4组，每组6位，每组前面增加003、形成4个字节，来表示3个字节Base64解码c：3个字节是一组，每个字节8位，也就是24位第一个字符：c << 16 & 0xFF （取得第一个8位）（取得第一个8位）第二个字符：c << 8 & 0xFF第三个字符：c & 0xFF
URL encoding
URL编码，也成为“百分号编码”，是将字符串以URL编码
编码原理：将需要转码的字符串转为16进制，从右到左，取4位（不足4位直接处理），每2位做一位，前面加上%
