二進制妙用之位標記

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. 總結

歡迎感興趣的朋友關注我的訂閱號“小院不小”，或點擊下方二維碼關注。我將多年開發中遇到的難點，以及一些有意思的功能，體會都會一一發布到我的訂閱號中