介绍

算术运算有：加（+）、减（-）、乘（*）、除（/）、求模(%)
位运算有：&（按位与）、|（按位或）、^（按位异或）、~（按位取反）、<<（按位左移右边补0）、>>（按位右移左边补符号位）、>>>（按位右移左边补0）
神仙题：在面试中如果之前见到过就会，没见到过就不会

布隆过滤器

布隆过滤器可以精确地表示一个集合，可以精确地判断元素是否在此集合中，精确程度由用户的具体设计决定，做到100%的精确即正确是不可能的，如果面试中的题目涉及到以下几点，则面试官需要你掌握布隆过滤器的知识

• 网页黑名单系统
• 垃圾邮件过滤系统
• 爬虫的网址判断重复系统
• 容忍一定程度的失误率
• 对空间要求较严格

布隆过滤器的优势在于，利用很少的空间可以做到精确率较高。
布隆过滤器具体原理如下：
假设有一个长度为m的bit类型的数组array，其中每个元素只有0和1两个状态
假设一共有k个hash函数，这些函数的输出域都大于或等于m，对hash的要求是它能够容纳题目中要求过滤的数据特征表示的大小的参数，并且足够优秀，相互独立。

• 具体过程为：1）构建过程：将需要过滤的数据特征表示作为参数输入hash函数，将hash函数的结果对m取模，将取余后的结果在array中的对应位置涂黑（置1），数据特征表示经过k个hash函数后将吧array中的k个位置涂黑。对所有训练数据经过所有hash函数处理，并涂黑array中相应的位置。2）过滤过程：只需要将待过滤数据特征表示作为k个hash函数的参数，hash函数的输出值对m取模后，检查array中与其对应的位置是否被涂黑，只要有一个位置没被涂黑就不被拦截。
• 布隆过滤器中m，k的计算，从待过滤中选取的的对象数量为n，要求误判率小于p。codecogs
  单个样本大小不影响布隆过滤器大小，只影响了哈希函数的实现细节。
  • m的计算公式如下：
    
  • k的计算公式如下：
    
  • p的计算公式如下：
    

经典题

• 布隆过滤器的使用
  不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64字节。现在想要实现一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上，请设计该系统。要求该系统允许有万分之一以下的判断失误率，并且使用的额外空间不要超过30G。
  此题根据公式计算得：m = 19.19n，向上取值为20n，即2000亿bit，约为25G
  根据公式计算得：k = 14
• 请不用任何额外变量交换a,b的值，代码如下：

#位运算（与、或、异或）满足交换律和结合律
a = a ^ b
b = b ^ a
a = a ^ b

• 给定两个32位整型数，a、b，请返回其中的最大值，要求不能使用比较的方法
  直接粘代码，此处如果直接通过c的符号来判断a,b的大小可能会导致溢出

class Compare:
    def flip(self, n):
        return n ^ 1
    def sign(self, n):
        return self.flip((n >> 31) & 1)
    def getMax(self, a, b):
        # write code here
        c = a - b
        a_sign = self.sign(a)
        b_sign = self.sign(b)
        c_sign = self.sign(c)
        diff_ab_sign = a_sign ^ b_sign #符号相同则为0，符号不同则为1
        same_ab_sign = self.flip(diff_ab_sign)
        return_a = diff_ab_sign * a_sign + same_ab_sign * c_sign
        return_b = self.flip(return_a)
        return return_a * a + return_b * b

• 给定整型数组arr，其中只有一个数出现了奇数次，其他数出现了偶数次，打印出现奇数次的数
  设eo = 0，在遍历arr的过程中计算每个元素和eo异或的结果，并赋值给eo，遍历完成后eo的值即为目标值
• 给定整型数组arr，其中有两个数出现了奇数次，其他数出现了偶数次，打印出现奇数次的数
  1、设eo = 0，在遍历arr的过程中计算每个元素和eo异或的结果，并赋值给eo，遍历完成后eo的值为出现奇数次的两个元素的异或，设这两个数位a，b则eo = a ^ b
  2、分析eo，假设eo_k = 1，则a_k和b_k中有一个为0，一个为1，假设a_k = 1
  3、设eo' = 0，在遍历arr的过程中计算arr中第k位为1的元素和eo'异或的结果，并赋值给eo'，遍历完成后eo'的值即为a的值
  4、b = eo' ^ eo