位运算基础及实战要点

#学习笔记

第7周-第16课 | 位运算

1. 位运算基础及实战要点

• 1. 位运算符
• 2. 算数位移与逻辑位移
• 3. 位运算的应用
• 为什么需要位运算以及位运算它本质上是什么
• 位运算的由来其实很简单，就是因为在计算机里面数字的表示形式不是人类常用的熟悉的十进制。人们为什么熟悉十进制，是因为历史的原因以及人类的大脑构造，觉得十进制更加好用，为什么呢？因为我们的手指是有十个，所以在古代人们计数的时候，用手指更好数。那么计算机的话因为大部分都是高电位和低电位，所以就010101。它本身任何的一个整型或者是十进制的数，在计算机里面的数字表示方式和存储形式都是二进制，大一的时候学计算机原理的时候讲过。如果给你一个十进制的数要把它转换成二进制应该怎么转换。给你任何一个十进制数，怎么把它转换成二进制数。或者是任何一个二进制数怎么把它转回十进制数。
• 要求二进制的表示形式就不断地除以2，把模出来的余数写在后面，一步一步写下来之后，最开始除以2得到的余数是它的最低位，越到后面说明位数越高，所以把所有的余数从下到上把它列出来，就等于它的二进制位了。
• 如何把二进制转换为十进制呢？从最底下的余数开始，按顺加上余数的二次方得到十进制数。
• 位运算符
• 位运算经常会有左移和右移，他们分别有逻辑左移和标准的计算机的左移。
• 计算机里面的左移是什么？
• 比如0011，把它左移一位，那就是把这个数字，整串二进制符号往左移一位。同时，空出来的二进制位补0。如果要左移的0一出去之后位就没有了，不管这个位是0是1移出去之后就没有了。右移同理可得，就把这一串数字往右移一位就行了，这边新的位数始终是补0的，老的位数一出去就去掉。
• 在计算机里面的话，一般来说老式的计算机是32位的，新的计算机，就比如现在买的笔记本，基本上都是64位的，所以它的一个整型其实就是有64个二进制位表示。
• 四种常用的位运算符；
• 1. | 按位或运算：或必须是两个二进制数进行操作，或指的是只要有一个二进制位是1，那么或出来的结果就是1。
• 2. & 按位与运算：与或相反，只要有一个二进制位是0，那么与出来就是0。
• 3. ~ 按位去反：把0011变成1100。
• 4. ^ 按位异或：表示如果相异的话就是1，如果相同的话就是0。
• XOR-异或
• 异或：相同的为0，不同的为1。也可以用“不进位加法”来理解。
• 异或操作的一些特点：（稍微高阶一点的，记住就好了）
• x ^ 0 = x：只要x和0相同的，那就是0，不同的就是1。那x异或0就是x本身。
• x ^ 1s = ~x //注意1s = ~0：x异或全1，这里的1s指的是全1，全1的话就是0取反，这里的话就是全0。x异或全0就等于x，x异或全1就等于x取反，就是把x里面所有的位0变1，1变成0。
• x ^ (~x) = 1s：那么同理x如果异或x取反的话，1变成0了。那么同理x如果异或x取反的话，x取反的话就是所有的二进制位0变成了1，1变成了0。它和x的话，所有的二进制位都是不同的，那么异出来的结果就是全1。
• x ^ x = 0：x异或x它们的所有二进制位，这两者所有的二进制位都是相同的，那么相同就是0。
• c = a ^ a => a ^ c = b ,b ^ c = a //交换两个数
• a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c //associative
• 同时可以用来交换两个数，以及有所谓的结合法，后面两者用得比较少。了解下即可。
• 经常我们在操作一个数它的位运算的时候，需要对这个数某几个二进制位进行置1的操作或者是清零的操作，或者是将它的指定的二进制位挪动，那么我们在程序里面经常会用到这么几个事情。
• 指定位置的位运算
• 1. 将x最右边的n位清零：x & (~0 << n)，就是把要做的一个事情，把0取反了之后就全部都是1，全部都是1之后向左位移了n位之后。，变成111111…，最后的话有n个0。和x与在一起指的是，将x的右边n位全部清零，只留下最左边的那些高位。右边低位的n全部都是清零的。
• 2. 获取x的第n位值（0或者1）：（x >> n） & 1，就是把x先右移n次，那么x第n位就变成最后一位了，然后再与上一个1，就得到了第n位是到底是0还是1。
• 3. 获取x的第n位的幂值：x & (1 << (n - 1))，同理可得，就是把一个1往左移移到高位去，然后和x与一下。
• 4. 仅将第n位置为1：x | (1 << n)。
• 5. 仅将第n位置为0：x & (~ (1 << n))。
• 6. 将x最高位至第n为（含）清零：x & ((1 << n ) - 1)。
• 7. 将第n位至第0位（含）清零：x & (~ (1 << (n + 1) ) - 1)。
• 以上都是同理可得的，如果是第一次见的话，要好好想一想，然后在纸上把他们画出来。
• 实战位运算要点 （面试的时候位运算讲的最多的，不管是在布隆过滤器、还是在N皇后问题讲的最多的，用的最多的就是这样一些位运算的技巧）
• 判断奇偶：
• x % 2 == 1 -> (x & 1) == 1， x % 2 == 0 -> (x & 1) == 0
• 经常会用的一个操作就是x模上2，到底是否等于1。也就是x除以的余数到底是0还是1，这个是数学上或者是从小到大学习数学的时候它的定义。但在计算机领域，更快捷的一个操作就是x与1，直接用x与1看看它是否等于1就行了也就是判断它的二进制位最后一位到底是0还是1，是0的话就说明是偶数，是1的话就表示是奇数。同时的话位运算比模操作要快不少，所以以后判断奇偶性，能用位运算就用位运算，那么始终用这个来写就行了。当然用Java或者是其它高级语言，用模的形式，它的编译器足够智能，肯定也是转换成二进制的，它不会傻傻地去模的。
• x >> 1 -> x / 2 即：x = x / 2; -> x = x >> 1;
• 相当于把它的最后一位二进制位清空，然后整个树再往右挪一步，那就相当于它除了2，也就是x除2这个操作，就可以用x右移一位来表示，所以以后写代码x = x / 2，就直接x = x 向右移一位是一样的，而且这样的话更快。
• mid = (left + right) / 2; -> mid = (left + right) >> 1;
• 在做二分查找的话，经常用的一个操作就是，左边界再加右边界再除以2。就可以用左边界再加右边界加在一起，右移一位来表示。
• x = x & (x - 1)，表示清零最低位的1，在纸上自己画下，就直接比如说x = 01101000，然后把x - 1 列出来到底是多少，然后再把两者与一下。这个时候会发现操作做的一件事情就是把x的最低位的二进制1给去掉了。
• x & -x => 得到最低位的1所表示的整个数。
• x & ~x => 0。

第7周-第17课 | 布隆过滤器和LRU缓存

1. 布隆过滤器的实现及应用

• 两个比较高级的数据结构，而且它们在面试中，以及在工业级的应用上面都较为广泛。
• 布隆过滤器 Bloom Filter
• HashTable + 拉链存储重复元素
• 布隆过滤器它是和哈希表类似，很多时候我们经常把它去和哈希表进行对比。哈希表如果有重复的元素，采用拉链存储法的话，可以看到本身任何一个元素进来，会经过一个哈希函数。
• 假设进来的就是一个String，它经过一个哈希函数之后，就映射到一个整数的下标位置，叫整数的index。比如说Lisa Smith的字符串就映射到001，然后存在001这位置，然后她的电话就是123456。当两个字符串被哈希到了同一个位置，那么所采用的解决冲突的办法就是在这个位置开一个链表，把多个元素都存在相同的位置的链表处，往后面不断积累，它就是哈希表一种存储形式。
• 这里发现一个特点，就是对于哈希表，它不仅有哈希函数来得到这么一个index值，且它会把整个要存的元素全部都放在哈希表里面去。这是一个没有误差的数据结构，且有多少的元素，每个元素有多大，那么所有的这些元素需要占的内存空间，在哈希表里面都要找相应的内存的大小给存进来。
• 在很多时候在工业级应用的时候发现我们并不需要存所有的元素本身，而只需要存一个信息，就是这个元素在这个表里面到底是有还是没有。
• 在这种情况下的话，如果只要查询有还是没有的时候，这个时候就需要一种更高效的数据结构。这个更高效的数据结构可以导致的一个结果，就是这里面有很多元素要存，但是这个表所需要的内存空间很少，同时我们不需要把元素本身，就比如不要把它String这些东西全部存起来，只需要说这个东西到底是有还是没有。
• 这种数据结构是怎么设计出来的？一个叫Bloom Filter应运而生。
• Bloom Filter vs Hash Table
• 布隆过滤器它是一个很长的二进制向量 和 一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。
• 所以它和哈希表一个最大的区别：
• 哈希表不仅可以判断它是否在集合中，也就是说哈希表的话就是map，我们在用map的时候，不仅可以判断它是否在其中，而且可以再存很多冗余的信息，比如说可以存他的电话号码存在这个哈希表当中，所以哈希表的话不止是判断是否在集合，同时还可以存元素本身和元素对应的各种额外信息。
• 布隆过滤器的话只是用于检索一个元素是否在还是不在，它只能存在和不在的信息，而不能存其他额外的信息。
• 它的优点就是空间效率和查询时间都远远高于一般算法，为什么能达到这个，它是用了二进制向量来表示，所以它很节省空间。另外一个方面它是一种模糊的查询方式。
• 它的缺点就是有一定的误识别率和删除困难这个两个。
• 布隆过滤器的整个原理
• 对于任何一个元素，假设要存三个元素{x,y,z}依次存进来，这里的x,y,z不是同事往里面灌，是一个一个依次往里面灌。每一个元素它会分配到一系列的二进制位中。假设x它就分配到三个二进制位，那么x插入到布隆过滤器就表示把x对应的这三个位置置为1就可以了，那么接下来y插入进来，那么y根据它的哈希函数，就分为另外三个对应的二进制位也置为1，同理z的话也分成三个就置为1。这个二进制的数组就用来表示所有的已经存入的xyz，是否已经在索引里面了。这个时候重新给你一个元素x，就会始终对应于这个三个二进制位，那么去这个表里面查，就查到这三个皆为1，所以话可以认为x是存在的。
• 如有一个陌生的元素w进来之后，它把它分配给通过布隆过滤器的二进制索引的函数，w就也会得到三个二进制位，这三个二进制位是110，有一个二进制位为0说明什么呢？说明w未在索引里面。这个时候会发现一个特点，如果一个元素它所对应的二进制位，只要有一个为0，就说明这个元素不在布隆过滤器的索引里面，且我们是可以肯定它不在的。
• 但是当一个新的元素比如q，它刚好分配的三个二进制位都为1的话，我们不一定能说是在的。
• 结论：当布隆过滤器把元素全部都插入完了之后，对于测试元素，也就是新来的一个元素，要来验证它是否存在的话，当它验证这个元素所对应的二进制位是1的时候，我们只能说它可能存在在布隆过滤器里面。但是当这个元素所对应的二进制位只要有一个不为1，那么我们可以百分之一百肯定它不在。
• 也就是说千言万语汇成一句话，这个元素去布隆过滤器里面查，如果查到它不在的话，那么它肯定就是不在的，如果查这个元素查到布隆过滤器里面它的二进制位都是1，为存在的一个状态的话，那么我们只能说它可能存在的。
• 那么当这种元素在里面查到的时候，那么接下来要怎么判断它到底是否存在呢？布隆过滤器只是放在最外面来当一个缓存使用的，也就是说来当一个很快的判断标准使的，当这种情况的元素查到布隆过滤器里面是存在的，那么这个元素就会继续放在数据库里面去查，到时候的话会查出来这个元素是不存在的。如果在布隆过滤器查到这个元素不存在，就不用在放在数据库里面继续查了，它肯定是不存在了，这样就节省下来访问数据库的时间了，而且可以肯定这个元素肯定也未添加进数据库里面。
• 这个时候会发现布隆过滤器，只是挡在一台机器前面的快速查询的缓存，真真要确定元素一定存在的话，它必须在访问这个机器里面的一个完整的存储数据结构，在工业上应用的话，一般来说也就是数据库了。
• 现实中的应用案例
• 1. 比特币网路，因为比特币是分布式系统，所以在分布式系统中，一个地址是否在这个结点里面，以及这个tansaction是否在node里面，经常会要用到所谓的布隆过滤器来进行快速查询。
• 2. 分布式系统（Map-Reduce、Hadoop、search engine之类的），以及Google用得很多这样的，比如说搜索引擎经常做的很多事情，就是把大量的网页信息，还有图片信息都存在它的整个服务器里面。那么一般来说，不同的网页是存在不同的集群里面的，当在search的时候查到一个东西之后，它就会根据索引就会知道它应该是在这个集群，它就先在集群的布隆过滤器里面去查一下看是否存在。如果存在的话它再去集群的DB里面进行访问，如果不存在的话那就直接略过了。所以在大型分布式系统里面，很多地在使用布隆过滤器。
• 3. Redis缓存
• 4. 垃圾邮件，就是来了一个邮件或者一个评论它到底是不是比如说涉黄的，涉黑的以及不正当的言论之类的，它也可以过一个布隆过滤器，然后很快地来判断，不是话就不是，是的话它再去DB里面查一下哪些涉黄涉黑的规则是否相符合。
• 科普的文章：
• 用程序是如何实现一个简单的布隆过滤器的
• Python实现、Java实现。Google 搜索 语言 + bloom filter + implementation，然后就可以得到相应的代码了。

2. LRU Cache的实现、应用和题解

第7周-第18课 | 排序算法

1. 初级排序和高级排序的实现和特性

• 排序算法
• 1. 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 在高级语言里面，直接调系统自带的排序函数，如果是Java的话可以穿进去一个叫comparator，或者是其他语言的话叫做cmp之类的函数。也就是说她比较的元素不一定非的是实数或者是int之类的类型，它可以是任何结构体或者是类的对象，只要给他传一个可以比较两个object之间的前后关系，它都可以帮你排序出来。像这种通过比较来决定元素间的相对次序，那么时间复杂度不能突破logn，在数学上可以被证明了。而大部分在我们要用到的排序都是这种比较类排序。
• 2. 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
• 指的是不用比较两个元素之间互相的关系，这种一般是对于整型的元素来做，也就是说在这里可以用线性时间直接完成。但是它的缺点是，一般来说只能用于整型相关的数据类型，也就是对于一些比如字符串的排序或者是对象之间的排序就无能为力了。同时它一般要辅助用额外的内存空间。
• 比较类排序：
• 1. 交换排序：冒泡排序、快速排序。
• 2. 插入排序：简单插入排序、希尔排序
• 3. 选择排序：简单选择排序、堆排序
• 4. 归并排序：二路归并排序、多路归并排序
• 非比较类排序：（基本上就是放在一个数组里面来统计每个数出现的次序）
• 1. 计数排序
• 2. 桶排序
• 3. 基数排序
• 从优先级来分析，最重要的排序肯定是比较类的排序，因为它才是范型的，工业变成用得最多的。而面试来说或者是说真正在去一个公司面试官考你技术能力，他考的肯定是nlogn的排序，也就是从优先级来讲重点花时间和精力看nlogn的排序，也就三个，堆排序、快速排序、归并排序。n平方的排序尽量快速解决，以了解为主，就算程序写的不好或者没法手写也没有什么太大的问题。关键是能够手写nlogn的三个排序，同时把这三个排序的原理弄得很明白。特别是比如说快速排序，它用到了分治的思想，归并排序也是，而且归并排序可以用在其他的解决一些算法面试题上面一定要了解。后面的非比较类排序也了解为主。
• 初级排序 - O(n^2) 面试之前要看一遍
• 1. 选择排序（Selection Sort）：每次找最小值，然后放到待排序数组的起始位置。
• 首先整个数组扫描一遍，取得它的数组的最小值，这个用最简单的办法就是0(n)的时间复杂度可以解决，把最小值放到最前面第一个位置去，然后接下来把剩余的数组也就是n-1个元素的数组也取得最小值放在第二个位置，然后n-2的数组去最小值放在第三个位置，这么每次往前挪。
• 2. 插入排序（Insertion Sort）：从前到后逐步构建有序序列；对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
• 插入排序的思想原理和前者其实差不多，只不过它顺序有点不一样。指的是假设前面的数组已经排好序了，那么对于后面的未排序的元素，找到它应该插在前面有序数组的什么位置，然后就插在相应的数组里面去，保持牵绊部分的子数组是有序的，所以叫做插入排序。用插入排序最大的一个问题，虽然可以二分查找，查找出来它相应要到的位置，但是因为这个是数组，所以要把相应的元素换到它所属于的下标，就会牵扯到所有的元素挪动，挪动本身就带来了在内存循环里面还是需要0(n)的时间复杂度，那么外层还有一个循环，总共它的训话的时间复杂度就是n平方。 会发现，它有很多的操作都浪费在了元素之间互相挪动这么一个地方。
• 3. 冒泡排序（Bubble Sort）：嵌套循环，每次查看相邻的元素如果逆序，则交换。
• 基本上是作为在大学里面讲的第一个就是冒泡排序，但是在实际中基本上从来不用，冒泡排序是两层嵌套循环，一层循环肯定不能解决问题，然后再最里面的循环的时候，每次查看相邻元素是否逆序，如果逆序的话则交换，那么在数学上可以证明。思考下写了两层嵌套循环之后，且每次查看相邻元素如果逆序的话再交换，那么经过n平方次的查看之后，所有的元素就肯定两两之间没有逆序了，都是从小到大或者从大到小排好了。冒泡排序关键的一点就是程序相对来说更好写一点，但是它逻辑上其实思考来根本没有选择排序让人觉得容易了解。选择排序就是每次找最小值放在最前面，每次再找其余元素的最小值放在第二个，再找其余元素放在第三。冒泡排序就是写两层嵌套的循环在里面，只要看到相邻元素是逆序的那则交换。动画经过第一次排序还是乱序的，这也是为什么冒泡排序最开始的话并不好思考，就是说这样难道就真的有序了吗。但是当它循环一层，最大的元素肯定是在最后面了，所以可以认为冒泡排序和选择排序它的顺序是相逆的，也就是说经过一层循环最大的会被放在最后面，因为最大的元素每次都会被交换，然后让最大的元素被冒泡出来，
• 这三者之间其实没有一个非常大的区别，三者的话其实就是异曲同工的原理。后续可以先看下模板程序，然后因为它本身就是最基础的编程，就直接把这几个排序用自己熟悉的语言手写一下。这些也算内功的一部分，也需要勤加练习，看起来逻辑上是简单的，但是程序要写的简洁，比如在多少行内写完还是要花点功夫的。
• 高级排序 - O(N*LogN) 要花时间和精力重点去了解，优先级是最高的
• 快速排序（Quick Sort）:数组取标杆pivot ，将小元素放在pivot左边，大元素放在右侧，然后依次对左边和右边的子数组继续快排；以达到整个序列有序。
• 快排是任何高级程序它的标准排序库里面用得最多的，它基于什么思想呢？第一个思想是分治，要让时间复杂度从n平方降下来，降到nlogn，那么分治毫无疑问就是要考虑的一个问题。排序在一遍一遍挪动的时候，其实应该有一些附加的信息在这个数组里面，所以不需要每次重复做一些劳动力的事情。
• 快排基于的一个思想也就是说在数组取一个标杆把它定位pivot下标，在数组里面pivot位置可以随机任何选的，一般来说可以选在中间，也可以选在最左边或者最右边，其实没有什么太大的区别。然后选定pivot的下标了之后，将小于pivot的所有的元素都放在pivot左侧，将大于pivot元素都放在pivot右侧，然后会达到一个效果就是至少是pivot的左侧的所有元素都是小于pivot右侧所有元素的。基于这个原因，只要一次把左侧的子数组进行排序和右侧的子数组进行排序，那么保证左右两侧的子数组都是有序的状态，那么整个序列就可以达到有序的状态了，也就是说去了一个pivot标杆把小的元素都移到pivot左侧，把大的元素都移到右侧，然后依次对左右侧的子数组进行快排，进行递归调用排序的调用，这样的话就可以达到整个数组是一个有序的状态。那么根据递归的时间复杂度一个主定理，通过主定理可以证明它的时间复杂度是nlogn的。
• 快排代码：特别考编程基本功，如果对于内存可以额外申请一个新的内容的话那反而简单，直接随便挑一个pivot位置，然后统计一下，只要比这个小的那么就放在新的数组的左边，只要比这个大就放在心的数组的右边。但是一般说来需要就直接在这个数组里面互相调换位置，也就是不申请新的内存空间，不申请新的数组，那么就要做一些技术处理或者就是写的程序就相对巧妙了。
• 归并排序（Merge Sort）- 分治
• 1. 把长度为n的输入序列分成两个长度为n / 2的子序列。
• 这里的分只要从中间劈开就行了，不需要做任何交换元素的操作。
• 2. 对这两个子序列分别采用归并排序。
• 分别调用了之后就可以保证左边的子序列和右边的子序列，在自己的片段区间里面是有序的。
• 3. 将两个排序好的子序列合并成一个最终的排序序列。
• 归并排序平时用的也挺多，它本身的一个原理指的是和快排刚好相反，快排就是拿到一个pivot的位置，这个可以随机选，然后将所有小于pivot元素移到左边去，大于pivot的移到右边去，且分别对左右侧再进行递归调用快排。归并排序可以认为是快排的逆向操作，这个逆的话从逻辑上大体的也并不是百分百准确。它做的一件事情是它先把这个数组一分为二，然后分别假设左边和右边都调了排序排好了之后，那么再把左右排好序的两个子数组合并成一个。
• 归并排序代码
• 试着去写一下，给你一个数组，它的两半部分全部都是排好序的，你怎么把它合并起来。或者可以想象为给你两个数组，这两个数组也是排好序的，怎么把它合起来。这种程序的题目，它逻辑相对来说比较简单，但是对基础编程代码工地其实要求很高。把这种归并，也就是两个数组有序怎么合在一起当成一段代码模板，把它记在脑子里面，同时能够灵活运用，这是提高最基础的内功很重要的一个部分。当你把这段代码可以脱口而出的话，在白板上给面试官写全的话，那么其实你整个编程的功底面试官肯定会刮目相看的。
• 总结：
• 归并和快排具有相似性，但步骤顺序相反
• 归并：先排序左右子数组，然后合并两个有序子数组。
• 快排：先调配出左右子数组，然后对于左右子数组进行排序。让左边的数组的所有元素都小于右边数组的所有元素，中间的叫pivot，左边的都小于pivot，右边的都大于pivot，但是左右匀速这个时候还是无序的，那么对于左右子树租分别调用排序的函数进行分治。
• 这两个是相当于高级排序里面的重点，一定要多过遍数。
• 堆排序（Heap Sort）- 堆插入O(logN)，取最大/小值O(1)
• 1. 数组元素依次建立小顶堆。
• 2. 依次取堆顶元素，并删除。
• 堆排的话堆那里有一个特性，堆本身有大顶堆和小顶堆，小顶堆那么元素是最小的元素放在最前面，大顶堆就是最大的元素放在最前面，每次插入删除和维护堆都是logN的，取最大值或者最小区都是O(1)的，所以它要做的一件事情是，把数组的元素依次插入到这个堆里面，建立起小顶堆，然后依次再取堆顶元素并删除，因为依次取堆顶元素，所以最后就是把所有元素从小到大从这个堆里面取出来了，取的这个过程就能保证所有元素是有序的。
• 堆排序代码：堆排序并不是需要让大家去手写一个堆。C++代码直接调了标准的C++库STL里面的priority_queue。这个queue就是一个优先队列，它的默认从小到大排序的堆，然后把所有元素依次放在queue里面去，接下来再从queue里面依次取它的头元素，且调了pop，pop就是去它的最小的元素出来，先把最小的元素给打掉，然后放回到a[i]里面去，然后就排好序了。它的整个时间复杂度是nlogn的。

赏

谢谢你请我喝咖啡