二进制妙用之位标记

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. 二进制实现

实现原理有以下两点

1. 同一个字符-‘a’得到的值一定相等
2. 将该值对应的位置打上标记，作为重复判断的依据

所以，二进制的实现也可以换成数组来实现。但是，通过二进制实现可以大大减少内存占用。

二进制可以实现原理如下

1. 初始一个值为0的整数。它对应在计算机的存储格式 00000000 00000000 00000000 00000000
2. 利用二进制或运算【|】，将对应位置二进制转换为1,比如 00 | 10 = 10，我们此此时就知道对应索引值为1的字符已经出现了。
3. 利用二进制与运算【&】，判断字符串是否已经出现过。比如当字符串还未出现时 00&10 = 00 ，已经有字符串出现时 11&10 = 10 此时结果不等于0
4. 二进制按位左移【<<】,比如 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. 总结

欢迎感兴趣的朋友关注我的订阅号“小院不小”，或点击下方二维码关注。我将多年开发中遇到的难点，以及一些有意思的功能，体会都会一一发布到我的订阅号中