瞭解在查找字符串中唯一字符時的位向量使用情況

我有以下代碼，它使用位向量查找字符串中的唯一字符。我們假設它是一個只有小寫字母的ASCII字符集。瞭解在查找字符串中唯一字符時的位向量使用情況

我很難理解下面的位向量的使用。即使在通過程序進行調試之後，並且在每次循環之後都要經歷變化。

// assuming that the characters range from a-z 
static boolean isUniqueBitVector(String str) { 
    int checker = 0; 

    for(int i = 0; i < str.length(); i++) { 
     int val = str.charAt(i) - 'a'; 

     if((checker & (1 << val)) > 0) { 
      return false; 
     } else { 
      checker |= (1 << val); 
     } 
    } 
    return true; 
}

什麼的目的向左1移位VAL（在串中的每個字符的INT表示）中並用檢查程序（初始化爲0）AND'ing的它和在else塊它中用OR。

來源

2017-02-12 Pha3drus

「我們認爲這是一個ASCII字符集，只能使用小寫字母。」好吧，但是更重要的是，你使用的是Java的'String'和'char'，它是Unicode小寫字母[Basic Latin]（http://www.unicode.org/charts/nameslist/index.html ）只有字母。 'if'''throw'參數驗證模式非常適合記錄和執行假設，如果不成立，則會使算法失效。 –

checker是一個32位整數，其中我們爲每個字母a-z分配最低的26個標誌。我們可以使用比特，因爲一個字母只能是非唯一的。

int val = str.charAt(i) - 'a';計算對應於當前字母的位的索引。這就是，輸入只包含a-z假設進來。val將爲零，且25.

之間的數字通常，(1 << val)是對應於所選擇信位。 <<是左移運算符。它用於將僅有一個位的1移動到左側的val位置。例如，1<<3將爲8.實際上，左移相當於乘以2的冪。

(checker & (1 << val))驗證所選位是否打開。 &運算符被稱爲按位和。它將兩個數字相結合，並將兩個都打開的位設置爲開。請記住，1 << val只有一個位打開。該結果和checker的唯一結果是非零，如果checker已經打開了相同的位。在這種情況下，我們會重複錯誤，因爲一封信已被重複。

如果找到了新字母，我們需要打開checker中的正確位。這是checker |= (1 << val);所做的。按位或運算符|在結果中打開一個位，如果它在任一操作數中打開。再次，1 << val只有一個位。因此，或將要複製checker的結果並打開該位（不管它是否已經打開）。

您在這裏看到的所有操作都是非常常見的成語。希望我的解釋能以某種方式爲你提供幫助，因爲在任何簡單的代碼中，你幾乎可以看到非常類似的東西。

來源

2017-02-12 00:41:38

瞭解在查找字符串中唯一字符時的位向量使用情況

回答

相關問題