- 1. 利用异或交换两个数
- 2. 寻找唯一的重复元素
- 3. 寻找只有一个出现了奇数次的数
- 4. 寻找只有两个出现了奇数次的数
- 5. 不用加减乘除做加法
- 6. 异或进行加密
- 7. 返回max值，不用比较判断
- 8. 格雷编码
- 9. 布隆过滤器
# 异或
# 1. 利用异或交换两个数
思路： 这个交换两个变量而无需借助第3个临时变量过程，其实现主要是基于异或运算的如下性质：
- 任意一个变量X与其自身进行异或运算，结果为0，即
X^X=0 - 任意一个变量X与0进行异或运算，结果不变，即
X^0=X - 异或运算具有可结合性，即
a^b^c=（a^b）^c=a^（b^c） - 异或运算具有可交换性，即
a^b=b^a
a = a^b
b = a^b = a^b^b = a
a = a^b = a^b ^a = a^a^b = b (这一步的时候a还是等于a^b)
def getSwap(num):
a = num[0]
b = num[1]
a = a ^ b
b = a ^ b
a = a ^ b
return [a, b]
# 2. 寻找唯一的重复元素
1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？
答：
令，1^2^...^1000（序列中不包含n）的结果为T
则1^2^...^1000（序列中包含n）的结果就是T^n。
T^(T^n)=n。
# 3. 寻找只有一个出现了奇数次的数
def findOdd(A):
n = len(A)
s = 0
for i in range(n):
s ^= A[i]
return s
# 4. 寻找只有两个出现了奇数次的数
给定一个数字arr，其中只有有两个数字出现了奇数次，其它数字都出现了偶数次，按照从小到大顺序输出这两个数。
思路：
- 从头到尾异或一遍，你就得到了需要求的两个数异或后的值。这两个数显然不相等，异或出来的结果不为0。
- 我们可以据此找出两个数的二进制表达中不同的一位，然后把所有这n个数分成两类，在那一位上是0的分成一类，在那一位上是1的分到另一类。
- 按照原先的异或解法，从每一部分中找出唯一的奇数次整数即可。
def findOdds(arr):
n = len(arr)
res1 = 0
for i in range(n):
res1 ^= arr[i]
res2 = 0
pos = 0
for i in range(32):
if (1<<i & res1):
pos = i
break
for i in range(n):
if 1 << pos & arr[i]:
res2 ^= arr[i]
res3 = res2 ^ res1
return [res3, res2] if res3 < res2 else [res2, res3]
# 5. 不用加减乘除做加法
思路：
1. 5+7，5二进制为101，7二进制为111 第一步：相加各位的值，不算进位，
得到010，二进制每位相加就相当于各位做异或操作，101^111。
2. 第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左
移一位得到1010，(101&111)<<1。
3. 第三步重复上述两步， 各位相加 010^1010=1000，进位值为
100=(010&1010)<<1。
4. 继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为
最终结果。
简单来说，就是异或，按位与并左移（计算进位值），直到进位值为0。
def add(m, n):
while n:
t = (n ^ m) & 0xFFFFFFFF
n = ((n & m) << 1 &) 0xFFFFFFFF
m = t
return m if m <= 0xFFFFFFFF else ~(m ^ 0xFFFFFFFF)
和大数0xFFFFFFFF做与运算，最大不会超过这个数，模拟C++中超出最大范围变成0！
a^0xFFFFFFFF 相当于对a取反
# 6. 异或进行加密
异或运算可完成简单的加密与解密过程
明文text，用户给定的密码pw，假设密文为cipher。
cipher = text ^ pw
text = cipher ^ pw = (text ^ pw) ^ pw
= text ^ (pw) ^ pw
= text
如果text长度大于pw，循环使用pw与text进行按位异或。
# 7. 返回max值，不用比较判断
方法一：
得到 a-b 的符号，根据该符号决定返回 a 或 b。
# 如果符号为0，那么得到1，如果符号为1，那么得到0
def flip(n):
return 1 ^ n
# 获取符号位，返回值1代表非负数，0代表负数
def getSign(n):
return flip((n >> 31) & 1)
def getMax(a, b):
c = a - b
scA = getSign(c)
scB = flip(scA)
return a * scA + b * scB
# 如果a > b，scA = 1, 则返回a; 如果 a < b，scB = 1, 则返回b
方法一可能会有问题，当a-b溢出时，会发生错误。
方法二：
def getMax(a, b):
c = a - b
a_s = getSign(a) # a的符号，若为1表示非负，为0表示负
b_s = getSign(b)
c_s = getSign(c)
dif_ab = a_s ^ b_s # 表示a和b的符号是否不相同，不相同为1，相同为0
same_ab = flip(dif_ab) # 表示a和b的符号是否相同，相同为1，相同为0
res_a = diff_ab * a_s + same_ab * c_s
res_b = flip(res_a)
return res_a * a + res_b * b
解释：
- ab符号相同一定不会溢出，所以取差值c的符号
- ab符号不同，可能会溢出，取a的符号。a若为正，符号为1，返回a；a若为负，符号为0，返回b
# 8. 格雷编码
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。
def grayCode(n):
res = []
for i in range(1 << n):
res.append(i ^ (i >> 1))
return res
解释：
- 给定位数
n，i从 0 取到2^n−1 gray(i) = i ^ (i / 2)
如 n = 3: gray(0) = 0 ^ 0 = 000 ^ 000 = 000 gray(1) = 1 ^ 0 = 001 ^ 000 = 001 gray(2) = 2 ^ 1 = 010 ^ 001 = 011 gray(3) = 3 ^ 1 = 011 ^ 001 = 010 gray(4) = 4 ^ 2 = 100 ^ 010 = 110 gray(5) = 5 ^ 2 = 101 ^ 010 = 111 gray(6) = 6 ^ 3 = 110 ^ 011 = 101 gray(7) = 7 ^ 3 = 111 ^ 011 = 100
# 9. 布隆过滤器
如果一个黑名单网站包含100亿个黑名单网页，每个网页最多占64B，设计一个系统，判断当前的URL是否在这个黑名单当中，要求额外空间不超过30GB，允许误差率为万分之一。
解题思路：布隆过滤器
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量(位图)和一系列随机映射函数（哈希函数）。 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
# 9.1. 实际工程的应用
实际上，布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等，有人会想，我直接将网页URL存入数据库进行查找不就好了，或者建立一个哈希表进行查找不就OK了。
当数据量小的时候，这么思考是对的，但如果整个网页黑名单系统包含100亿个网页URL，在数据库查找是很费时的，并且如果每个URL空间为64B，那么需要内存为640GB，一般的服务器很难达到这个需求。
那么，在这种内存不够且检索速度慢的情况下，不妨考虑下布隆过滤器，但业务上要可以忍受判断失误率。
# 9.2. 位图（bitmap）
布隆过滤器其中重要的实现就是位图的实现，也就是位数组，并且在这个数组中每一个位置只占有1个bit，而每个bit只有0和1两种状态。如上图bitarray所示！bitarray也叫bitmap，大小也就是布隆过滤器的大小。
假设一种有k个哈希函数，且每个哈希函数的输出范围都大于m，接着将输出值对k取余（%m）,就会得到k个[0, m-1]的值，由于每个哈希函数之间相互独立，因此这k个数也相互独立，最后将这k个数对应到bitarray上并标记为1（涂黑）。
等判断时，将输入对象经过这k个哈希函数计算得到k个值，然后判断对应bitarray的k个位置是否都为1（是否标黑），如果有一个不为黑，那么这个输入对象则不在这个集合中，也就不是黑名单了！如果都是黑，那说明在集合中，但有可能会误，由于当输入对象过多，而集合也就是bitarray过小，则会出现大部分为黑的情况，那样就容易发生误判！因此使用布隆过滤器是需要容忍错误率的，即使很低很低！
参考资料：