1. Apa itu Bitset?
Catatan: Konten berikut berasal dari JDK API:
Kelas Bitset mengimplementasikan sedikit vektor yang tumbuh sesuai permintaan. Setiap komponen bitset memiliki nilai boolean. Indeks bit bitset dengan bilangan bulat non-negatif. Setiap bit yang diindeks dapat diuji, diatur, atau dibersihkan. Melalui operasi XOR yang logis dan logis atau logis, satu bitset dapat digunakan untuk memodifikasi konten bitset lain.
Secara default, nilai awal semua bit dalam set adalah false.
Setiap set bit memiliki ukuran saat ini, yaitu, jumlah bit ruang saat ini yang digunakan oleh set bit. Perhatikan bahwa ukuran ini terkait dengan implementasi BITSET, sehingga dapat berubah dengan implementasi. Panjang set bit terkait dengan panjang logis set bit dan didefinisikan independen dari implementasi.
Kelas bitset menciptakan jenis array khusus untuk menahan nilai bit. Ukuran array dalam bitset akan meningkat sesuai kebutuhan. Ini mirip dengan vektor bit (vektorofbits).
Ini adalah kelas tradisional, tetapi telah sepenuhnya dirancang ulang di Java2.
Bitset mendefinisikan dua konstruktor.
Konstruktor pertama membuat objek default:
BitSet()
Metode kedua memungkinkan pengguna untuk menentukan ukuran awal. Semua bit diinisialisasi ke 0.
BitSet(intsize)
2. Prinsip Implementasi Java Bitset
Di Java, implementasi Bitset terletak di paket Java.util:
public class BitSet implements Cloneable, java.io.Serializable {private final static int ADDRESS_BITS_PER_WORD = 6;private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;/* Used to shift left or right for a partial word mask */private static final long WORD_MASK = 0xFFFFFFFFFFFFFFFFL; Private Static Final ObjectStreamfield [] SerialPersistentFields = {New ObjectStreamField ("Bits", Long []. Class),};/*** Bidang internal yang sesuai dengan "bit" serialfield. */private long [] kata; .....}Seperti yang Anda lihat, implementasi yang mendasari Bitset menggunakan array panjang sebagai struktur penyimpanan internal, sehingga ukuran bitset adalah kelipatan bilangan bulat dari ukuran jenis panjang (64-bit).
Ia memiliki dua konstruktor:
1. BITSET (): Buat set bit baru, ukuran default adalah 64 bit.
bitset publik () {initwords (bits_per_word); sizeIssticky = false;}2. Bitset (int nbits): Buat set bit yang ukuran awalnya cukup untuk secara eksplisit mewakili bit dengan kisaran indeks 0 hingga NBITS-1.
Bitset publik (int nbits) {// nbits tidak bisa negatif; Ukuran 0 ok jika (nbits <0) melempar negativearraysizeException baru ("nbits <0:" + nbits); initwords (nbits); sizeIssticky = true; }Catatan:
1. Jika ukuran inisialisasi bitset ditentukan, itu akan diatur ke bilangan bulat lebih besar dari atau sama dengan 64 dari angka ini. Misalnya, untuk 64 bit, ukuran bitset adalah 1 panjang, sedangkan untuk 65 bit, ukuran bitset adalah 2 panjang, yaitu, 128 bit. Peraturan ini terutama untuk penyelarasan memori, sambil menghindari pertimbangan tidak berurusan dengan keadaan khusus dan menyederhanakan program.
2: Metode Ukuran Bitset: Mengembalikan bitset ini untuk mewakili jumlah bit aktual yang digunakan ketika nilai bit adalah kelipatan integer dari 64.
Metode Panjang: Kembalikan "Ukuran Logis" dari Bitset ini: Indeks bit set tertinggi di bitset ditambahkan oleh 1
3. Gunakan skenario
Skenario aplikasi umum adalah melakukan beberapa pekerjaan statistik pada data besar -besaran, seperti analisis log, penghitungan pengguna, dll.
Saya ditanya pertanyaan sebelum wawancara magang dengan Alibaba: ada 10 juta angka acak, dan kisaran angka acak adalah antara 100 juta dan 100 juta. Sekarang saya perlu menulis algoritma untuk mengetahui jumlah antara 100 juta dan 100 juta yang tidak dalam jumlah acak?
Contoh kode adalah sebagai berikut:
Kelas publik alibaba {public static void main (string [] args) {acak acak = acak baru (); Daftar <Integer> Daftar = ArrayList baru <> (); untuk (int i = 0; i <10000000; i ++) {int randomResult = acak. untuk (int i = 0; i <list.size (); i ++) {System.out.println (list.get (i));} bitset bitset = bitset baru (10000000000); untuk (int i = 0; i <10000000; i ++) {bitset.set.set (list.get (i);}} sistem. angka "+bitset.size ()); for (int i = 0; i <100000000; i ++) {if (! bitset.get (i)) {System.out.println (i);}}}}}}}}}}}}}}}}}Meringkaskan
Di atas adalah semua tentang artikel ini yang membahas skenario penggunaan dan contoh kode Java Bitset, dan saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!