Kasus penggunaan dunia nyata dari operator bitwise [ditutup]

Apa sajakah kasus penggunaan dunia nyata dari operator bitwise berikut?

• DAN
• XOR
• TIDAK
• ATAU
• Pergeseran Kiri / Kanan

• Bidang bit (bendera)
  Mereka adalah cara paling efisien untuk mewakili sesuatu yang kondisinya didefinisikan oleh beberapa properti "ya atau tidak". ACL adalah contoh yang bagus; jika Anda memiliki katakanlah 4 izin terpisah (baca, tulis, jalankan, ubah kebijakan), lebih baik menyimpan ini dalam 1 byte daripada limbah 4. Ini dapat dipetakan ke jenis enumerasi dalam banyak bahasa untuk menambah kenyamanan.

• Komunikasi melalui port / soket
  Selalu melibatkan checksum, paritas, stop bit, algoritma kontrol aliran, dan sebagainya, yang biasanya bergantung pada nilai logika masing-masing byte sebagai lawan dari nilai numerik, karena medium hanya dapat mentransmisikan satu bit pada sebuah waktu.

• Kompresi, Enkripsi
  Keduanya sangat bergantung pada algoritma bitwise. Lihatlah algoritma deflate sebagai contoh - semuanya ada dalam bit, bukan byte.

• Finite State Machines
  Saya berbicara terutama tentang jenis yang tertanam dalam beberapa perangkat keras, meskipun mereka dapat ditemukan dalam perangkat lunak juga. Ini adalah kombinasi di alam - mereka mungkin benar-benar akan mendapatkan "dikompilasi" ke sekelompok gerbang logika, sehingga mereka harus dinyatakan sebagai AND, OR, NOT, dll

• Grafik Hampir tidak ada ruang yang cukup di sini untuk masuk ke setiap area di mana operator ini digunakan dalam pemrograman grafik. XOR(atau ^) sangat menarik di sini karena menerapkan input yang sama untuk kedua kalinya akan membatalkan yang pertama. GUI yang lebih tua digunakan untuk mengandalkan ini untuk menyoroti seleksi dan overlay lainnya, untuk menghilangkan kebutuhan redraws yang mahal. Mereka masih berguna dalam protokol grafik lambat (yaitu remote desktop).

Itu hanya beberapa contoh pertama yang saya buat - ini bukan daftar yang lengkap.

Apakah ini aneh?

(value & 0x1) > 0

Apakah bisa dibagi dua (datar)?

(value & 0x1) == 0

Inilah beberapa idiom umum yang berurusan dengan bendera yang disimpan sebagai bit individual.

enum CDRIndicators {
  Local = 1 << 0,
  External = 1 << 1,
  CallerIDMissing = 1 << 2,
  Chargeable = 1 << 3
};

unsigned int flags = 0;

Tetapkan bendera yang Dibebankan:

flags |= Chargeable;

Hapus bendera CallerIDMissing:

flags &= ~CallerIDMissing;

Uji apakah CallerIDMissing dan Charged diatur:

if((flags & (CallerIDMissing | Chargeable )) == (CallerIDMissing | Chargeable)) {

}

Saya telah menggunakan operasi bitwise dalam mengimplementasikan model keamanan untuk CMS. Itu memiliki halaman yang dapat diakses oleh pengguna jika mereka berada di grup yang sesuai. Seorang pengguna dapat berada dalam beberapa grup, jadi kami perlu memeriksa apakah ada persimpangan antara grup pengguna dan grup halaman. Jadi kami menetapkan masing-masing kelompok pengidentifikasi kekuatan-2 yang unik, misalnya:

Group A = 1 --> 00000001
Group B = 2 --> 00000010
Group C = 3 --> 00000100

Kami ATAU nilai-nilai ini bersama-sama, dan menyimpan nilai (sebagai satu int) dengan halaman. Misalnya jika sebuah halaman dapat diakses oleh grup A & B, kami menyimpan nilai 3 (yang dalam biner adalah 00000011) sebagai kontrol akses halaman. Dengan cara yang hampir sama, kami menyimpan nilai pengidentifikasi grup ORed dengan pengguna untuk mewakili grup mana mereka berada.

Jadi untuk memeriksa apakah pengguna tertentu dapat mengakses halaman yang diberikan, Anda hanya perlu DAN nilai-nilai bersama dan memeriksa apakah nilainya tidak nol. Ini sangat cepat karena pemeriksaan ini dilaksanakan dalam satu instruksi, tidak ada perulangan, tidak ada perjalanan pulang-pergi basis data.

Pemrograman tingkat rendah adalah contoh yang baik. Anda mungkin, misalnya, perlu menulis bit tertentu ke register yang dipetakan untuk membuat beberapa perangkat keras melakukan apa yang Anda inginkan:

volatile uint32_t *register = (volatile uint32_t *)0x87000000;
uint32_t          value;
uint32_t          set_bit   = 0x00010000;
uint32_t          clear_bit = 0x00001000;

value = *register;            // get current value from the register
value = value & ~clear_bit;   // clear a bit
value = value | set_bit;      // set a bit
*register = value;            // write it back to the register

Juga, htonl()dan htons()diimplementasikan menggunakan &dan |operator (pada mesin yang endianness (urutan Byte) tidak cocok dengan urutan jaringan):

#define htons(a) ((((a) & 0xff00) >> 8) | \
                  (((a) & 0x00ff) << 8))

#define htonl(a) ((((a) & 0xff000000) >> 24) | \
                  (((a) & 0x00ff0000) >>  8) | \
                  (((a) & 0x0000ff00) <<  8) | \
                  (((a) & 0x000000ff) << 24))

Saya menggunakannya untuk mendapatkan nilai RGB (A) dari nilai warna yang dikemas, misalnya.

Ketika saya memiliki banyak bendera boolean, saya suka menyimpan semuanya dalam sebuah int.

Saya mengeluarkannya menggunakan bitwise-AND. Sebagai contoh:

int flags;
if (flags & 0x10) {
  // Turn this feature on.
}

if (flags & 0x08) {
  // Turn a second feature on.
}

dll.

& = DAN:
Menyembunyikan bit tertentu.
Anda mendefinisikan bit spesifik yang harus ditampilkan atau tidak ditampilkan. 0x0 & x akan menghapus semua bit dalam satu byte sementara 0xFF tidak akan berubah x. 0x0F akan menampilkan bit di nibble yang lebih rendah.

Konversi:
Untuk memasukkan variabel yang lebih pendek ke variabel yang lebih panjang dengan identitas bit, perlu menyesuaikan bit karena -1 dalam int adalah 0xFFFFFFFF sedangkan -1 dalam panjang adalah 0xFFFFFFFFFFFFFFFFFF. Untuk mempertahankan identitas, Anda menerapkan masker setelah konversi.

| = ATAU
Setel bit. Bit akan diatur secara independen jika sudah diatur. Banyak datastructures (bitfields) memiliki flag seperti IS_HSET = 0, IS_VSET = 1 yang dapat diatur secara independen. Untuk mengatur bendera, Anda menerapkan IS_HSET | IS_VSET (Dalam C dan perakitan ini sangat mudah dibaca)

^ = XOR
Temukan bit yang sama atau berbeda.

~ = TIDAK
Balik bit.

Dapat ditunjukkan bahwa semua operasi bit lokal yang mungkin dapat dilaksanakan oleh operasi ini. Jadi, jika Anda suka, Anda dapat menerapkan instruksi ADD hanya dengan operasi bit.

Beberapa peretasan luar biasa:

http://www.ugcs.caltech.edu/~wnoise/base2.html
http://www.jjj.de/bitwizardry/bitwizardrypage.html

Enkripsi adalah semua operasi bitwise.

Anda dapat menggunakannya sebagai cara cepat dan kotor untuk hash data.

int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;

Saya baru saja menggunakan bitwise-XOR ( ^) sekitar tiga menit yang lalu untuk menghitung checksum untuk komunikasi serial dengan PLC ...

Bitwise & digunakan untuk menutupi / mengekstrak bagian tertentu dari byte.

1 variabel Byte

 01110010
&00001111 Bitmask of 0x0F to find out the lower nibble
 --------
 00000010

Khususnya operator shift (<< >>) sering digunakan untuk perhitungan.

Ini adalah contoh untuk membaca warna dari gambar bitmap dalam format byte

byte imagePixel = 0xCCDDEE; /* Image in RRGGBB format R=Red, G=Green, B=Blue */

//To only have red
byte redColour = imagePixel & 0xFF0000; /*Bitmasking with AND operator */

//Now, we only want red colour
redColour = (redColour >> 24) & 0xFF;  /* This now returns a red colour between 0x00 and 0xFF.

Saya harap contoh kecil ini membantu ....

Di dunia abstrak bahasa modern saat ini, tidak terlalu banyak. File IO adalah file yang mudah diingat, meskipun itu menjalankan operasi bitwise pada sesuatu yang sudah diterapkan dan tidak mengimplementasikan sesuatu yang menggunakan operasi bitwise. Namun, sebagai contoh mudah, kode ini menunjukkan penghapusan atribut read-only pada file (sehingga dapat digunakan dengan FileStream baru yang menentukan FileMode.Create) di c #:

//Hidden files posses some extra attibutes that make the FileStream throw an exception
//even with FileMode.Create (if exists -> overwrite) so delete it and don't worry about it!
if(File.Exists(targetName))
{
    FileAttributes attributes = File.GetAttributes(targetName);

    if ((attributes & FileAttributes.ReadOnly) == FileAttributes.ReadOnly)
        File.SetAttributes(targetName, attributes & (~FileAttributes.ReadOnly));

    File.Delete(targetName);
}

Sejauh implementasi kustom, berikut adalah contoh baru-baru ini: Saya membuat "pusat pesan" untuk mengirim pesan aman dari satu instalasi aplikasi terdistribusi kami ke yang lain. Pada dasarnya, ini analog dengan email, lengkap dengan Kotak Masuk, Kotak Keluar, Terkirim, dll, tetapi juga menjamin pengiriman dengan tanda terima baca, jadi ada subfolder tambahan di luar "kotak masuk" dan "terkirim." Jumlah ini adalah persyaratan bagi saya untuk mendefinisikan secara umum apa yang "ada di kotak masuk" atau apa "di folder yang dikirim". Dari folder yang dikirim, saya perlu tahu apa yang dibaca dan apa yang belum dibaca. Dari apa yang belum dibaca, saya perlu tahu apa yang diterima dan apa yang tidak. Saya menggunakan informasi ini untuk membangun klausa dinamis tempat menyaring sumber data lokal dan menampilkan informasi yang sesuai.

Inilah cara enum disatukan:

    public enum MemoView :int
    {
        InboundMemos = 1,                   //     0000 0001
        InboundMemosForMyOrders = 3,        //     0000 0011
        SentMemosAll = 16,                  //     0001 0000
        SentMemosNotReceived = 48,          //     0011
        SentMemosReceivedNotRead = 80,      //     0101
        SentMemosRead = 144,                //     1001
        Outbox = 272,                       //0001 0001 0000
        OutBoxErrors = 784                  //0011 0001 0000
    }

Apakah Anda melihat apa yang dilakukannya? Dengan anding (&) dengan nilai enum "Kotak Masuk", InboundMemos, saya tahu bahwa InboundMemosForMyOrders ada di kotak masuk.

Berikut ini adalah versi matang dari metode yang membangun dan mengembalikan filter yang menentukan tampilan untuk folder yang saat ini dipilih:

    private string GetFilterForView(MemoView view, DefaultableBoolean readOnly)
    {
        string filter = string.Empty;
        if((view & MemoView.InboundMemos) == MemoView.InboundMemos)
        {
            filter = "<inbox filter conditions>";

            if((view & MemoView.InboundMemosForMyOrders) == MemoView.InboundMemosForMyOrders)
            {
                filter += "<my memo filter conditions>";
            }
        }
        else if((view & MemoView.SentMemosAll) == MemoView.SentMemosAll)
        {
            //all sent items have originating system = to local
            filter = "<memos leaving current system>";

            if((view & MemoView.Outbox) == MemoView.Outbox)
            {
                ...
            }
            else
            {
                //sent sub folders
                filter += "<all sent items>";

                if((view & MemoView.SentMemosNotReceived) == MemoView.SentMemosNotReceived)
                {
                    if((view & MemoView.SentMemosReceivedNotRead) == MemoView.SentMemosReceivedNotRead)
                    {
                        filter += "<not received and not read conditions>";
                    }
                    else
                        filter += "<received and not read conditions>";
                }
            }
        }

        return filter;
    }

Sangat sederhana, tetapi implementasi yang rapi pada tingkat abstraksi yang biasanya tidak memerlukan operasi bitwise.

Pengkodean base64 adalah contohnya. Pengkodean Base64 digunakan untuk merepresentasikan data biner sebagai karakter yang dapat dicetak untuk mengirim melalui sistem email (dan keperluan lainnya). Pengkodean Base64 mengubah serangkaian 8 bit byte menjadi indeks pencarian karakter 6 bit. Operasi bit, pemindahan, dan'ing, atau'ing, not'ing sangat berguna untuk mengimplementasikan operasi bit yang diperlukan untuk pengkodean dan dekode Base64.

Ini tentu saja hanya 1 dari banyak contoh.

Saya terkejut tidak ada yang memilih jawaban yang jelas untuk era internet. Menghitung alamat jaringan yang valid untuk sebuah subnet.

http://www.topwebhosts.org/tools/netmask.php

Biasanya operasi bitwise lebih cepat daripada melakukan multiply / bagi. Jadi, jika Anda perlu mengalikan variabel x dengan mengatakan 9, Anda akan melakukan x<<3 + xbeberapa siklus yang lebih cepat daripada x*9. Jika kode ini di dalam ISR, Anda akan menghemat waktu respons.

Demikian pula jika Anda ingin menggunakan array sebagai antrian melingkar, itu akan lebih cepat (dan lebih elegan) untuk menangani membungkus cek dengan operasi sedikit bijak. (ukuran array Anda haruslah kekuatan 2). Misalnya:, Anda dapat menggunakan tail = ((tail & MASK) + 1)alih-alih tail = ((tail +1) < size) ? tail+1 : 0, jika Anda ingin memasukkan / menghapus.

Juga jika Anda ingin bendera kesalahan untuk menyimpan beberapa kode kesalahan bersamaan, setiap bit dapat menyimpan nilai yang terpisah. Anda dapat DAN dengan setiap kode kesalahan individu sebagai tanda centang. Ini digunakan dalam kode kesalahan Unix.

Bitmap n-bit juga bisa menjadi struktur data yang sangat keren dan ringkas. Jika Anda ingin mengalokasikan kumpulan sumber daya ukuran n, kita dapat menggunakan n-bit untuk mewakili status saat ini.

Sepertinya tidak ada yang menyebutkan matematika titik tetap.

(Ya, aku sudah tua, oke?)

Apakah angka xkekuatan 2? (Berguna misalnya dalam algoritme di mana penghitung bertambah, dan tindakan hanya diambil beberapa kali logaritmik)

(x & (x - 1)) == 0

Yang merupakan bit integer tertinggi x? (Ini misalnya dapat digunakan untuk menemukan daya minimum 2 yang lebih besar dari x)

x |= (x >>  1);
x |= (x >>  2);
x |= (x >>  4);
x |= (x >>  8);
x |= (x >> 16);
return x - (x >>> 1); // ">>>" is unsigned right shift

Yang mana yang terendah 1 bit dari integer x? (Membantu menemukan berapa kali habis dibagi 2.)

x & -x

Operator bitwise berguna untuk array looping yang panjangnya adalah kekuatan 2. Seperti banyak orang yang disebutkan, operator bitwise sangat berguna dan digunakan dalam Flags , Graphics , Networking , Enkripsi . Bukan hanya itu, tetapi mereka sangat cepat. Penggunaan Favorit pribadi saya adalah untuk lingkaran sebuah array yang tanpa conditional . Misalkan Anda memiliki array berbasis indeks nol (mis. Indeks elemen pertama adalah 0) dan Anda perlu mengulanginya tanpa batas. Maksud saya pergi dari elemen pertama ke yang terakhir dan kembali ke yang pertama. Salah satu cara untuk mengimplementasikan ini adalah:

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    if (i >= arr.length) 
        i = 0;
}

Ini adalah pendekatan paling sederhana, jika Anda ingin menghindari jika pernyataan , Anda dapat menggunakan pendekatan modulus seperti ini:

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    i = i % arr.length;
}

Sisi bawah dari kedua metode ini adalah bahwa operator modulus mahal, karena mencari sisa setelah pembagian integer. Dan metode pertama menjalankan pernyataan if pada setiap iterasi. Dengan operator bitwise namun jika panjang array Anda adalah kekuatan 2, Anda dapat dengan mudah menghasilkan urutan seperti 0 .. length - 1dengan menggunakan &(bitwise dan) operator seperti itu i & length. Jadi mengetahui ini, kode dari atas menjadi

int[] arr = new int[8];
int i = 0;
while (true){
    print(arr[i]);
    i = i + 1;
    i = i & (arr.length - 1);
}

Inilah cara kerjanya. Dalam format biner, setiap angka yang memiliki kekuatan 2 dikurangi dengan 1 diekspresikan hanya dengan angka satu. Misalnya 3 dalam biner adalah 11, 7 adalah111 , 15 adalah 1111dan seterusnya, Anda mendapatkan idenya. Sekarang, apa yang terjadi jika Anda &memiliki angka terhadap angka yang hanya terdiri dari angka dalam biner? Katakanlah kita melakukan ini:

num & 7;

Jika numlebih kecil atau sama dengan 7 maka hasilnya akan numkarena setiap bit &-ed dengan 1 adalah dirinya sendiri. Jika numlebih besar dari 7, selama &operasi komputer akan mempertimbangkan 7 nol terkemuka yang tentu saja akan tetap nol setelah& operasi hanya bagian yang tertinggal akan tetap. Seperti dalam kasus 9 & 7dalam biner akan terlihat seperti

1001 & 0111

hasilnya akan menjadi 0001 yaitu 1 dalam desimal dan membahas elemen kedua dalam array.

Saya menggunakannya untuk opsi multi-pilih, dengan cara ini saya hanya menyimpan satu nilai, bukan 10 atau lebih

itu juga bisa berguna dalam model relasional sql, katakanlah Anda memiliki tabel berikut: BlogEntry, BlogCategory

secara tradisional Anda bisa membuat hubungan nn di antara mereka menggunakan tabel BlogEntryCategory atau ketika tidak ada banyak catatan BlogCategory Anda bisa menggunakan satu nilai di BlogEntry untuk menautkan ke beberapa catatan BlogCategory seperti yang akan Anda lakukan dengan enum yang ditandai, di sebagian besar RDBMS juga ada operator yang sangat cepat untuk memilih pada kolom 'ditandai' ...

Ketika Anda hanya ingin mengubah beberapa bit dari Output mikrokontroler, tetapi register untuk menulis adalah byte, Anda melakukan sesuatu seperti ini (pseudocode):

char newOut = OutRegister & 0b00011111 //clear 3 msb's
newOut = newOut | 0b10100000 //write '101' to the 3 msb's
OutRegister = newOut //Update Outputs

Tentu saja, banyak mikrokontroler memungkinkan Anda mengubah setiap bit secara individual ...

Jika Anda ingin menghitung jumlah mod (%) Anda dengan kekuatan 2, Anda dapat menggunakan yourNumber & 2^N-1, yang dalam hal ini sama dengan yourNumber % 2^N.

number % 16 = number & 15;
number % 128 = number & 127;

Ini mungkin hanya berguna sebagai alternatif untuk operasi modulus dengan dividen yang sangat besar yaitu 2 ^ N ... Tetapi bahkan kemudian peningkatan kecepatannya atas operasi modulus diabaikan dalam pengujian saya di. NET 2.0. Saya menduga kompiler modern sudah melakukan optimasi seperti ini. Apakah seseorang ada yang tahu lebih soal ini?

Saya telah melihat mereka digunakan dalam sistem kontrol akses berbasis peran.

Ada penggunaan dunia nyata dalam pertanyaan saya di sini -
Tanggapi hanya pemberitahuan WM_KEYDOWN pertama?

Saat mengkonsumsi pesan WM_KEYDOWN di windows C api bit 30 menentukan status kunci sebelumnya. Nilainya 1 jika kunci turun sebelum pesan dikirim, atau nol jika kunci naik

Mereka sebagian besar digunakan untuk operasi bitwise (kejutan). Berikut adalah beberapa contoh dunia nyata yang ditemukan di basis kode PHP.

Pengkodean karakter:

if (s <= 0 && (c & ~MBFL_WCSPLANE_MASK) == MBFL_WCSPLANE_KOI8R) {

Struktur data:

ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK;

Driver basis data:

dbh->transaction_flags &= ~(PDO_TRANS_ACCESS_MODE^PDO_TRANS_READONLY);

Implementasi kompiler:

opline->extended_value = (opline->extended_value & ~ZEND_FETCH_CLASS_MASK) | ZEND_FETCH_CLASS_INTERFACE;

Setiap kali saya pertama kali memulai pemrograman C, saya memahami tabel kebenaran dan semua itu, tetapi itu tidak semua klik dengan bagaimana sebenarnya menggunakannya sampai saya membaca artikel ini http://www.gamedev.net/reference/articles/article1563.asp (yang memberi contoh kehidupan nyata)

Saya tidak berpikir ini dianggap sebagai bitwise, tetapi Array Ruby mendefinisikan operasi yang ditetapkan melalui operator bitwise integer normal. Jadi [1,2,4] & [1,2,3] # => [1,2]. Demikian pula untuk a ^ b #=> set differencedan a | b #=> union.

Solusi linear Tower Of Hanoi menggunakan operasi bitwise untuk menyelesaikan masalah.

public static void linear(char start, char temp, char end, int discs)
{
    int from,to;
    for (int i = 1; i < (1 << discs); i++) {
        from = (i & i-1) % 3;
        to = ((i | i-1) + 1) % 3;
        System.out.println(from+" => "+to);
    }
}

Penjelasan untuk solusi ini dapat ditemukan di sini