Может ли кто-нибудь объяснить, как в этом коде используется сдвиг?

Question

Я решаю проблемы с примерами, одновременно пытаясь изучить Python% \ ... но проблема, с которой я столкнулась, имеет проблемы и решения на Java, поэтому я пытаюсь преобразовать между двумя языками. Я только что узнал, как работает бит-сдвиг, и я смотрел на этот код, пытаясь понять, что именно происходит здесь в строке 5 (и 8) ... Я попытался записать несколько примеров, просто проходя через код по строкам но почему-то это все еще не совсем очевидно для меня ... Не могли бы кто-нибудь прояснить?

Кроме того, это действительно странно для меня, что str.charAt(i) возвращает символ, насколько я понимаю, и тогда вы можете перейти к вычесть его из другого персонажа как номера ... Является ли применение int к характеру такой же, как в ord() Python?

Проблема: Реализация алгоритма для определения строки имеет все уникальные символы.

решение (в случае только с символами A-Z):

1 boolean isUniqueChars(String str){ 
2  int checker = 0 
3  for (int i = 0; i < str.length(); i++){ 
4   int val = str.charAt(i) - 'a'; 
5   if ((checker & (1 << val)) > 0){ 
6    return false; 
7   } 
8   checker |= (1 << val); 
9  } 
10  return true; 
11 } 

Answer 1

Конечно. Этот код действительно будет работать, только если str имеет в нем только строчные буквы.

checker - это 32-разрядное целое число, и вы используете 26 из 32 бит для записи присутствия конкретной буквы в str. Таким образом, бит 0 будет использоваться для записи присутствия a, бит 1 будет использоваться для записи присутствия b и т. Д. До бита 25, который будет использоваться для записи присутствия z.

Основным алгоритмом является работа через str, символ по характеру. Для каждого символа найдите соответствующий бит в checker. Если он уже установлен, этот символ должен появляться во второй раз, поэтому мы можем прекратить обработку и вернуть false. В противном случае установите этот бит.

Если вы дойдете до конца строки, не найдя дубликатов символов, верните true.

Магия находится в следующих шагах.

• Вычитание 'a' от каждого символа преобразует его в число от 0 до 25.
• Символ << является «сдвиг влево» оператор, который перемещает битовый шаблон число битов влево. Результатом этого является то, что 1 << val - это значение места для определенного бита (1, 2, 4, 8 и т. Д.).
• Символ & делает двоичный код AND, поэтому выражение checker & (1 << val) будет 0, если бит val очищен или равен 1 << val, если он установлен.
• Символ |= выполняет двоичный код OR и присваивает результат переменной слева. Таким образом, выражение checker |= (1 << val) устанавливает бит val.

Answer 2

Давайте попробуем более простой вариант:

boolean isUniqueChars(String str) { 
    boolean[] seen = new boolean[26]; 
    for (int i = 0; i < str.length(); i++) { 
     // convert char to 0-based offset 
     int index = str.charAt(i) - 'a'; 
     if (seen[index]) { 
      // this char was seen already 
      return false; 
     } 
     seen[index] = true; 
    } 
    // no duplicates found 
    return true; 
} 

Довольно straighforward, верно? Мы создаем логический массив, используя смещение символа как индекс, и проверяем каждый символ в строке, чтобы узнать, встретили ли мы его еще.Выставляемый вами код использует ту же логику, но вместо этого используется более эффективный бит.

(1 << val) превращает val в разрядный индекс. checker & (1 << val) отфильтровывает другие индексы, поэтому мы можем проверить только этот. (checker & (1 << val)) > 0 проверяет, есть ли значение в индексе. checker |= (1 << val) превращает бит в индекс. Вся другая логика идентична.

Answer 3

Во-первых, код будет работать только надежно, если строка ввода содержит буквы 'a' to 'z'.

Контроллер переменной 32 бит. Каждый бит в checker используется как флаг для указания наличия одного из 26 букв «a» - «z».

Линия

int val = str.charAt(i) - 'a'; 

преобразует символ хранящийся в индексе ул я в целое число, хранящемся в вале, путем вычитания значения символа «а» так. Да, я думаю, что у pascal есть функция Ord (''), которая делает то же самое.

a = 0 
b = 1 
c = 2 
etc 
etc 
etc 
z = 25 

код

(1 << val) 

сдвиги вал в соответствующее значение для его битовой позиции,

так

a = 0 = 1 
b = 1 = 2 
c = 2 = 4 
d = 3 = 8 
etc 
etc 
z = 25 = 33554432 

if ((checker & (1 << val)) > 0) 

определяет, если бит уже установлен в чекер, указывая дублирующий символ. Если это так, функция возвращает false.

еще

checker |= (1 << val) 

устанавливает бит в проверки через бинарный или петли, а затем круглый снова.