Новый для java - попытка понять: checker | = (1 << val)

Ответ 1

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

Вот подход.

Примечание:

1. В приведенном ниже коде мы будем предполагать, что строка имеет только нижний регистр от a до z. Это позволит нам использовать только один int.

2. Java целое число имеет размер 32

3. Количество строчных букв составляет 26

Таким образом, мы можем четко установить значение 0/1 (true или false) внутри одного целого числа в десятичная запись.

4. Это похоже на bool посещения [32]. bool использует 1 байт. Следовательно, вам нужно 32 байта для хранения bool посещенных [32].

5. Битовая маскировка - это оптимизация пространства.

Давайте начнем:

1. Вы перебираете все символы в строке.
2. Предположим, на i-й итерации вы нашли символ "b". Вы рассчитываете его 0 на основе индекса.

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

Для 'b' это 1. т.е. 98-97.

3. Теперь с помощью оператора сдвига влево мы находим значение 2 ^ 1 => 2.

(1 << val) // 1<<1 => 10(binary)

Теперь давайте посмотрим, как работает побитовая и works

0 & 0 -> 0
0 & 1 -> 0
1 & 0 -> 0
1 & 1 -> 1

Итак, с помощью кода ниже:

(checker & (1 << val))

Мы проверяем, если проверка [val] == 0. Предположим, мы уже столкнулись с "б".

check = 0000 0000 0000 0000 0000 1000 1000 0010   &  
'b'   = 0000 0000 0000 0000 0000 0000 0000 0010 
 ----------------------------------------------
result= 0000 0000 0000 0000 0000 0000 0000 0010

т.е. десятичное value = 2, которое> 0

Итак, вы наконец поняли эту часть.

 if ((checker & (1 << val)) > 0) 
                return false;

4. Теперь, если "b" не встречалось, тогда мы устанавливаем второй бит проверки, используя побитовое ИЛИ.

(Эта часть называется битовой маскировкой.)

ИЛИ Таблица правды

0 | 0 -> 0
0 | 1 -> 1
1 | 0 -> 1
1 | 1 -> 1

Так

check = 0000 0000 0000 0000 0000 1000 1000 0000   |  
'b'   = 0000 0000 0000 0000 0000 0000 0000 0010 
 ----------------------------------------------
result= 0000 0000 0000 0000 0000 1000 1000 0010

Так что это упрощает эту часть:

checker |= (1 << val);  // checker = checker |  (1 << val);

Я надеюсь, что это помогло кому-то!

Ответ 2

Похоже, я опоздал на вечеринку, но позвольте мне попытаться объяснить это.

Прежде всего, AND, т.е. & Операция:

0 & 0 = 0
1 & 0 = 0
0 & 1 = 0
1 & 1 = 1

Таким образом, в основном, если вам дают немного, и вы хотите выяснить, является ли его 1 или 0, вы просто & это с 1. Если результат равен 1, то у вас было 1, в противном случае у вас было 0. Мы будем использовать это Свойство & ниже.

ИЛИ то есть | операция

0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 1  

В общем, если вам дают немного, и вы хотите что-то с ним сделать, чтобы вывод всегда был равен 1, тогда вы делаете | 1 с этим.

Теперь в Java тип int составляет 4 байта, т.е. 32 бита. Таким образом, мы можем использовать сам int как структуру данных для хранения 32 состояний или логических значений в более простых терминах, поскольку бит может быть либо 0, либо 1, т.е. Ложным или истинным. Поскольку мы предполагаем, что наша строка состоит только из строчных букв, у нас внутри int достаточно места для хранения логического значения для каждого из 26 символов!

Итак, сначала мы инициализируем нашу структуру данных, которую мы называем checker 0, что является не чем иным, как 32 нулями: 0000000000000000000000.

Все идет нормально?

Теперь мы просматриваем нашу строку для каждого символа, сначала мы получаем целочисленное представление символа.

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

Мы вычитаем из него a потому что мы хотим, чтобы наше целое число было основано на 0. Так что, если vals:

a = 0 i.e. '0000000000000000000000'
b = 1 i.e. '0000000000000000000001'
c = 2 i.e. '0000000000000000000010'
d = 4 i.e. '0000000000000000000100'

Теперь, как показано выше, a - это 32 ноля, но остальные символы имеют один ноль и 31 ноль. Поэтому, когда мы используем эти символы, мы left shift каждый из них на 1, т.е. (1 << val), поэтому у каждого из них есть один 1-битный и 31 нулевой бит:

a = 1 i.e. '0000000000000000000001'
b = 2 i.e. '0000000000000000000010'
c = 4 i.e. '0000000000000000000100'
d = 8 i.e. '0000000000000000001000'

Мы закончили с настройкой. Сейчас мы делаем 2 вещи:

1. Сначала предположим, что все символы разные. Для каждого символа, с которым мы сталкиваемся, мы хотим, чтобы в нашей структуре данных, т.е. в контролере, было 1 для этого символа. Поэтому мы используем наше свойство OR, описанное выше, чтобы сгенерировать 1 в нашей структуре данных, и, следовательно, мы делаем:

   checker = checker | (1 << val);
   

Таким образом, программа проверки хранит 1 для каждого встречаемого нами персонажа.

2. Теперь мы подошли к той части, где персонажи могут повторяться. Поэтому перед тем, как выполнить шаг 1, мы хотим убедиться, что у контролера уже нет 1 в позиции, соответствующей текущему символу. Итак, мы проверяем значение

   checker & (1 << val)
   

Таким образом, с помощью свойства AND, описанного выше, если мы получим 1 из этой операции, то у средства проверки уже было 1 в этой позиции, что означает, что мы должны были встретить этот символ раньше. Поэтому мы немедленно возвращаем false.

Это оно. Если все наши & проверки возвращают 0, мы, наконец, возвращаем true, то есть повторений символов не было.

Ответ 3

1 << val совпадает с 2 to the degree of val. Таким образом, это число, которое имеет только один в своем двоичном представлении (один находится в позиции val+1, если вы считаете, правая часть номера слева).

a |= b означает в основном это: установить в a все бинарные флаги/единицы из
двоичное представление b (и сохранить те в a, которые уже были установлены).

Ответ 4

Это устанавливает бит val'th справа на 1.

1 << val - это сдвинутое влево время val. Остальное значение равно 0.

Линия эквивалентна checker = checker | (1 << val). Очередь с 0 бит ничего не делает, поскольку x | 0 == x. Но или с 1 всегда приводит к 1. Таким образом, это превращается (только) в бит.

Оператор if аналогичен, поскольку он проверяет, уже ли бит уже включен. Значение маски 1 << val - это все 0s, за исключением одного 1. И-ing с 0 всегда производит 0, поэтому большинство бит в результате равны 0. x и 1 == x, поэтому это будет отличным от нуля, только если это бит в val не равен 0.

Ответ 5

checker |= (1 << val) совпадает с checker = checker | (1 << val). << - это сдвиг влево, как вы сказали. 1 << val означает, что a 1 сдвинуто val цифры влево. Пример: 1 << 4 - 1000. Смещение левого бита такое же, как умноженное на 2. 4 сдвига левого бита 4 раза 1, умноженное на 2.

1 * 2 = 2 (1)
2 * 2 = 4 (2)
4 * 2 = 8 (3)
8 * 2 = 16 = (4)

| побит или. Это похоже на нормальный или на один бит. Если у нас более одного бита, вы выполняете операцию или для каждого бита. Пример:

110 | 011 = 111

Вы можете использовать это для установки флагов (сделать бит 1).

Условие if похоже на это, но имеет оператор &, который является поразменным и. Он в основном используется для маскировки двоичного числа.

Пример:

110 | 100 = 100

Итак, ваш код просто проверяет, установлен ли бит в месте val 1, затем return false, в противном случае установите бит в месте val равным 1.

Ответ 6

Другие ответы объясняют использование операторов кодирования, но я не думаю, что они касаются логики этого кода.

В основном код 1 << val смещает 1 в двоичном номере на уникальное место для каждого символа, например

a-0001 b-0010 c-0100 d-1000

Как вы можете заметить для разных символов, место 1 отличается от

checker = checker | (1 << val)

checker здесь Oring (в основном сохраняя 1 в том же месте, что и в 1<<val) Итак, контролер знает, какие символы уже были приняты Пусть говорят, что после появления a, b, c, d checker будет выглядеть так 0000 1111

наконец,

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

проверяет, не был ли этот символ ранее, если да возвращает false. Чтобы объяснить, вы должны немного узнать о операции AND (&).

• 1 & 1- > 1
• 0 & 0- > 0
• 1 & 0- > 0

Итак, в настоящее время в чеке есть 1 в местах, чьи соответствующие символы уже имели место единственным способом выражения внутри оператора if если символ встречается дважды, что приводит к 1 & 1- > 1 > 0

Ответ 7

Это означает, что двоичный OR для значений checker и (1 << val) (который равен 1, сдвинутый влево val раза) и сохранит вновь созданное значение в checker.

Левый сдвиг (<<)

Сдвиньте все двоичные цифры на одно место. Эффективно поднимите число до 2 на мощность val или умножьте число на 2 val раз.

Bitwise ИЛИ (|)

В каждом двоичном символе как левого, так и правого значений, если на месте любого из двух чисел есть 1, сохраните его.

Расширенное задание (|=)

Сделайте операцию (в этом случае побитовое ИЛИ) и присвойте значение левой переменной. Это работает со многими операторами, такими как: -

• a += b, добавьте a в b и сохраните новое значение в a.
• a *= b, умножьте a на b и сохраните новое значение в a.

Ответ 8

Побитовый сдвиг работает следующим образом:

Пример: a = 15 (представление бит: 0000 1111)

Для работы: a<<2

Он будет вращать представление битов на 2 позиции в левом направлении.

Итак a<<2 есть 0011 1100 = 0*2^7+0*2^6+1*2^5+1*2^4+1*2^3+1*2^2+0*2^1+0*2^0 = 1*2^5+1*2^4+1*2^3+1*2^2 = 32+18+8+4=60

следовательно a<<2 = 60

Теперь:

checker & (1<<val) всегда будет больше 0, если 1 уже присутствует в позиции 1<<val.

Следовательно, мы можем вернуть false.

В противном случае мы назначим значение проверки 1 на 1

Ответ 9

Я работаю над алгоритмом, и здесь я заметил, что это тоже сработает. Это облегчает понимание алгоритма, когда вы выполняете его вручную:

public static boolean isUniqueChars(String str) {
    if (str.length() > 26) { // Only 26 characters
        return false;
    }
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        int newValue = Math.pow(2, val) // int newValue = 1 << val
        if ((checker & newValue) > 0) return false;
        checker += newValue // checker |= newValue
    }
    return true;

Когда мы получим значение val (0-25), мы можем либо сдвинуть 1 вправо на значение val, либо мы могли бы использовать мощность 2s.

Кроме того, пока значение ((checker & newValue) > 0) равно false, новое значение checker генерируется, когда мы суммируем старое значение checker и newValue.