二进制妙用之位标记
_herbert
2021-11-03 17:08
1. 使用背景
已知一个字符串 String s = "abcdefg"，需要判断字符串中是否存在重复的字符。
2. 常规实现
根据Hashset特性判断重复。
public void test2() {
String s1 = "abcadeeee";
Set s = new HashSet();
for (int i = 0; i < s1.length(); i++) {
if (!s.add(s1.charAt(i))) {
System.out.println("第[" + i + "]位字符 " + s1.charAt(i) + " 已经存在");
}
}
}
3. 二进制实现
实现原理有以下两点
- 同一个字符-‘a’得到的值一定相等
- 将该值对应的位置打上标记，作为重复判断的依据
所以，二进制的实现也可以换成数组来实现。但是，通过二进制实现可以大大减少内存占用。
二进制可以实现原理如下
- 初始一个值为0的整数。它对应在计算机的存储格式
00000000 00000000 00000000 00000000 - 利用二进制或运算【|】，将对应位置二进制转换为1,比如
00 | 10 = 10，我们此此时就知道对应索引值为1的字符已经出现了。 - 利用二进制与运算【&】，判断字符串是否已经出现过。比如当字符串还未出现时
00&10 = 00，已经有字符串出现时11&10 = 10此时结果不等于0 - 二进制按位左移【<<】,比如
01<<1 = 10
最终代码实现如下
// author:herbert date:20211022 wx:464884492
public void findRepeatChar(){
String s1 = "abcadeeee";
int mark = 0;
for (int i = 0; i < s1.length(); i++) {
Integer bitIndex = s1.charAt(i) - 'a';
if ((mark & (1 << bitIndex)) !=0) {
System.out.println("第["+i+"]位字符 "+s1.charAt(i) + " 已经存在");
}
mark = mark|(1 << bitIndex);
}
}
5. 总结
欢迎感兴趣的朋友关注我的订阅号“小院不小”，或点击下方二维码关注。我将多年开发中遇到的难点，以及一些有意思的功能，体会都会一一发布到我的订阅号中
评论