二進制妙用之位標(biāo)記

1. 使用背景

已知一個字符串 String s = "abcdefg"，需要判斷字符串中是否存在重復(fù)的字符。

2. 常規(guī)實現(xiàn)

根據(jù)Hashset特性判斷重復(fù)。

public?void?test2()?{
??String?s1?=?"abcadeeee";
??Set?s?=?new?HashSet();
??for?(int?i?=?0;?i?????if?(!s.add(s1.charAt(i)))?{
??????System.out.println("第["?+?i?+?"]位字符?"?+?s1.charAt(i)?+?"?已經(jīng)存在");
????}
??}
}

3. 二進制實現(xiàn)

實現(xiàn)原理有以下兩點

1. 同一個字符-‘a(chǎn)’得到的值一定相等
2. 將該值對應(yīng)的位置打上標(biāo)記，作為重復(fù)判斷的依據(jù)

所以，二進制的實現(xiàn)也可以換成數(shù)組來實現(xiàn)。但是，通過二進制實現(xiàn)可以大大減少內(nèi)存占用。

二進制可以實現(xiàn)原理如下

1. 初始一個值為0的整數(shù)。它對應(yīng)在計算機的存儲格式 00000000 00000000 00000000 00000000
2. 利用二進制或運算【|】，將對應(yīng)位置二進制轉(zhuǎn)換為1,比如 00 | 10 = 10，我們此此時就知道對應(yīng)索引值為1的字符已經(jīng)出現(xiàn)了。
3. 利用二進制與運算【&】，判斷字符串是否已經(jīng)出現(xiàn)過。比如當(dāng)字符串還未出現(xiàn)時 00&10 = 00 ，已經(jīng)有字符串出現(xiàn)時 11&10 = 10 此時結(jié)果不等于0
4. 二進制按位左移【<<】,比如 01<<1 = 10

最終代碼實現(xiàn)如下

//?author:herbert?date:20211022?wx:464884492
public?void?findRepeatChar(){
?String?s1?=?"abcadeeee";
??int?mark?=?0;
??for?(int?i?=?0;?i????Integer?bitIndex?=?s1.charAt(i)?-?'a';
???if?((mark?&?(1?<0)?{
????System.out.println("第["+i+"]位字符?"+s1.charAt(i)?+?"?已經(jīng)存在");
???}
???mark?=?mark|(1?<??}
}????

5. 總結(jié)

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