位运算
基本概念
对于 8 位二进制，能表示的总数是 $2^8=256$，为了表示负数，将第一位作为符号位，并使用补码表示法：
正数：从 00000000 到 01111111，也就是从 0 到 127，一共 128 个值（包括 0）。
负数：从 10000000 到 11111111，代表 -128 到 -1，也是 128 个值。
由于 00000000 和 10000000 都能表示 0（一个正0，一个负0），但 0 只需一个编码，所以，负数可以“借”来这个位置，多表示一个数（就是 -128）。
负数的补码表示 = 该数的正数的反码 + 1，因为 1 + (-1) 要等于 0，而只改变符号的话，它们的二进制数相加并不等于 0，以 1 的二进制表示 00000001 为例，若使 1 - 1 = 0 成立，则 -1 应该为 11111111，而这正是 00000001 的反码 11111110 加 1 得到的。
对于 8 位二进制，只有 -128 不满足 负数的补码表示 = 该数的正数的反码 + 1，因为第一位已经被用来表示符号位，这时就不存在 +128，最大只能到 +127，而 0 只需一个表示就行，所以 10000000 就留给了 -128。
常见位运算
常见的位运算如下：
~：按位取反，0 变成 1，1 变成 0，如~1010 = 0101&：按为与运算， 1 与 1 方为 1|：按位或运算，只要有一个 为 1 ，则该位置 为 1^：按位异或，不相同的值则为 1，比如 0 异或 1，或者 1 异或 0<<：带符号左移，比如 35(00100011),左移一位为 70(01000110), -35(11011101)左移一位为 -70(10111010)>>：带符号右移，比如 35(00100011),右移一位为 17(00010001), -35(11011101)左移一位为 -18(11101110)<<<：无符号左移，比如 35(00100011),左移一位为 70(01000110)>>>：无符号右移，比如 -35(11011101),右移一位为 110(01101110)x ^= y;y ^= x;x ^= y;：x 与 y 交换s &= ~(1 << k)：第 k 位置为 0
位运算实现加法
如果给两个正数 a 和 b，怎么使用位运算求出它们的和。
a 与 b 的每一位相加，如果相加时没有产生进位，结果就是异或操作（a ^ b）的值，但是如果产生了进位，分为两部分，一部分是 a 和 b 不进位的和，另外一部分是 a 和 b 进位的结果，两部分相加即可。如果此时相加还是会有进位问题，那么就循环直到进位等于 0，即不产生进位为止：
当前位的和值等于
a ^ b进位的结果为
a & b，但是进位是往前每次往前进 1 位，叠加在前面一位上，因此需要左移一位a & b << 1。
将两者相加，在循环中直到进位为 0。代码如下：
public static int add(int a, int b) {
while (b != 0) {
int sum = a ^ b;
int carry = (a & b) << 1;
a = sum;
b = carry;
}
return a;
}统计二进制整数中1的数量
给一个整数，计算出该整数在二进制表示中 1 的个数。可以直接使用标准库中的 Integer.bitCount() 方法，该方法使用了位运算优化策略。常见的方法是使用循环，逐位检查。
任何一位与 1 进行与运算，最终结果都是它本身，那么一个数与 1 进行与运算（&），如果结果是 1 ，则说明最后一位 是 1。知道了最后一位是否为 1，只要把数字不断向右移位和 1 进行与计算，结果为 1 则说明最后一位是 1，循环直到数字为 0 即可。注意这里需要使用无符号右移，即 >>>，代码如下：
public static int countBits(int num) {
int count = 0;
while (num != 0) {
count += num & 1; // 检查最低位是否为 1
num >>>= 1; // 无符号右移一位
}
return count;
}位运算找字符串的差异
若有两个字符串 a 和 b，都是大小写字母，b 是由 a 字符串打乱字符顺序之后，再随机位置加上 1 个字符，转换而成，该如何找出这个字符。比如 a = "lasda" , b = "daldas" ,不同的字符是 "d"。
最简单的方法就是统计两个字符串中每个字符出现的次数，对比一下就可以找出多出来的字符到底是哪一个。
每个字符对应一个 ASCII 码，ASCII 码使用指定的 7 位或 8 位二进制数组合来表示 128 或 256 种可能的字符。标准 ASCII 码也叫基础 ASCII 码，使用 7 位二进制数（剩下的 1 位二进制为 0）来表示所有的大写和小写字母，数字 0 到 9、标点符号，以及在美式英语中使用的特殊控制字符。另一种方式就是我们将每个字符的 ASCII 全部加起来，差值就是多出来字符的 ASCII 码，ASCII 码的数值是 int ，可以转换成为字符。
也可以使用位运算解决，首先，可以注意到 a^b^a = b，即任何一个字符，与偶数个其他字符进行异或运算，最终结果等于本身。所以两个字符串的所有字符都进行异或，多出来的字符数量必定是奇数，其他的字符数量是偶数。因此，只需要对所有字符进行异或计算，就可以得到最终结果。代码如下：
public static char findDifferentChar(String a, String b) {
int ret = 0;
for(char c : a.toCharArray())
ret ^= c;
for(char c : b.toCharArray())
ret ^= c;
return (char) ret;
}二进制中的汉明距离
信息论中，Hamming Distance(汉明距离)表示两个等长字符串在对应位置上不同字符的数目，从另外一个方面看，汉明距离度量了通过替换字符的方式将字符串 x 变成 y 所需要的最小的替换次数。比如：
"KathSam" 和 "kothran" 的汉明距离是 3
1111101 和 1001001 的汉明距离是 3这里的问题是计算两个整数 a 和 b ，他们的二进制表示中不同的位置的数量（汉明距离）。
可以分为两步：
先异或计算，获取到数值不同的位置
计算数值不同的位的数量，正好使用之前统计二进制整数中1的数量的代码。
代码如下：
public static int hammingDist(int a, int b) {
int s = a ^ b, count = 0;
while(s != 0) {
count += s & 1;
s >>>= 1;
}
return count;
}对于该循环计算1数量的代码，即使是 0 位置我们也会循环，每次都要循环完 32 位。有一个Brian Kernighan优化算法，该算法使用 x 与 x-1 做与运算，得到的结果恰好为 x 删去其二进制表示中最右侧的 1 的结果。即循环中每次 x &= x-1 操作都会删去最右侧的一个 1，直到等于 0，循环的次数就是 1 的个数：
public static int hammingDist_opt(int a, int b) {
int s = a ^ b, count = 0;
while(s != 0) {
s &= s - 1;
count++;
}
return count;
}布隆过滤器
布隆过滤器的误判率是可以预测的，与位数组的大小，以及 hash 函数的个数等相关。
假设位数组的大小是 m，一共有 k 个 hash 函数，那么每一个 hash 函数，只能 hash 到 m 位中的一个位置，所以某一位没有被 hash 到的概率是 $1-1/m$，k 个 hash 函数都 hash 之后，该位还是没有被 hash 到的概率为 $(1-1/m)^k$。
如果此时插入了 n 个元素，即位数组已经被 hash 了 n*k 次，该位还是没有被 hash 到的概率是 $(1-1/m)^{kn}$，那么该位已被 hash 变成 1 的概率为 $1-(1-1/m)^{kn}$。
如果需要检测某一个元素是不是在集合中，也就是该元素对应的 k 个位 hash 出来的值都为 1，即元素本不存在，但该元素对应的所有位都被 hash 变成 1 的概率是 $(1-(1-1/m)^{kn})^k$，当 m 很大时可近似为 $(1-e^{-kn/m})^k$。
所以，随着位数组大小 m 和 hash 函数个数的增加，误判率会下降，随着插入的元素 n 的增加，概率会上升。
最后还可以根据自己期待的误判率 P 和期待添加的个数 n，来大致计算出布隆过滤器的位数组的长度：$m=-\frac{n\ln P}{(\ln 2)^2}$。
下面实现一个简单的布隆过滤器，需要考虑的点：
位数组空间大小，其他不变，位空间越大，hash 冲突的可能性越小。
hash 函数的实现，为避免冲突，应使用多个不同的质数来当种子。
实现两个方法：添加元素和判断某元素是否存在。
下面用了简单的 hash 函数，主要是使用 hash 值得高低位进行异或，然后乘以种子，再对位数组大小进行取余数：
public class MyBloomFilter {
private static final int DEFAULT_SIZE = Integer.MAX_VALUE; // 默认大小
private static final int MIN_SIZE = 1000;
private int SIZE = DEFAULT_SIZE;
// hash函数的种子因子
private static final int[] HASH_SEEDS = new int[]{3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
// 位数组，表示特征
private BitSet bitSet = null;
// hash 函数
private HashFunction[] hashFunctions = new HashFunction[HASH_SEEDS.length];
public MyBloomFilter() {
init();
}
public MyBloomFilter(int size) {
if(size > MIN_SIZE) {
SIZE = size;
}
init();
}
private void init() {
bitSet = new BitSet(SIZE);
for(int i = 0; i < HASH_SEEDS.length; i++) {
hashFunctions[i] = new HashFunction(SIZE, HASH_SEEDS[i]);
}
}
public void add(Object value) {
for(HashFunction hf : hashFunctions)
bitSet.set(hf.hash(value)); // 将hash计算出来的位置为true
}
public boolean contains(Object value) {
boolean result = true;
for(HashFunction hf : hashFunctions) {
result = bitSet.get(hf.hash(value));
// hash函数只要有一个计算出为false，则直接返回
if(!result)
return result;
}
return result;
}
public static class HashFunction {
int size;
int seed;
public HashFunction(int size, int seed) {
this.size = size;
this.seed = seed;
}
public int hash(Object value) {
if(value == null)
return 0;
else {
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16; // 高位的hash值
int combine = hash1 ^ hash2; // 合并hash值(相当于把高低位的特征结合)
return Math.abs(combine * seed) % size; // 相乘再求余
}
}
}
public static void main(String[] args) {
Integer num1 = 12321;
Integer num2 = 12345;
MyBloomFilter myBloomFilter =new MyBloomFilter();
System.out.println(myBloomFilter.contains(num1));
System.out.println(myBloomFilter.contains(num2));
myBloomFilter.add(num1);
myBloomFilter.add(num2);
System.out.println(myBloomFilter.contains(num1));
System.out.println(myBloomFilter.contains(num2));
}
// BitSet 应用于找素数的例子
private static List<Integer> primes(int n) {
BitSet isPrime = new BitSet(n + 1);
isPrime.set(2, n + 1); // 默认全部设为true
// 埃拉托色尼筛法
for(int i = 2; i * i <= n; i++) {
if(isPrime.get(i)) {
for(int j = i * i; j <= n; j += i)
isPrime.clear(j);
}
}
List<Integer> res = new ArrayList<>();
for(int i = 2; i <= n; i++) {
if(isPrime.get(i))
res.add(i);
}
return res;
}
}
/* output
false
false
true
true */