位运算
在计算机存储的世界中,一切都是二进制的,位运算就是对二进制位进行操作的一种运算。位运算是计算机中的一种常见运算,可以用来提高性能和提升代码的可读性。
位运算有很多种,比如与、或、非、异或等,这些运算可以用来实现很多高效的算法。在这里,我们根据Bitmap实现密码强度检查器的实例,讲解位运算的实际应用场景。
代码讲解
private static final int[] bitmaps = createBitmap();
public static final int UPPER_CASE = 1 << 1;
public static final int LOWER_CASE = 1 << 2;
public static final int DIGIT = 1 << 3;
public static final int SPECIAL_CHAR = 1 << 4;
public static final int ALL = UPPER_CASE | LOWER_CASE | DIGIT | SPECIAL_CHAR;
static int[] createBitmap() {
int[] maps = new int[128];
for (int i = 0; i < 128; i++) {
if (i >= 65 && i <= 90) { // A-Z
maps[i] = UPPER_CASE;
} else if (i >= 97 && i <= 122) { // a-z
maps[i] = LOWER_CASE;
} else if (i >= 48 && i <= 57) { // 0-9
maps[i] = DIGIT;
} else if (i == 33 || i == 64 || i == 35 || i == 36 || i == 37 || i == 94 || i == 38 || i == 42 || i == 95
|| i == 45) { // !@#$%^&*_
maps[i] = SPECIAL_CHAR;
}
}
return maps;
}
public static boolean checkPasswordStrengthWithBitmap(String password) {
if (password.length() < 6) {
return false;
}
int hints = 0;
int count = 1;
int prevDiff = 0;
for (int i = 0; i < password.length(); i++) {
char c = password.charAt(i);
int currentBit = bitmaps[c];
if ((currentBit & ALL) == 0) {
return false;
}
hints |= currentBit;
}
return hints == ALL;
}
上面的代码中,我们使用Bitmap来表示密码中的字符,然后用位运算来判断是否符合要求。
我们先说清楚Bitmap的构建,我们用一个长度为128的数组来表示ASCII码表中的字符,然后用1 << 1, 1 << 2, 1 << 3, 1 << 4来表示大小写字母、数字、特殊字符,然后用位运算来判断是否符合要求。
那么我们先看一下UPPER_CASE、LOWER_CASE、DIGIT、SPECIAL_CHAR这四个常量:
从上面的图可以看出来,1 << 1 就是2, 对应的二进制表示就是"00000010"
| 或运算
ALL 这个变量UPPER_CASE | LOWER_CASE | DIGIT | SPECIAL_CHAR的或运算:
二进制的或运算是将两个数的二进制表示对应位进行或运算,只要有一个为1,结果就是1,否则就是0。
也就是00000010 | 000000100 | 0000001000 | 00000010000,也就是00000011110 所以ALL就是表示每个位上的状态都是1,也就是密码中包含了大小写字母、数字、特殊字符。
|= 或运算
hints |= currentBit 这个语句是将hints和currentBit进行或运算,然后将结果赋值给hints。 等同于:
hints = hints | currentBit;
就是相当于将hints的每一位和currentBit的每一位进行或运算,然后将结果赋值给hints。
& 与运算
代码中,我们用(currentBit & ALL) == 0来判断是否符合要求,这里用到了与运算。 二进制的与运算是将两个数的二进制表示对应位进行与运算,只有两个数的对应位都是1,结果才是1,否则就是0。
也就是00000010 & 0000001110,也就是00000010, 因为只有第二位是1,其他位都是0。 这个值就不会等于0,就表示当前的字符是符合要求的。
~ 非运算
~ 非运算是将一个数的二进制表示取反,也就是0变成1,1变成0。 也就是~00000010,也就是11111101,这个值就是-3。
配合与运算,可以用来取消hints的某一位, 比如当前是 UPPER_CASE | LOWER_CASE, 我们想取消LOWER_CASE,
- 可以用hints & ~LOWER_CASE来取消LOWER_CASE,
- 也就是00000010 & ~00000100,---> 00000010 & 11111011,---> 00000010
- 这样就取消了LOWER_CASE。
比如:
hints = hints &= ~currentBit;
等同于:
hints = hints & ~currentBit;
^ 异或运算
异或运算是将两个数的二进制表示对应位进行异或运算,只有两个数的对应位不相同,结果才是1,否则就是0。
也就是00000010 ^ 0000001110,也就是000000110, 因为只有第二位是1,其他位都是0。 这个值就不会等于0,就表示当前的字符是符合要求的。
总结
在实际的开发中,我们可以用位运算来实现很多高效的算法,比如Bitmap、布隆过滤器等,这些算法都是基于位运算的,可以提高代码的性能和可读性。
作为后端开发工程师,我们需要了解位运算的基本原理和应用场景,这样才能更好地优化代码,提高系统的性能。
所有的后端面试常见的问题,我们每天都会在我们的编程群里面讨论和Code review, 欢迎大家加入我们的编程群,一起学习和进步。
欢迎大家关注 入职啦 (公众号: ruzhila) ,获取更多有趣的编程挑战题和技术干货!