破解索引】
基础前缀：?一.进制
1.进制的基本概念
进制即进位计数制，是利用固定的数学符号和统一的规则的带进位的计数方法。
任何一种进制都有一个基数，基数为X的进制称为X进制，表示每个数位上的数运算时都是逢X进一。
对于一个X进制的数，其具体数值由其中的每个数码和数码所在的数位决定。
整数部分从右往左(第一个数位记为1，增 ）的第m个数位具有的权重为X^（m-1）；
如：十进制整数1234
| 1234=1×10^3+2×10^2+3×10^1+4×10^0 |
| 0.5678=5×10^-1+5×10^-2+6×10^-3+8×10^-4 |
720.514=7×8^2 + 2×8^1 +0×8^0 +4×8^-1+ 0×8^-2+ 7×8^-3……
2.进制转化的基本方法
非十进制转十进制
——
将非十进制数转成十进制数，只要将每个数位的数乘以该数位的权重，最后相加即可（每个数位的加权和）。
十进制转非十进制
——
将十进制数转成 X进制数，需要对整数部分和小数部分分别转换。
整数：连除取余，直到0
例如，将十进制数 50 转成二进制：
50÷2=25 余 0
25÷2=12 余 1
12÷2=6 余 0
6÷2=3 余 0
3÷2=1 余 1
1÷2=0 余 1
反向遍历每次的余数，依次是 1,1,0,0,1,0
因此十进制数 5050 转成二进制数是110010 (2)
小数：连乘取整，直到0
例如，将十进制数 0.6875 转成二进制：
0.6875×2=1.375 整 1
0.375×2=0.75 整 0
0.75×2=1.5 整 1
0.5×2=1 整 1
正序遍历每次的整数部分，依次是 1,0,1,1
，因此十进制数 0.6875 转成二进制数是0.1011(2)
注意：需要注意的是，在一种进制下的有限小数，转成另一种进制之后可能变成无限循环小数，例如上面的【 720.514 转八进制】
非十进制转非十进制
——
如果需要在两个不同的非十进制之间转换，常规的思路是先转成十进制数，再转成目标进制数。在一些特殊情况下，也可以不经过十进制，直接进行转换。
例如，将二进制数转成八进制数或十六进制数，以及将八进制数或十六进制数转成二进制数，都不需要经过十进制。一位八进制数可以表示成三位二进制数，一位十六进制数可以表示成四位二进制数。
如：101110010（2），按三位一组分：101|110|010,转成八进制数562(8)
?二.计算机中整数如何表示
《1》——
计算机中整数统统用二进制表示，只有两个数码0，1
一位二进制的取值共有2个，k位二进制的取值共有2^k个
4 字节数，即32 位二进制数，可能取值有 2^32个；
8 字节数，即 64 位二进制数，可能取值有 2^64个
16 字节数，即 128 位二进制数，可能取值有 2^128个
《2》——
计算机中的数据类型包括有符号类型和无符号类型，有符号类型的整数称为有符号整数，无符号类型的整数称为无符号整数。
（每个数据类型都有对应的无符号、有符号类型两种，
如：int ,unsigned int等，其字节数一致。）
区别：
——
1、有符号整数中，最高位用于表示符号，因此最高位又称符号位。当最高位是 0时表示 0 或正整数，当最高位是 1时表示负整数。除了最高位以外的数位用于表示数字的大小。
2、无符号整数中，所有的数位都用于表示数字的大小，因此无符号整数不存在负数。
以int/unsigned int，4字节数为例.4字节数包含32位二进制数。
对于4字节数的有符号数（int），
当最高位是 0 时,4字节数的取值范围是 【0~2147483647(2^31-1)】
当最高位是1时，4字节数的取值范围是 【-2147483648(-2^31) ~ - 1 】
对于4字节数的无符号数（unsigned int）
无符号位，所以其取值范围为：【0~4294967295（2^32-1）】
《总结》：
1.有符号整数的取值范围包括负整数、零与正整数，
无符号整数的取值范围只包括零与正整数，不包括负整数；
2.在位数相同的情况下，有符号整数可以表示的最大值比无符号整数小了一半；
3.对于二进制位为k的整数，有符号整数的取值范围是 -2^(k-1)~2^(k?1)-1
无符号整数的取值范围是 0 到 2^k .
?三.原码、补码和反码
《1》机器数和真值
概念：一个数在计算机中的二进制表示形式称为这个数的机器数。机器数是有符号数，机器数的最高位是符号位，0表示 0 或正数，1 表示负数。
例如：
以 8 位二进制数为例。十进制数 +10 转换成二进制数是 00001010，十进制数?10 转换成二进制数是 10001010。这里的 00001010和 10001010 就是机器数。
因为机器数的最高位是符号位，所以机器数的形式值不一定等于真正数值。例如 10001010 的形式值是 138，真正数值是 -10，形式值和真正数值是不同的。为了加以区分，将机器数的真正数值称为机器数的真值(将符号位变为±号）。
《2.原码》
原码是机器数的符号位加上机器数的真值的绝对值，最高位是符号位，其余位表示数值。
继续以8位二进制数：
如：+10 00001010
如：-10 10001010
原码是最容易理解的方式
《3.反码》
反码在原码的基础上得到，0 和正数的反码与原码相同，负数的反码是将原码的除了符号位之外的每一位取反，取反即为将 0 变成 1 或将 1 变成 0。
继续以8位二进制数：
+10 的原码是 00001010，反码是 00001010；
-10 的原码是 10001010，反码是 11110101。
反码只是在原码的基础上对负数将符号位外的各位取反，往往不够直观；对负数，需要先转化成原码，再算。
《4.补码》
补码在反码的基础上得到。0 和正数的补码与原码、反码相同，负数的补码是在反码的基础上加 1 得到。
继续以8位二进制数：
+10 的原码是 00001010，反码是 00001010，补码是 00001010；
?10 的原码是 10001010，反码是 11110101，补码是 11110110。
对于负数，补码的表示方式非常不直观，通常需要转换成原码才能计算其数值。（对人不友好，但对计算机友好）
诡异的0??
1、同时存在 +0（即符号位和其余位都是0）和
?0（即符号位是1，其余位都是0）的表示，
虽然可以认为 +0 和?0 是同一个数，但是0带符号是没有意义的，
而且会导致有两个不同的原码都对应 0；
用原码进行减法运算，会导致错误的结果。
2、反码的引入，解决了原码的减法运算结果错误的问题，
但是仍然没有解决同时存在 +0 和 ?0 的问题
3、补码的引入则同时解决了减法运算错误和同时存在 +0和 -0的问题，
而且可以多表示一个最小值。在补码表示法中，不存在 -0的情况。
以 8位二进制数为例，0的补码是 00000000，10000000 表示的是 -128，
-128没有原码和反码的表示（8位二进制数的原码和反码能表示的最小值是 -127）。
由此可见，补码不仅解决了原码和反码的问题，还可以多表示一个最小值。
综上：补码是最适合计算机的数字表示，我们在位运算过程中，都是用的补码。
?
------🎉 🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈🎈 华丽分割线
位运算算法：?开始?
- 概述：计算机采用的是二进制，二进制包括两个数码：0,1。在计算机的底层，一切运算都是基于位运算实现的。
- 即我们平时的加减乘除最后都能按位运算实现，另外由于位运算最接近底层，所以我们位运算操作的速度往往比+/-*快很多。
- 位运算共有 6 种，分别是：与、或、异或、取反、左移和右移，其中左移和右移统称移位运算，移位运算又分为算术移位和逻辑移位。上述位运算中，只有取反是一元运算，其余的都是二元运算。
- 采用位运算，一方面可以大大加快我们的计算速度，另一方面，由于位运算本身的特性，它对于求解某些特殊题目具有非常大的优势（如：汉明距离、求数组中只出现一次的数字、判断是否为2的幂等等）
?🛫基本介绍 与、或、异或、取反、左移、右移（&、|、^、~、>>、<<）
1.与运算的符号是 &，运算规则是：对于每个二进制位，当两个数对应的位都为 1时，结果才为 1，否则结果为 0。
| 0 | 0 | 0 |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
2。或运算的符号是 |，运算规则是：对于每个二进制位，当两个数对应的位都为 0时，结果才为 0，否则结果为 1。
| 0 | 0 | 0 |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
3.异或运算的符号是 ⊕（在代码中用∧ 表示异或），运算规则是：对于每个二进制位，当两个数对应的位相同时，结果为0，否则结果为 1。
| 0 | 0 | 1 |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
4.取反运算的符号是 ～，运算规则是：对一个数的每个二进制位进行取反操作，0变成 1，1 变成 0。
| 0 | ~ | 1 |
|---|---|---|
| 1 | ~ | 0 |
5|6.移位运算，>>,<<
移位运算按照移位方向分类可以分成左移和右移，按照是否带符号分类可以分成算术移位和逻辑移位。
1@ 左移运算的符号是 <<。左移运算时,将全部二进制位向左移动若干位高位丢弃，低位补 0。对于左移运算,算术移位和逻辑移位是相同的。
2 @右移运算的符号是 >>。右移运算时，将全部二进制位向右移动若干位，低位丢弃，高位的补位由算术移位或逻辑移位决定：
算术右移时，高位补最高位；
逻辑右移时，高位补 0。
示例：下列表示：有符号的8位二进制表示
数字 二进制表示 数字 二进制表示
29 00011101 >>3= -24 11101000（补码，化成原码为：10011000）
-50 11001110 <<2= 51 00110011
（可见，移位操作使用时，可能会改变符号，要小心谨慎，我们常用移位代替*2、/2但稍不留心，就可能出现各种各样的错误）
注：对于C/C++ 而言，对于有符号类型，右移运算为算术右移；对于无符号类型，右移运算为逻辑右移。
对于JAVA，算术右移的符号是 >>，逻辑右移的符号是 >>>（因为JAVA中的数均为有符号类型）。
?🛫基本介绍 ：位运算性质一览表
幂等律：a & a=a，a | a=a （注意异或不满足幂等律）；
交换律：a & b = b & a ，a | b = b | a，a ^ b = b ^ a
结合律：(a & b) & c = a & (b & c)，(a | b) | c = a | (b | c)
(a^b)^c=a^(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 & 0 = 0,a &(-1) = a，a & (～a)=0；
或运算性质：a | 0 = a, a|(～a)=?1；
异或运算性质：a^0=a,a^a=0
其他：X:a&(a-1)相当于将a的二进制表示的最后一个1变成0
Y：a&(-a)相当于将a的二进制表示的最后一个1保留，其前面的1都变为0
位运算奇巧：?超越🌀
💥 1.判断非负数的奇偶
奇数&1=1，因为奇数最后一位均为1
偶数&1=0，因为偶数最后一位均为0
void jd(int n){
if(!(n&1))cout<<"n为偶数"<<endl;
if(n&1)cout<<"n为奇数"<<endl;
}
💥 2.对2^k快速取余
记非负数为n,
则，n%2=n&1
n%4=n&3
……
n%2^k =n&(2^k-1)
💥 3.快速取得某数二进制表示的后n位 或 消除后n位
取后n位：
x&(0b11……1），只留下末n位，其余位去掉（都变为0）
这里n个1,0b说明我们使用二进制表示
消除后n位：
x&(0b11……000），去掉末n位都为0，前面的位保留
这里n个1,0b说明我们使用二进制表示
💥 4.快速判断2的幂
class Solution {
public:
bool isPowerOfTwo(int n) {
if(n<=0)return false;
return !(n&(n-1));//原理：如性质，n&(n-1)可以将n二进制表示下的最后一个1去掉
}//而凡是2的幂的数，都只有一个0，即n&(n-1)==0
};
💥 5用或，设置标记位/用且，置空标记位
标记：
x|=ob1000……，1在第n位，这样可以将x二进制表示下的第n位标记为1
置空：
x & 0b1111111110……1111);
32位二进制数，唯一的零在第n位，如此，将x二进制表示下的第n为置空为0
💥 6.快速乘以/除以2……
1、左移运算对应乘法运算。将一个数左移 k 位，等价于将这个数乘以 2^k
2、算术右移运算对应除法运算。将一个数右移 k位相当于将这个数除以 2^k，结果向下取整。
注意：
1.对于任意整数，乘法运算都可以用左移运算实现，但是需要注意溢出的情况.如：32位进制表示下，INT_MAX右移1位即溢出
2.对于0或正数，将一个数（算术）右移 k 位，和将这个数除以 2^k等价；但与负数不等，如：（-50）>>2=-13,(-50)/4=-12
💥 7.交换变量
对于两个数a,b(可以为负数），可以用位运算快速表示交换变量。
void swap(int&a,int& b){
a^=b;
b^=a;
a^=b; //结合异或运算的性质
}
💥 8.求解只出现一次的数字
题目描述：
给定一个非空整数数组，除了某个元素只出现奇数次以外，其余每个元素均出现偶数次。找出那个只出现了奇数次的元素。
用异或运算的性质：
1.两个相同的数异或，得零
2.一个数异或零，得它本身
一次遍历求解
int singleNumber(vector<int>& nums) {
int jie=0;
for(int i:nums)jie^=i;
return jie;
}
💥 9.Brian Kernighan 算法(快速去掉二进制表示的最后一位）
n&(n-1)
快速将n二进制表示的最后一位去掉，同上性质
💥💥💥必知：10.状态压缩💥💥💥
主要思想：
状态压缩，顾名思义就是将多个值的状态压缩成一个数字。具体而言，如果有 n 个值，每个值有 2 种可能的状态，则状态总数有 2^n
个，可以用一个 n 位二进制数记录全部 n 个状态的取值。
例如，一共有 n 个物品，每个物品分别对应一个值，即该物品是拿还是不拿，可以用一个 n 位二进制数表示每个物品的值。当 n=5 时，假设二进制数从最低位到最高位依次表示第 1 个物品到第 5 个物品是拿还是不拿，1 表示拿，0 表示不拿，则 01011 (2)表示拿了第 1 个、第 2 个和第 4 个物品，不拿第 3 个和第 5 个物品。
下面是一道经典的题目（状态压缩的简应用）
例题：剑指 Offer II 005. 单词长度的最大乘积
分析：本题的关键是如何判断两个单词是否含有相同字符。
很容易想到遍历字符串，依次计数。但很明显，这样的时间复杂度太高了。加上今天学了按位或，很容易想到位掩码。用位掩码模拟字符串中各字母的出现情况。这里其实是一种状态压缩的方法。
t=00000000000000000000000000//26位
1<<(‘a’-‘a’)=1 通过t|= //有’a’出现，t的第一位更为1
1<<(‘b’-‘a’)=1<<1=10 //有’b’出现，t的第二位更为1
… //这样以来，我们只要根据两字符串位掩码的按位与情况判断即可。
//如：“abc”=000111
// “efc”=110100
class Solution {
public:
int maxProduct(vector<string>& words) {
int n=words.size();
vector<int>memo;
for(int i=0;i<n;i++){
int t=0;
for(int j=0;j<words[i].size();j++){
t|=(1<<(words[i][j]-'a'));
} //状态储存
memo.emplace_back(t); //创建备忘录，记录各字符串的位掩码
}
int jie=0;
for(int i=0;i<words.size()-1;i++){
for(int j=i+1;j<words.size();j++){
int tmp=words[i].size()*words[j].size();
if(!(memo[i]&memo[j]))jie=max(jie,tmp);
}
}
return jie;
}
};
适用情景：
如果每个值都有 2 种状态，n 个值对应的状态总数就是 2^n
，因此只有当 n 较小时，才能适用状态压缩。一般而言，当 n≤20 时，可以考虑状态压缩。
补充：状态压缩与动态规划结合常有奇效；这里还没找到例子
………………
总结：
位运算是很奇妙的算法，常常可用位运算达到奇巧。同时学习位运算对计算机底层理解大有帮助。
解题之路漫漫，但，追求是不能轻易背弃的。（￣︶￣）↗
在下，见习解题家，请多多指教。
参考：《leetbook》《算法零基础100讲》、解题者的笔记