Jelaskan penggunaan vektor sedikit untuk menentukan apakah semua karakter unik

Saya bingung tentang bagaimana vektor bit akan bekerja untuk melakukan ini (tidak terlalu terbiasa dengan vektor bit). Ini kode yang diberikan. Bisakah seseorang tolong menuntun saya melalui ini?

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;
}

Terutama, apa yang checkerdilakukan?

int checkerdigunakan di sini sebagai penyimpanan untuk bit. Setiap bit dalam nilai integer dapat diperlakukan sebagai flag, jadi akhirnya intadalah array bit (flag). Setiap bit dalam kode Anda menyatakan apakah karakter dengan indeks bit ditemukan dalam string atau tidak. Anda bisa menggunakan bit vektor untuk alasan yang sama, bukan int. Ada dua perbedaan di antara mereka:

• Ukuran . intmemiliki ukuran tetap, biasanya 4 byte yang berarti 8 * 4 = 32 bit (bendera). Vektor bit biasanya dapat berukuran berbeda atau Anda harus menentukan ukuran dalam konstruktor.

• API . Dengan vektor bit Anda akan lebih mudah membaca kode, mungkin kira-kira seperti ini:

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

  untuk intAnda akan memiliki kode logika bit level rendah:

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

Mungkin juga mungkin intsedikit lebih cepat, karena operasi dengan bit tingkat sangat rendah dan dapat dieksekusi apa adanya oleh CPU. BitVector memungkinkan penulisan kode cryptic sedikit lebih sedikit daripada itu dapat menyimpan lebih banyak flag.

Untuk referensi di masa mendatang: bit vector juga dikenal sebagai bitSet atau bitArray. Berikut ini beberapa tautan ke struktur data ini untuk berbagai bahasa / platform:

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

Saya curiga Anda mendapatkan kode ini dari buku yang sama yang saya baca ... Kode itu sendiri di sini hampir tidak samar seperti operator- | =, &, dan << yang biasanya tidak digunakan oleh kami orang awam - penulis tidak repot-repot meluangkan waktu ekstra untuk menjelaskan prosesnya atau bagaimana sebenarnya mekanika yang terlibat di sini. Saya puas dengan jawaban sebelumnya pada utas ini di awal tetapi hanya pada tingkat abstrak. Saya kembali ke sana karena saya merasa perlu ada penjelasan yang lebih konkret - kurangnya orang selalu membuat saya merasa tidak enak.

Operator ini << adalah shifter bitwise kiri. Dibutuhkan representasi biner dari angka atau operan tersebut dan menggesernya ke atas, namun banyak tempat yang ditentukan oleh operan atau angka di sebelah kanan seperti dalam angka desimal hanya dalam biner. Kita mengalikan dengan basis 2 - ketika kita naik tetapi banyak tempat bukan basis 10 - jadi angka di sebelah kanan adalah eksponen dan angka di sebelah kiri adalah kelipatan basis dari 2.

Operator ini = mengambil operan di sebelah kiri dan atau itu dengan operan di kanan- dan ini - '&' dan bit dari kedua operan ke kiri dan kanan itu.

Jadi apa yang kita miliki di sini adalah tabel hash yang disimpan dalam angka biner 32 bit setiap kali pemeriksa mendapat (atau checker |= (1 << val)) dengan nilai biner yang ditunjuk dari sebuah huruf, bit terkaitnya disetel menjadi true. Nilai karakter adalah dan bersama checker ( checker & (1 << val)) > 0) - jika lebih besar dari 0 kita tahu kita memiliki dupe karena dua bit identik disetel ke true dan bersama-sama akan mengembalikan true atau '1' '.

Ada 26 tempat biner yang masing-masing sesuai dengan huruf kecil-penulis mengatakan untuk menganggap string hanya berisi huruf kecil- dan ini karena kita hanya memiliki 6 lebih banyak (dalam bilangan bulat 32) tempat yang tersisa untuk dikonsumsi- dan daripada kita mendapatkan tabrakan

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

Jadi, untuk string input 'azya', saat kami bergerak langkah demi langkah

string 'a'

a      =00000000000000000000000000000001
checker=00000000000000000000000000000000

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

a and checker=0 no dupes condition

string 'az'

checker=00000000000000000000000000000001
z      =00000010000000000000000000000000

z and checker=0 no dupes 

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

string 'azy'

checker= 00000010000000000000000000000001    
y      = 00000001000000000000000000000000 

checker and y=0 no dupes condition 

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

string 'azya'

checker= 00000011000000000000000000000001
a      = 00000000000000000000000000000001

a and checker=1 we have a dupe

Sekarang, ini menyatakan duplikat

Saya pikir semua jawaban ini menjelaskan cara kerjanya, namun saya merasa ingin memberikan masukan tentang bagaimana saya melihatnya lebih baik, dengan mengganti nama beberapa variabel, menambahkan beberapa yang lain dan menambahkan komentar ke dalamnya:

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;
}

Saya juga berasumsi bahwa contoh Anda berasal dari buku Cracking The Code Wawancara dan jawaban saya terkait dengan konteks ini.

Untuk menggunakan algoritma ini untuk menyelesaikan masalah, kita harus mengakui bahwa kita hanya akan meneruskan karakter dari a ke z (huruf kecil).

Karena hanya ada 26 huruf dan ini diurutkan dengan benar dalam tabel pengkodean yang kami gunakan, ini menjamin kami bahwa semua perbedaan potensial str.charAt(i) - 'a'akan lebih rendah dari 32 (ukuran variabel int checker).

Seperti yang dijelaskan oleh Snowbear, kita akan menggunakan checkervariabel sebagai array bit. Mari kita memiliki pendekatan dengan contoh:

Katakanlah str equals "test"

• Lulus pertama (i = t)

pemeriksa == 0 (0000000000000000000000000000000000)

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)

• Lulus kedua (i = e)

pemeriksa == 524288 (00000000000010000000000000000000)

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

dan seterusnya .. sampai kita menemukan bit yang sudah diset di checker untuk karakter tertentu melalui kondisi

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

Semoga ini bisa membantu

Ada beberapa jawaban bagus yang sudah disediakan di atas. Jadi saya tidak ingin mengulangi apa yang sudah dikatakan semuanya. Tetapi memang ingin menambahkan beberapa hal untuk membantu dengan program di atas karena saya hanya bekerja melalui program yang sama dan memiliki beberapa pertanyaan tetapi setelah menghabiskan waktu, saya memiliki kejelasan lebih lanjut tentang program ini.

Pertama-tama "pemeriksa" digunakan untuk melacak karakter yang sudah dilalui dalam String untuk melihat apakah ada karakter yang diulang.

Sekarang "checker" adalah tipe data int sehingga hanya dapat memiliki 32 bit atau 4 byte (tergantung platform) sehingga program ini hanya dapat bekerja dengan benar untuk set karakter dalam kisaran 32 karakter. Itulah alasannya, program ini mengurangi 'a' dari masing-masing karakter untuk membuat program ini berjalan hanya untuk karakter huruf kecil. Namun, jika Anda mencampur huruf besar dan kecil maka itu tidak akan berhasil.

Omong-omong, jika Anda tidak mengurangi 'a' dari setiap karakter (lihat pernyataan di bawah) maka program ini akan bekerja dengan benar untuk hanya String dengan karakter huruf besar atau String dengan karakter huruf kecil saja. Jadi cakupan program di atas meningkat dari hanya karakter huruf kecil ke karakter huruf besar juga, tetapi mereka tidak dapat dicampur bersama.

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

Namun saya ingin menulis program generik menggunakan Operasi Bitwise yang seharusnya berfungsi untuk setiap karakter ASCII tanpa khawatir tentang huruf besar, huruf kecil, angka, atau karakter khusus apa pun. Untuk melakukan ini, "pemeriksa" kami harus cukup besar untuk menyimpan 256 karakter (ukuran Set Karakter ASCII). Tetapi sebuah int di Java tidak akan berfungsi karena ia hanya dapat menyimpan 32 bit. Oleh karena itu dalam program di bawah ini, saya menggunakan kelas BitSet yang tersedia di JDK yang dapat memiliki ukuran apa pun yang ditetapkan pengguna saat instantiating objek BitSet.

Berikut adalah program yang melakukan hal yang sama seperti program di atas yang ditulis menggunakan operator Bitwise tetapi program ini akan bekerja untuk sebuah String dengan karakter apa pun dari rangkaian karakter 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;

}

Membaca jawaban Ivan di atas sangat membantu saya, walaupun saya akan mengatakannya dengan agak berbeda.

The <<dalam (1 << val)adalah operator sedikit pergeseran. Dibutuhkan 1(yang dalam biner direpresentasikan sebagai 000000001, dengan nol sebelumnya sebanyak yang Anda suka / dialokasikan oleh memori) dan menggesernya ke kiri oleh valspasi. Karena kita mengasumsikan hanya az dan mengurangi asetiap kali, setiap huruf akan memiliki nilai 0-25, yang akan menjadi indeks surat itu dari kanan dalam checkerrepresentasi boolean bilangan bulat, karena kita akan memindahkan 1ke kiri dalam checker valwaktu.

Pada akhir setiap pemeriksaan, kami melihat |=operator. Ini menggabungkan dua angka biner, menggantikan semua 0dengan 1jika 1ada di salah satu operan di indeks itu. Di sini, itu berarti bahwa di mana pun 1ada (1 << val), yang 1akan disalin ke dalam checker, sementara semua checker1 yang ada akan dilestarikan.

Seperti yang bisa Anda tebak, 1fungsi di sini sebagai bendera boolean untuk true. Ketika kita memeriksa untuk melihat apakah suatu karakter sudah terwakili dalam string, kita membandingkan checker, yang pada titik ini pada dasarnya adalah array dari boolean flags ( 1values) pada indeks karakter yang telah diwakili, dengan apa yang pada dasarnya adalah array dari nilai boolean dengan 1bendera pada indeks karakter saat ini.

The &Operator menyelesaikan cek ini. Mirip dengan |=, &operator akan menyalin 1 hanya jika kedua operan memiliki 1indeks tersebut. Jadi, pada dasarnya, hanya bendera yang sudah ada checkeryang juga diwakili (1 << val)akan disalin. Dalam hal ini, itu berarti hanya jika karakter saat ini telah diwakili akan ada 1hadiah di mana saja di hasil checker & (1 << val). Dan jika a 1hadir di mana saja dalam hasil operasi itu, maka nilai boolean yang dikembalikan adalah > 0, dan metode mengembalikan false.

Ini, saya menduga, mengapa vektor bit juga disebut bit array . Karena, meskipun mereka bukan tipe data array, mereka dapat digunakan mirip dengan cara array digunakan untuk menyimpan bendera boolean.

Penjelasan Sederhana (dengan kode JS di bawah)

• Variabel integer per kode mesin adalah array 32-bit
• Semua operasi yang bijak 32-bit
• Mereka agnostik dari arsitektur OS / CPU atau sistem angka pilihan bahasa, misalnya DEC64untuk JS.
• Pendekatan pencarian duplikasi ini mirip dengan menyimpan karakter dalam array ukuran 32 di mana, kita menetapkan 0thindeks jika kita temukan adalam string, 1stuntuk b& seterusnya.
• Karakter duplikat dalam string akan memiliki bit yang sesuai ditempati, atau, dalam hal ini, set ke 1.
• Ivan sudah menjelaskan : Bagaimana perhitungan indeks ini bekerja di jawaban sebelumnya ini .

Ringkasan operasi:

• Lakukan AND operasi antara checker& indexkarakter
• Secara internal keduanya Int-32-Arrays
• Ini adalah operasi yang agak bijaksana antara 2 ini.
• Memeriksa if output dari operasi itu1
• jika output == 1
  • The checkervariabel memiliki yang agak indeks-th tertentu set di kedua array
  • Jadi itu duplikat.
• jika output == 0
  • Karakter ini belum ditemukan sejauh ini
  • Lakukan operasi ATAU antara checker& indexkarakter
  • Dengan demikian, memperbarui bit indeks-ke 1
  • Tetapkan output ke checker

Asumsi:

• Kami berasumsi kami akan mendapatkan semua karakter huruf kecil
• Dan, ukuran 32 itu sudah cukup
• Oleh karena itu, kami mulai menghitung indeks dari 96 sebagai titik referensi dengan mempertimbangkan kode ascii untuk ais97

Diberikan di bawah ini adalah kode sumber 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

Perhatikan bahwa dalam JS, meskipun bilangan bulat 64 bit, operasi yang bijak selalu dilakukan pada 32 bit.

Contoh: Jika stringnya adalah aa:

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

i = 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

i = 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

Mari kita memecah baris kode demi baris.

pemeriksa int = 0; Kami sedang memulai pemeriksa yang akan membantu kami menemukan nilai duplikat.

int val = str.charAt (i) - 'a'; Kami mendapatkan nilai ASCII dari karakter di posisi ke-i dari string dan mengurangkannya dengan nilai ASCII dari 'a'. Karena asumsi adalah bahwa string adalah karakter yang lebih rendah saja, jumlah karakter dalam dibatasi hingga 26. Hece, nilai 'val' akan selalu>> 0.

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

checker | = (1 << val);

Sekarang ini bagian yang sulit. Mari kita perhatikan contoh dengan string "abcda". Ini idealnya akan kembali salah.

Untuk iterasi loop 1:

Pemeriksa: 0000000000000000000000000000000000

val: 97-97 = 0

1 << 0: 00000000000000000000000000000001

pemeriksa & (1 << val): 0000000000000000000000000000000000 tidak> 0

Oleh karena itu pemeriksa: 00000000000000000000000000000001

Untuk iterasi loop 2:

Pemeriksa: 00000000000000000000000000000001

val: 98-97 = 1

1 << 0: 0000000000000000000000000000000010

pemeriksa & (1 << val): 0000000000000000000000000000000000 tidak> 0

Oleh karena itu pemeriksa: 0000000000000000000000000000000011

Untuk iterasi loop 3:

Pemeriksa: 00000000000000000000000000000011

val: 99-97 = 0

1 << 0: 00000000000000000000000000000100100

pemeriksa & (1 << val): 0000000000000000000000000000000000 tidak> 0

Oleh karena itu pemeriksa: 00000000000000000000000000000111

Untuk iterasi loop 4:

Pemeriksa: 00000000000000000000000000000111

val: 100-97 = 0

1 << 0: 00000000000000000000000000001000

pemeriksa & (1 << val): 0000000000000000000000000000000000 tidak> 0

Oleh karena itu pemeriksa: 00000000000000000000000000001111

Untuk iterasi loop 5:

Pemeriksa: 00000000000000000000000000001111

val: 97-97 = 0

1 << 0: 00000000000000000000000000000001

pemeriksa & (1 << val): 0000000000000000000000000000000001 adalah> 0

Karena itu kembalikan salah.

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;
}

Posting Sebelumnya menjelaskan dengan baik apa yang dilakukan oleh kode blok dan saya ingin menambahkan Solusi sederhana saya menggunakan struktur data java BitSet:

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:   }

Cara saya mengerti menggunakan Javascript. Mengasumsikan inputvar inputChar = "abca"; //find if inputChar has all unique characters

Ayo mulai

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

Above line Finds Nilai biner dari karakter pertama di inputChar yang a , a = 97 di ascii, kemudian mengonversi 97 ke biner menjadi 1100001 .

Dalam Javascript Misalnya: "a".charCodeAt().toString(2) mengembalikan 1100001

checker = 0 // Representasi biner 32 bit = 0000000000000000000000000

checker = 1100001 | checker; // checker menjadi 1100001 (Dalam representasi 32 bit menjadi 000000000 ..... 00001100001)

Tetapi saya ingin bitmask saya ( int checker) untuk mengatur hanya satu bit, tetapi checker adalah 1100001

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

Sekarang kode di atas berguna. Saya hanya mengurangi 97 selalu (ASCII val a)

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

Mari kita gunakan valyang diatur ulang

Jalur 5 dan Jalur 6 menjelaskan jawaban @van dengan baik

Untuk jaga-jaga jika ada yang mencari kotlin setara dengan karakter unik dalam string menggunakan bit vector

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
}

Ref: https://www.programiz.com/kotlin-programming/bitwise