Понимание использования вектора бит в поиске уникального символа в строке

Question

У меня есть следующий код, который находит уникальные символы в строке с использованием битовых векторов. Предположим, что это набор символов 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 и AND'ing его проверка (инициализируется 0) и OR'ing его в блоке еще.

Answer 1

checker - 32-битное целое число, из которого мы назначаем наименьшее значение 26 для хранения флага для каждой буквы a-z. Мы можем использовать биты для этого, потому что письмо может быть неединственным только один раз.

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 уже имеет тот же бит. В этом случае мы возвращаем false, потому что письмо повторяется.

В случае, если новая буква найдена, нам нужно включить правильный бит в checker. Это то, что делает checker |= (1 << val);. Побитовый или оператор, |, включается бит в результате, если он включен в любом из операндов. Опять же, 1 << val имеет только один бит. Поэтому результат или будет реплицироваться checker и включить этот бит (независимо от того, был ли он уже включен).

Все операции, которые вы видите здесь, являются очень распространенными идиомами. Надеюсь, мое объяснение помогло вам в некотором роде, потому что вы почти наверняка увидите очень похожие вещи в любом простом двоичном коде.