少年游

欲买桂花同载酒，终不似，少年游。

0%

JAVA位运算以及在大数据上的应用

发表于 更新于 分类于
塔布数据

位运算

1
2
3
4
5
6
7
* & : 与运算
* | : 或运算
* ^ : 异或运算
* ~ : 非运算
* << : 左移操作，右侧补0
* >> : 右移操作，左侧补1
* >>> : 右移操作，左侧补0

基本技巧

  1. 判别奇数偶数
    (num & 1) != 0 为奇数 (常规情况下, 取余操作没有逻辑操作快)
  2. 判别某一位为1
    num = num >> indexBit; //右移indexBit位
    (num & 1) == 1 //判断当前位是不是1
  3. 二进制数1的个数
    (n & (n -1)) //不断清除最右边的 1
  4. 异或 数学逻辑
    b = a ^ b ^ a
    a ^ a = 0
    a ^ 0 = a
    eg:加密运算，将text和psd异或加密。

实例

  1. 数组中有两个元素出现了奇数次，其他元素出现了偶数次。找出这两个元素。

解析：a^b^c^d^…^z,出现偶数次可以抵消，奇数次则最终留下来运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package com.leetcode;

import java.util.BitSet;

/**
 * Created by Paul on 2016/9/23.
 */
public class TwoEven {

    public static void main(String[] args){
        int a[]={1,2,3,4,5,6,1,2,3,4,7,5,1,1,7,7};
        fun(a);
    }


    public static void fun(int[] data){
        int e0 = 0;
        for(int i = 0;i < data.length;i ++){
            e0 = e0 ^ data[i];
        }
        //在indexBit这个位置上面，一定有一个是1，另外一个为0
        int indexBit = findFirstBit(e0);
        int num1 = 0, num2 =0;
        for(int i = 0;i < data.length;i ++){

            if(isbit1(data[i] ,indexBit))num1 = num1 ^ data[i];
            else
                num2 = num2 ^ data[i];
        }
        System.out.println(num1 + " | " + num2);

    }

    public static  int findFirstBit(int num){
        // 64位机器
        int indexBit = 0;
        // num & 1 == 0  如果这样写，会报错。原来位运算 优先级 比 == 低
        while((num & 1) == 0 && (indexBit < 32)){
            num = num >> 1;
            indexBit ++;
        }
        return indexBit;
    }

    // 对应bit位是0还是1
    public static boolean isbit1(int num,int indexBit){
        num = num >> indexBit;
        return (num & 1) == 1;
    }
}

  1. 对于两个32位整数a和b，请设计一个算法返回a和b中较大的。但是不能用任何比较判断。若两数相同，返回任意一个。
    给定两个整数a和b，请返回较大的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 sa = sign(a);
        int sb = sign(b);
        int sc = sign(c);
        int difSab = sa ^ sb;
        int sameSab = flip(difSab);
        int returnA = difSab * sa + sameSab * sc;
        int returnB = flip(returnA);
        return a * returnA + b * returnB;
    }
}

大数据之位存储

BitSet

1.set(int bitIndex)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
    * Sets the bit at the specified index to {@code true}.
    *
    * @param  bitIndex a bit index
    * @throws IndexOutOfBoundsException if the specified index is negative
    * @since  JDK1.0
    */
   public void set(int bitIndex) {
       if (bitIndex < 0)
           throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

       int wordIndex = wordIndex(bitIndex);
       expandTo(wordIndex);

       words[wordIndex] |= (1L << bitIndex); // Restores invariants

       checkInvariants();
   }

2.get(int bitIndex) 取值
1
2
3
4
5
6
7
8
9
10
public boolean get(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        checkInvariants();

        int wordIndex = wordIndex(bitIndex);
        return (wordIndex < wordsInUse)
            && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }

3.flip(int bitIndex) 置反
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
     * Sets the bit at the specified index to the complement of its
     * current value.
     *
     * @param  bitIndex the index of the bit to flip
     * @throws IndexOutOfBoundsException if the specified index is negative
     * @since  1.4
     */
    public void flip(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);
        expandTo(wordIndex);

        words[wordIndex] ^= (1L << bitIndex);

        recalculateWordsInUse();
        checkInvariants();
    }

4.clear(int bitIndex)清除
1
2
3
4
5
6
7
8
9
10
11
12
13
public void clear(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);
        if (wordIndex >= wordsInUse)
            return;

        words[wordIndex] &= ~(1L << bitIndex);

        recalculateWordsInUse();
        checkInvariants();
    }

Bloom filter

原理 : hash + BitSet
(1) 一般情况：通过hash函数映射到BitSet上
y = f(x) % BitSet.size();
y的位置在BitSet上为1
(2) 布隆过滤器 : n个独立的hash函数 + m位的BitSet;
hash函数之后投射到m位的BitSet上，需要index = f(x) % m;
(3) 如果当前的x输入，经过映射会出现y1,y2,…,yn.如果y1,y2,….,yn位置上全是1.
则返回true.否则，返回false,即从未出现过。

常用场景：
1.网页黑名单系统
2.垃圾邮件过滤系统
3.爬虫的网址判断