牛客网《BAT面试算法精品课》笔记七：位运算

牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 算术运算常见操作符：+ - * / % 位运算常见操作符：& | ^ ~ << >> 位运算的面试题大部分靠平时积累。新题在面试场上较难想出解题思路。 **案例一.[

](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042184-300x86.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042184.png)** 普通方法：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042185.png) **布隆过滤器方法：** 如果遇到以下这些题，那面试官很可能就是在考察你布隆过滤器的知识： 网页黑名单系统； 垃圾邮件过滤系统； 爬虫的网址判断重复系统； 容忍一定程度的失误率； 对空间要求比较严格； 布隆过滤器可以精确的代表一个集合，可以精确判断某一个元素是否在此集合中，精确程度由用户的具体设计决定，做到100%的精确即正确是不可能的。 布隆过滤器的优势在于，利用很少的空间可以做到精确率较高。 bitarray数组，每个位置占一个bit：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042186.png) 布隆过滤器bitarray大小如何确定：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042187.png) 真实失误率：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042188.png) 生成布隆过滤器的过程总结：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042189.png) **案例二.** 如何不用任何额外变量交换两个整数的值？ 给定整数a，整数b 使用额外变量： Int c=a;  a=b;  b=c; 使用位运算： a=a ^ b;  b=a ^ b;  a=a ^ b; 不使用位运算和额外变量： a=a+b;  b=a-b;  a=a-b; **案例三.** 给定两个32位整数a和b，返回a和b中较大的，但是不能用任何比较判断。 方法一.[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042190.png) 方法二:[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042191.png) **案例四.** 给定一个整形数组arr，其中只有一个数出现了奇数次，其他的数都出现了偶数次，请打印这个数。要求时间复杂度O(N)，额外空间复杂度O(1) n与0异或结果为n，n与n异或结果为0. eo=0，arr={C,B,D,A,A,B,C} 异或运算满足交换率，异或运算满足结合率。 按照原始arr数出现的顺序异或结果，与该数组异或的结果相同：{A,A,B,B,C,C,D} eo与上述数组异或的结果为：eo=D **案例五. ** 给定一个整形数组arr，其中有两个数出现了奇数次，其他的数都出现了偶数次，请打印这两个数。要求时间复杂度O(N)，额外空间复杂度O(1) [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042192.png) **案例六.** 请设置一种加密过程，完成对明文text的加密和解密工作 [