数据结构小记

位运算

作者 Wavy Peng 日期 2018-05-27
数据结构
数据结构小记

【声明】 图源：牛客网

基本概念

  • 算术运算的常见操作符：+、-、*、/、%
  • 位运算的常见操作符：&（按位与）、|（按位或）、^（按位异或）、~（取反）、<<（左移右侧补零）、>>（右移左侧补符号位）、>>>（右移左侧补零）

经典案例

案例一

题目

布隆过滤器

不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64个字节。现在想要实现一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单。请设计系统，要求该系统允许有万分之一以下的判断失误率，并且使用额外空间不要超过30G。

分析

考察点：大数据、位运算

  • 应用场景
    • 容忍一定程度的失误率，对空间要求较严格==>布隆过滤器
      • 网页黑名单系统
      • 垃圾邮件过滤系统
      • 爬虫的网址判断重复系统
  • 普通方法
    • 将黑名单存入哈希表或数据库，接下来就是对每个URL进行查询，判断其是否在黑名单里
    • 此时：数据量100亿、单个URL占64字节，则需要空间$64Byte*100亿=6400亿Byte=640G$空间
    • 此方法违反了额外空间的限制

  • 布隆过滤器

    • 可精确地代表一个集合

    • 可精确地判断某一元素是否在此集合中

    • 精确度由用户的具体设计决定，做到100%的精确是不可能的

    • 优势：利用很少的空间，可以做到精确率较高

    • 针对本题，布隆过滤器的具体实现思路如下：

      • 定义bitarray，每个位置一个bit，分0（白）1（黑）两种状态
      • 假设共有K个哈希函数，输出域>=m，优秀且各自独立
      • 对同一个URL，经过K个哈希函数计算出来的结果也是相互独立的
      • 每个计算出来的结果对m取余，在bitarray上对应的位置处记录为1（描黑）
      • 接下来对所有的URL进行上述3~4操作，生成一个完整的布隆过滤器

    • 如何检测某个URL是否在上述生成的布隆过滤器中？

      • 假设待测URL=a，对a进行K个哈希函数计算，结果对m取余，得到0~m-1范围上的K个值
      • 接下来在bitarray上比较这K个值是否都是黑的，如果有一个不为黑，则a一定不在集合里；如果都为黑，说明a在此集合里（但是也有可能产生误判）
      • 产生误判的原因：
        • 如果在生成布隆过滤器的过程中，因为输入的对象过多而bitarray的空间又过小时，会导致bitarray上绝大多数位置都已经变黑了，在检测a时，由于K个位置上已经描黑，会错误地判断a在集合中。（宁可错杀三千，不可放过一个）

    • 布隆过滤器的bitarray大小如何确定？

      • 大小为m，样本数量为n，失误率为p，m有n和p来决定
      • 分析本题场景：n=100亿，p=0.01%，单个样本大小不影响布隆过滤器大小，只影响了哈希函数的实现细节
      • $m=-\frac{n×lnp}{(ln2)^2}$，求得m=19.19n，向上取整为20n，2000亿bit约为25G
      • $k=ln2×\frac{m}{n}=0.7×\frac{m}{n}$，求得k=14（需要14个彼此独立的哈希函数）
      • 只要让每个哈希函数都能接收64bytes的字符串类型参数，并且返回的哈希值范围大于0~2000亿
      • 失误率计算公式$(1-e^{-\frac{nk}{m}})^k$，求得真实失误率p=0.006% < 0.01%
      • 哈希函数本身不占什么空间，所以使用的空间就是bitarray的大小即25G的空间

    • 总结生成布隆过滤器的过程：

      • 注意到题目允许有一定程度的失误率
      • 根据样本个数n，和允许的失误率p，结合以下公式$m=-\frac{n×lnp}{(ln2)^2}$求出m
      • 根据已经求得的m，以及以下公式$k=ln2×\frac{m}{n}=0.7×\frac{m}{n}$求得哈希函数个数k

案例二

题目

如何不用任何额外变量交换两个整数的值？

分析

实现
// 解法一
public int[] getSwap(int[] num) {
    num[0] = num[0] + num[1];
    num[1] = num[0] - num[1];
    num[0] = num[0] - num[1];
    return num;
}

// 解法二
public int[] getSwap(int[] num) {
    num[0] = num[0] ^ num[1];
    num[1] = num[0] ^ num[1];
    num[0] = num[0] ^ num[1];
    return num;
}

案例三

题目

给定两个32位整数a和b，返回a和b中较大的。但是不能用任何比较判断

分析
  • 方法一

sign()：取得32位整数符号，如果不是负数返回1，如果是负数返回0。

getMax1()：scA和scB只会有一个为1，另一个为0。如果a-b不是负数，scA为1，scB为0；如果a-b是负数，scA为0，scB为1。

  • 方法二

实现
public class Compare {
    public int flip(int n){
        return n^1;
    }
    public int sign(int n){
        return flip((n>>31)&1);
    }
    public int getMax(int a, int b) {
        int c=a-b;
        int as = sign(a);
        int bs = sign(b);
        int cs = sign(c);
        int difab = as^bs;
        int sameab = flip(difab);
        int returnA = difab*as + sameab*cs;
        int returnB = flip(returnA);
        return returnA*a + returnB*b;
    }
}

案例四

题目

给定一个整型数组arr，其中只有一个数出现了奇数次，其他的数都出现了偶数次，请打印这个数。要求时间复杂度为O(N)，空间复杂度为O(1)

分析
  • n与0异或结果为n，n与n异或结果为0
  • eo=0，arr=[C,B,D,A,A,B,C]，在遍历数组的过程中将每个数都与eo异或，最终eo=D即出现了奇数次的那个数，原因如下：
    • 异或运算满足交换律
    • 异或运算满足结合律
实现
public int findOdd(int[] A, int n) {
    int eo = 0;
    for(int i=0;i<n;i++)
        eo^=A[i];
    return eo;
}

案例五

题目

给定一个整型数组arr，其中有两个数出现了奇数次，其他数都出现了偶数次，打印这个数。要求时间复杂度O(n)，空间复杂度O(1)。

分析

实现
public int[] findOdds(int[] arr, int n) {
    int eo = 0;
    for(int i=0;i<n;i++)
        eo^=arr[i];
    // 计算eo（32位整数）中某位为1的位置k
    int k=0;
    while(((eo>>k)&1)!=1)
        k++;
    // 找到两个出现奇数次数中的一个
    int e = 0;
    for(int i=0;i<n;i++){
        if(((arr[i]>>k)&1)==1)
            e^=arr[i];
    }
    int e_ = eo^e;
    int[] res = {Math.min(e,e_),Math.max(e,e_)};
    return res;
}

案例六

题目

请设计一种加密过程，完成对明文text的加密和解密工作

分析

FEATURED TAGS
数据结构