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

Я не понимаю, как будет работать битовый вектор (не слишком знаком с битовыми векторами). Вот код, данный. Может кто-нибудь, пожалуйста, проведите меня через это?

public static boolean isUniqueChars(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;
        checker |= (1 << val);
    }
    return true;
}

В частности, что checkerделает?

int checkerиспользуется здесь как хранилище для битов. Каждый бит в целочисленном значении можно рассматривать как флаг, поэтому в конечном итоге intэто массив битов (флаг). Каждый бит в вашем коде указывает, был ли найден символ с индексом бита в строке или нет. Вы можете использовать битовый вектор по той же причине вместо int. Между ними есть два отличия:

• Размер . intимеет фиксированный размер, обычно 4 байта, что означает 8 * 4 = 32 бита (флаги). Битовый вектор обычно может быть разного размера, или вы должны указать размер в конструкторе.

• API . С битовыми векторами вам будет легче читать код, вероятно, что-то вроде этого:

  vector.SetFlag(4, true); // set flag at index 4 as true

  у intвас будет битовый логический код более низкого уровня:

  checker |= (1 << 5); // set flag at index 5 to true

Также, вероятно, intможет быть немного быстрее, потому что операции с битами очень низкого уровня и могут быть выполнены как есть CPU. BitVector позволяет писать чуть меньше загадочного кода, а также может хранить больше флагов.

Для дальнейшего использования: битовый вектор также известен как bitSet или bitArray. Вот несколько ссылок на эту структуру данных для разных языков / платформ:

• CPP: BitSet
• Java: BitSet
• C #: BitVector32 и BitArray

У меня есть подозрение, что вы получили этот код из той же книги, которую я читаю ... Сам код здесь не настолько загадочный, как операторы- | =, &, <<, которые обычно не используются мы, неспециалист, - автор не удосужился потратить дополнительное время на объяснение процесса и на то, какова действительная механика, которая здесь задействована. Я был доволен предыдущим ответом на эту тему в начале, но только на абстрактном уровне. Я вернулся к этому, потому что чувствовал, что нужно более конкретное объяснение - его отсутствие всегда вызывает у меня неприятное чувство.

Этот оператор << является левым побитовым сдвигом, он принимает двоичное представление этого числа или операнда и сдвигает его на любое количество мест, указанных операндом или числом справа, как в десятичных числах только в двоичных файлах. Мы умножаем на основание 2 - когда мы двигаемся вверх, но во многих местах не основание 10 - так что число справа - это показатель степени, а число слева - это основание, кратное 2.

Этот оператор | = берет операнд слева и / или его с операндом справа - и этот - '&' и биты обоих операндов слева и справа от него.

Итак, у нас есть хеш-таблица, которая хранится в 32-битном двоичном числе каждый раз, когда проверяющий получает or'd ( checker |= (1 << val)) с заданным двоичным значением буквы, соответствующий его бит, для которого устанавливается значение true. Значение символа равно and'd с помощью checker ( checker & (1 << val)) > 0) - если оно больше 0, мы знаем, что у нас есть дублирование, - потому что два идентичных бита, установленные в true и имеющие вместе, вернут true или '1' '.

Есть 26 двоичных разрядов, каждое из которых соответствует строчной букве - автор сказал, что строка содержит только строчные буквы - и это потому, что у нас осталось только 6 (в 32-битном целом) месте для использования - и чем мы столкнуться

00000000000000000000000000000001 a 2^0

00000000000000000000000000000010 b 2^1

00000000000000000000000000000100 c 2^2

00000000000000000000000000001000 d 2^3

00000000000000000000000000010000 e 2^4

00000000000000000000000000100000 f 2^5

00000000000000000000000001000000 g 2^6

00000000000000000000000010000000 h 2^7

00000000000000000000000100000000 i 2^8

00000000000000000000001000000000 j 2^9

00000000000000000000010000000000 k 2^10

00000000000000000000100000000000 l 2^11

00000000000000000001000000000000 m 2^12

00000000000000000010000000000000 n 2^13

00000000000000000100000000000000 o 2^14

00000000000000001000000000000000 p 2^15

00000000000000010000000000000000 q 2^16

00000000000000100000000000000000 r 2^17

00000000000001000000000000000000 s 2^18

00000000000010000000000000000000 t 2^19

00000000000100000000000000000000 u 2^20

00000000001000000000000000000000 v 2^21

00000000010000000000000000000000 w 2^22

00000000100000000000000000000000 x 2^23

00000001000000000000000000000000 y 2^24

00000010000000000000000000000000 z 2^25

Итак, для входной строки 'azya', по мере продвижения по шагам

строка «а»

a      =00000000000000000000000000000001
checker=00000000000000000000000000000000

checker='a' or checker;
// checker now becomes = 00000000000000000000000000000001
checker=00000000000000000000000000000001

a and checker=0 no dupes condition

строка 'az'

checker=00000000000000000000000000000001
z      =00000010000000000000000000000000

z and checker=0 no dupes 

checker=z or checker;
// checker now becomes 00000010000000000000000000000001  

строка 'azy'

checker= 00000010000000000000000000000001    
y      = 00000001000000000000000000000000 

checker and y=0 no dupes condition 

checker= checker or y;
// checker now becomes = 00000011000000000000000000000001

Строка 'Azya'

checker= 00000011000000000000000000000001
a      = 00000000000000000000000000000001

a and checker=1 we have a dupe

Теперь он объявляет дубликат

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

public static boolean isUniqueChars(String str) {

    /*
    checker is the bit array, it will have a 1 on the character index that
    has appeared before and a 0 if the character has not appeared, you
    can see this number initialized as 32 0 bits:
    00000000 00000000 00000000 00000000
     */
    int checker = 0;

    //loop through each String character
    for (int i = 0; i < str.length(); ++i) {
        /*
        a through z in ASCII are charactets numbered 97 through 122, 26 characters total
        with this, you get a number between 0 and 25 to represent each character index
        0 for 'a' and 25 for 'z'

        renamed 'val' as 'characterIndex' to be more descriptive
         */
        int characterIndex = str.charAt(i) - 'a'; //char 'a' would get 0 and char 'z' would get 26

        /*
        created a new variable to make things clearer 'singleBitOnPosition'

        It is used to calculate a number that represents the bit value of having that 
        character index as a 1 and the rest as a 0, this is achieved
        by getting the single digit 1 and shifting it to the left as many
        times as the character index requires
        e.g. character 'd'
        00000000 00000000 00000000 00000001
        Shift 3 spaces to the left (<<) because 'd' index is number 3
        1 shift: 00000000 00000000 00000000 00000010
        2 shift: 00000000 00000000 00000000 00000100
        3 shift: 00000000 00000000 00000000 00001000

        Therefore the number representing 'd' is
        00000000 00000000 00000000 00001000

         */
        int singleBitOnPosition = 1 << characterIndex;

        /*
        This peforms an AND between the checker, which is the bit array
        containing everything that has been found before and the number
        representing the bit that will be turned on for this particular
        character. e.g.
        if we have already seen 'a', 'b' and 'd', checker will have:
        checker = 00000000 00000000 00000000 00001011
        And if we see 'b' again:
        'b' = 00000000 00000000 00000000 00000010

        it will do the following:
        00000000 00000000 00000000 00001011
        & (AND)
        00000000 00000000 00000000 00000010
        -----------------------------------
        00000000 00000000 00000000 00000010

        Since this number is different than '0' it means that the character
        was seen before, because on that character index we already have a 
        1 bit value
         */
        if ((checker & singleBitOnPosition) > 0) {
            return false;
        }

        /* 
        Remember that 
        checker |= singleBitOnPosition is the same as  
        checker = checker | singleBitOnPosition
        Sometimes it is easier to see it expanded like that.

        What this achieves is that it builds the checker to have the new 
        value it hasnt seen, by doing an OR between checker and the value 
        representing this character index as a 1. e.g.
        If the character is 'f' and the checker has seen 'g' and 'a', the 
        following will happen

        'f' = 00000000 00000000 00000000 00100000
        checker(seen 'a' and 'g' so far) = 00000000 00000000 00000000 01000001

        00000000 00000000 00000000 00100000
        | (OR)
        00000000 00000000 00000000 01000001
        -----------------------------------
        00000000 00000000 00000000 01100001

        Therefore getting a new checker as 00000000 00000000 00000000 01100001

         */
        checker |= singleBitOnPosition;
    }
    return true;
}

Я также предполагаю, что ваш пример взят из книги « Взлом кода», и мой ответ связан с этим контекстом.

Чтобы использовать этот алгоритм для решения проблемы, мы должны признать, что мы собираемся передавать только символы от a до z (строчные буквы).

Поскольку существует только 26 букв, и они правильно отсортированы в используемой нами таблице кодирования, это гарантирует нам, что все потенциальные различия str.charAt(i) - 'a'будут меньше 32 (размер переменной int checker).

Как объяснил Snowbear, мы собираемся использовать checkerпеременную как массив битов. Давайте рассмотрим пример:

Скажем str equals "test"

• Первый проход (я = т)

проверка == 0 (00000000000000000000000000000000)

In ASCII, val = str.charAt(i) - 'a' = 116 - 97 = 19
What about 1 << val ?
1          == 00000000000000000000000000000001
1 << 19    == 00000000000010000000000000000000
checker |= (1 << val) means checker = checker | (1 << val)
so checker = 00000000000000000000000000000000 | 00000000000010000000000000000000
checker == 524288 (00000000000010000000000000000000)

• Второй проход (я = е)

проверка == 524288 (00000000000010000000000000000000)

val = 101 - 97 = 4
1          == 00000000000000000000000000000001
1 << 4     == 00000000000000000000000000010000
checker |= (1 << val) 
so checker = 00000000000010000000000000000000 | 00000000000000000000000000010000
checker == 524304 (00000000000010000000000000010000)

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

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

Надеюсь, поможет

Есть несколько отличных ответов, уже предоставленных выше. Поэтому я не хочу повторять то, что уже все сказано. Но я хотел добавить пару вещей, чтобы помочь с вышеупомянутой программой, так как я только что работал над той же самой программой и у меня было несколько вопросов, но потратив некоторое время, у меня есть больше ясности в этой программе.

Прежде всего, «проверка» используется для отслеживания символа, который уже пройден в строке, чтобы увидеть, есть ли повторяющиеся символы.

Теперь «checker» является типом данных int, поэтому он может иметь только 32 бита или 4 байта (в зависимости от платформы), поэтому эта программа может корректно работать только для набора символов в диапазоне 32 символа. По этой причине эта программа вычитает «a» из каждого символа, чтобы эта программа работала только для строчных букв. Однако если вы смешаете символы нижнего и верхнего регистров, это не сработает.

Кстати, если вы не вычитаете «a» из каждого символа (см. Оператор ниже), то эта программа будет работать правильно только для строки с символами верхнего регистра или строки только с символами нижнего регистра. Таким образом, область действия вышеуказанной программы увеличивается от букв нижнего регистра до символов верхнего регистра, но их нельзя смешивать вместе.

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

Однако я хотел написать общую программу с использованием побитовой операции, которая должна работать с любыми символами ASCII, не беспокоясь о верхнем регистре, нижнем регистре, числах или любых специальных символах. Для этого наш «чекер» должен быть достаточно большим для хранения 256 символов (размер набора символов ASCII). Но int в Java не будет работать, поскольку он может хранить только 32 бита. Следовательно, в приведенной ниже программе я использую класс BitSet, доступный в JDK, который может передавать любой определенный пользователем размер при создании экземпляра объекта BitSet.

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

public static boolean isUniqueStringUsingBitVectorClass(String s) {

    final int ASCII_CHARACTER_SET_SIZE = 256;

    final BitSet tracker = new BitSet(ASCII_CHARACTER_SET_SIZE);

    // if more than  256 ASCII characters then there can't be unique characters
    if(s.length() > 256) {
        return false;
    }

    //this will be used to keep the location of each character in String
    final BitSet charBitLocation = new BitSet(ASCII_CHARACTER_SET_SIZE);

    for(int i = 0; i < s.length(); i++) {

        int charVal = s.charAt(i);
        charBitLocation.set(charVal); //set the char location in BitSet

        //check if tracker has already bit set with the bit present in charBitLocation
        if(tracker.intersects(charBitLocation)) {
            return false;
        }

        //set the tracker with new bit from charBitLocation
        tracker.or(charBitLocation);

        charBitLocation.clear(); //clear charBitLocation to store bit for character in the next iteration of the loop

    }

    return true;

}

Чтение ответа Ивана выше действительно помогло мне, хотя я бы сформулировал это несколько иначе.

<<В (1 << val)это бит - оператор сдвига. Он берет 1(который в двоичном виде представлен как 000000001, с тем количеством предшествующих нулей, сколько вам нравится / выделяется памятью) и сдвигает его влево на valпробелы. Поскольку мы предполагаем только az и вычитаем aкаждый раз, каждая буква будет иметь значение 0-25, которое будет индексом этой буквы справа в checkerлогическом представлении целого числа, поскольку мы будем перемещать 1влево в checker valразы.

В конце каждой проверки мы видим |=оператора. Это объединяет два двоичных числа, заменяя все 0на s 1, если a 1существует в любом операнде с этим индексом. Здесь это означает, что там, где 1существует a (1 << val), оно 1будет скопировано checker, а все checkerсуществующие 1 будут сохранены.

Как вы, вероятно, можете догадаться, здесь 1функции в качестве логического флага для истины. Когда мы проверяем, представлен ли уже символ в строке, мы сравниваем checker, который на данный момент является массивом логических флагов ( 1значений) по индексам символов, которые уже были представлены, с тем, что по сути является массивом логические значения с 1флагом в индексе текущего символа.

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

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

Простое объяснение (с кодом JS ниже)

• Целочисленная переменная на машинный код - это 32-битный массив
• Все битовые операции 32-bit
• Они не зависят от архитектуры ОС / ЦП или выбранной системы счисления языка, например, DEC64для JS.
• Такое дублирование находка подход аналогичен хранение символов в массиве размера 32 , где мы устанавливаем 0thиндекс , если мы находим aв строке, 1stдля bи так далее.
• Повторяющийся символ в строке будет занят соответствующим битом или, в этом случае, будет установлен в 1.
• Иван уже объяснил : как этот расчет индекса работает в предыдущем ответе .

Краткое описание операций:

• Выполнить И операцию между checker& indexперсонажа
• Внутренне оба Int-32-Arrays
• Это битовая операция между этими двумя.
• Проверьте ifвывод операции был1
• если output == 1
  • Эта checkerпеременная имеет определенный индексный бит, установленный в обоих массивах
  • Таким образом, это дубликат.
• если output == 0
  • Этот персонаж до сих пор не найден
  • Выполните операцию ИЛИ между checker& indexсимвола
  • Таким образом, обновляя индексный бит до 1
  • Назначьте вывод checker

Предположения:

• Мы предполагали, что получим все строчные буквы
• И этого размера 32 достаточно
• Следовательно, мы начали наш индекс, считая с 96 в качестве контрольной точки, учитывая код ascii для ais97

Ниже приведен исходный код JavaScript .

function checkIfUniqueChars (str) {

    var checker = 0; // 32 or 64 bit integer variable 

    for (var i = 0; i< str.length; i++) {
        var index = str[i].charCodeAt(0) - 96;
        var bitRepresentationOfIndex = 1 << index;

        if ( (checker & bitRepresentationOfIndex) > 1) {
            console.log(str, false);
            return false;
        } else {
            checker = (checker | bitRepresentationOfIndex);
        }
    }
    console.log(str, true);
    return true;
}

checkIfUniqueChars("abcdefghi");  // true
checkIfUniqueChars("aabcdefghi"); // false
checkIfUniqueChars("abbcdefghi"); // false
checkIfUniqueChars("abcdefghii"); // false
checkIfUniqueChars("abcdefghii"); // false

Обратите внимание, что в JS, несмотря на то, что целые числа имеют 64 бита, битовая операция всегда выполняется на 32 битах.

Пример: если строка aaто:

// checker is intialized to 32-bit-Int(0)
// therefore, checker is
checker= 00000000000000000000000000000000

я = 0

str[0] is 'a'
str[i].charCodeAt(0) - 96 = 1

checker 'AND' 32-bit-Int(1) = 00000000000000000000000000000000
Boolean(0) == false

// So, we go for the '`OR`' operation.

checker = checker OR 32-bit-Int(1)
checker = 00000000000000000000000000000001

я = 1

str[1] is 'a'
str[i].charCodeAt(0) - 96 = 1

checker= 00000000000000000000000000000001
a      = 00000000000000000000000000000001

checker 'AND' 32-bit-Int(1) = 00000000000000000000000000000001
Boolean(1) == true
// We've our duplicate now

Давайте разберем код построчно.

int checker = 0; Мы инициируем проверку, которая поможет нам найти повторяющиеся значения.

int val = str.charAt (i) - 'a'; Мы получаем значение ASCII символа в i-й позиции строки и вычитаем его из значения ASCII 'a'. Поскольку предполагается, что строка содержит только символы младшего разряда, количество символов ограничено 26. Таким образом, значение 'val' всегда будет> = 0.

if ((checker & (1 << val))> 0) возвращает false;

проверка | = (1 << val);

Теперь это сложная часть. Давайте рассмотрим пример со строкой «abcda». В идеале это должно вернуть false.

Для цикла итерации 1:

Checker: 00000000000000000000000000000000

val: 97-97 = 0

1 << 0: 00000000000000000000000000000001

checker & (1 << val): 00000000000000000000000000000000 не> 0

Отсюда проверка: 00000000000000000000000000000001

Для цикла итерации 2:

Checker: 00000000000000000000000000000001

val: 98-97 = 1

1 << 0: 00000000000000000000000000000010

checker & (1 << val): 00000000000000000000000000000000 не> 0

Отсюда проверка: 00000000000000000000000000000011

Для цикла итерации 3:

Checker: 00000000000000000000000000000011

val: 99-97 = 0

1 << 0: 00000000000000000000000000000100

checker & (1 << val): 00000000000000000000000000000000 не> 0

Отсюда проверка: 00000000000000000000000000000111

Для цикла итерации 4:

Checker: 00000000000000000000000000000111

val: 100-97 = 0

1 << 0: 00000000000000000000000000001000

checker & (1 << val): 00000000000000000000000000000000 не> 0

Отсюда проверка: 00000000000000000000000000001111

Для цикла итерации 5:

Checker: 00000000000000000000000000001111

val: 97-97 = 0

1 << 0: 00000000000000000000000000000001

checker & (1 << val): 00000000000000000000000000000001 равно> 0

Следовательно, верните ложь.

public static void main (String[] args)
{
    //In order to understand this algorithm, it is necessary to understand the following:

    //int checker = 0;
    //Here we are using the primitive int almost like an array of size 32 where the only values can be 1 or 0
    //Since in Java, we have 4 bytes per int, 8 bits per byte, we have a total of 4x8=32 bits to work with

    //int val = str.charAt(i) - 'a';
    //In order to understand what is going on here, we must realize that all characters have a numeric value
    for (int i = 0; i < 256; i++)
    {
        char val = (char)i;
        System.out.print(val);
    }

    //The output is something like:
    //             !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ ¡¢£¤¥¦§¨©ª«¬­®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ
    //There seems to be ~15 leading spaces that do not copy paste well, so I had to use real spaces instead

    //To only print the characters from 'a' on forward:
    System.out.println();
    System.out.println();

    for (int i=0; i < 256; i++)
    {
        char val = (char)i;
        //char val2 = val + 'a'; //incompatible types. required: char found: int
        int val2 = val + 'a';  //shift to the 'a', we must use an int here otherwise the compiler will complain
        char val3 = (char)val2;  //convert back to char. there should be a more elegant way of doing this.
        System.out.print(val3);
    }

    //Notice how the following does not work:
    System.out.println();
    System.out.println();

    for (int i=0; i < 256; i++)
    {
        char val = (char)i;
        int val2 = val - 'a';
        char val3 = (char)val2;
        System.out.print(val3);
    }
    //I'm not sure why this spills out into 2 lines:
    //EDIT I cant seem to copy this into stackoverflow!

    System.out.println();
    System.out.println();

    //So back to our original algorithm:
    //int val = str.charAt(i) - 'a';
    //We convert the i'th character of the String to a character, and shift it to the right, since adding shifts to the right and subtracting shifts to the left it seems

    //if ((checker & (1 << val)) > 0) return false;
    //This line is quite a mouthful, lets break it down:
    System.out.println(0<<0);
    //00000000000000000000000000000000
    System.out.println(0<<1);
    //00000000000000000000000000000000
    System.out.println(0<<2);
    //00000000000000000000000000000000
    System.out.println(0<<3);
    //00000000000000000000000000000000
    System.out.println(1<<0);
    //00000000000000000000000000000001
    System.out.println(1<<1);
    //00000000000000000000000000000010 == 2
    System.out.println(1<<2);
    //00000000000000000000000000000100 == 4
    System.out.println(1<<3);
    //00000000000000000000000000001000 == 8
    System.out.println(2<<0);
    //00000000000000000000000000000010 == 2
    System.out.println(2<<1);
    //00000000000000000000000000000100 == 4
    System.out.println(2<<2);
    // == 8
    System.out.println(2<<3);
    // == 16
    System.out.println("3<<0 == "+(3<<0));
    // != 4 why 3???
    System.out.println(3<<1);
    //00000000000000000000000000000011 == 3
    //shift left by 1
    //00000000000000000000000000000110 == 6
    System.out.println(3<<2);
    //00000000000000000000000000000011 == 3
    //shift left by 2
    //00000000000000000000000000001100 == 12
    System.out.println(3<<3);
    // 24

    //It seems that the -  'a' is not necessary
    //Back to if ((checker & (1 << val)) > 0) return false;
    //(1 << val means we simply shift 1 by the numeric representation of the current character
    //the bitwise & works as such:
    System.out.println();
    System.out.println();
    System.out.println(0&0);    //0
    System.out.println(0&1);       //0
    System.out.println(0&2);          //0
    System.out.println();
    System.out.println();
    System.out.println(1&0);    //0
    System.out.println(1&1);       //1
    System.out.println(1&2);          //0
    System.out.println(1&3);             //1
    System.out.println();
    System.out.println();
    System.out.println(2&0);    //0
    System.out.println(2&1);       //0   0010 & 0001 == 0000 = 0
    System.out.println(2&2);          //2  0010 & 0010 == 2
    System.out.println(2&3);             //2  0010 & 0011 = 0010 == 2
    System.out.println();
    System.out.println();
    System.out.println(3&0);    //0    0011 & 0000 == 0
    System.out.println(3&1);       //1  0011 & 0001 == 0001 == 1
    System.out.println(3&2);          //2  0011 & 0010 == 0010 == 2, 0&1 = 0 1&1 = 1
    System.out.println(3&3);             //3 why?? 3 == 0011 & 0011 == 3???
    System.out.println(9&11);   // should be... 1001 & 1011 == 1001 == 8+1 == 9?? yay!

    //so when we do (1 << val), we take 0001 and shift it by say, 97 for 'a', since any 'a' is also 97

    //why is it that the result of bitwise & is > 0 means its a dupe?
    //lets see..

    //0011 & 0011 is 0011 means its a dupe
    //0000 & 0011 is 0000 means no dupe
    //0010 & 0001 is 0011 means its no dupe
    //hmm
    //only when it is all 0000 means its no dupe

    //so moving on:
    //checker |= (1 << val)
    //the |= needs exploring:

    int x = 0;
    int y = 1;
    int z = 2;
    int a = 3;
    int b = 4;
    System.out.println("x|=1 "+(x|=1));  //1
    System.out.println(x|=1);     //1
    System.out.println(x|=1);      //1
    System.out.println(x|=1);       //1
    System.out.println(x|=1);       //1
    System.out.println(y|=1); // 0001 |= 0001 == ?? 1????
    System.out.println(y|=2); // ??? == 3 why??? 0001 |= 0010 == 3... hmm
    System.out.println(y);  //should be 3?? 
    System.out.println(y|=1); //already 3 so... 0011 |= 0001... maybe 0011 again? 3?
    System.out.println(y|=2); //0011 |= 0010..... hmm maybe.. 0011??? still 3? yup!
    System.out.println(y|=3); //0011 |= 0011, still 3
    System.out.println(y|=4);  //0011 |= 0100.. should be... 0111? so... 11? no its 7
    System.out.println(y|=5);  //so we're at 7 which is 0111, 0111 |= 0101 means 0111 still 7
    System.out.println(b|=9); //so 0100 |= 1001 is... seems like xor?? or just or i think, just or... so its 1101 so its 13? YAY!

    //so the |= is just a bitwise OR!
}

public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a';  //the - 'a' is just smoke and mirrors! not necessary!
        if ((checker & (1 << val)) > 0) return false;
        checker |= (1 << val);
    }
    return true;
}

public static boolean is_unique(String input)
{
    int using_int_as_32_flags = 0;
    for (int i=0; i < input.length(); i++)
    {
        int numeric_representation_of_char_at_i = input.charAt(i);
        int using_0001_and_shifting_it_by_the_numeric_representation = 1 << numeric_representation_of_char_at_i; //here we shift the bitwise representation of 1 by the numeric val of the character
        int result_of_bitwise_and = using_int_as_32_flags & using_0001_and_shifting_it_by_the_numeric_representation;
        boolean already_bit_flagged = result_of_bitwise_and > 0;              //needs clarification why is it that the result of bitwise & is > 0 means its a dupe?
        if (already_bit_flagged)
            return false;
        using_int_as_32_flags |= using_0001_and_shifting_it_by_the_numeric_representation;
    }
    return true;
}

Предыдущие сообщения хорошо объясняют, что делает блок кода, и я хочу добавить свое простое решение с использованием структуры данных BitSet java:

private static String isUniqueCharsUsingBitSet(String string) {
  BitSet bitSet =new BitSet();
    for (int i = 0; i < string.length(); ++i) {
        int val = string.charAt(i);
        if(bitSet.get(val)) return "NO";
        bitSet.set(val);
    }
  return "YES";
}

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

Как я понял, используя Javascript. Предполагая вводvar inputChar = "abca"; //find if inputChar has all unique characters

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

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

Над строкой Находит двоичное значение первого символа в inputChar, который является a , a = 97 в ascii, затем преобразование 97 в двоичный код становится 1100001 .

В JavaScript, например: "a".charCodeAt().toString(2) возвращает 1100001

checker = 0 // двоичное 32-битное представление = 0000000000000000000000000

checker = 1100001 | checker; // проверка становится 1100001 (в 32-битном представлении она становится 000000000 ..... 00001100001)

Но я хочу, чтобы моя битовая маска ( int checker) устанавливала только один бит, а проверка - 1100001

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

Теперь приведенный выше код пригодится. Я просто вычитаю 97 всегда (ASCII val из)

val = 0; // 97 - 97  Which is  a - a
val = 1; // 98 - 97 Which is b - a
val = 1;  // 99 - 97 Which is c - a

Позволяет использовать valкоторый сбрасывается

Строка 5 и Строка 6 хорошо объяснены @Ivan ответ

На всякий случай, если кто-то ищет kotlin-эквивалент уникальных символов в строке, используя битовый вектор

fun isUnique(str: String): Boolean {
    var checker = 0
    for (i in str.indices) {
        val bit = str.get(i) - 'a'
        if (checker.and(1 shl bit) > 0) return false
        checker = checker.or(1 shl bit)
    }
    return true
}

Ссылка: https://www.programiz.com/kotlin-programming/bitwise