Meditasi LeetCode — Manipulasi Bit Bab

Jadual kandungan

• Pengenalan
• Pengendali bitwise
  • DAN (&)
  • ATAU (|)
  • XOR (^)
  • BUKAN (~)
  • Anjakan kiri (isi sifar) (<<)
  • Anjakan kanan (pemeliharaan tanda) (>>)
  • Anjakan kanan (tidak ditandatangani) (>>>)
• Mendapat sedikit
• Menetapkan sedikit
• Sumber

Kita berada di bab terakhir siri ini, dan akhirnya tiba masanya untuk melihat secara ringkas tentang manipulasi bit.

Seperti yang ditakrifkan oleh Wikipedia, operasi bitwise beroperasi pada rentetan bit, tatasusunan bit atau angka binari (dianggap sebagai rentetan bit) pada tahap bit individunya.

---

Mula-mula kita mewakili nombor dalam perduaan (asas 2). Kita boleh menggunakan kaedah toString pada nombor, dan menentukan radix:

const n = 17;

console.log(n.toString(2)); // 10001

Kita juga boleh menghuraikan integer memberikannya asas:

console.log(parseInt(10001, 2)); // 17

Perhatikan bahawa kita juga boleh mewakili nombor binari dengan awalan 0b:

console.log(0b10001); // 17
console.log(0b101); // 5

Sebagai contoh, ini adalah nombor yang sama:

0b1 === 0b00000001 // true

---

Semua operasi bitwise dilakukan pada nombor binari 32-bit dalam JavaScript.
Iaitu, sebelum operasi bitwise dilakukan, JavaScript menukar nombor kepada 32-bit **ditandatangani* integer.*

Jadi, sebagai contoh, 17 bukan sekadar 10001 tetapi 00000000 00000000 00000000 00010001.

Selepas operasi bitwise dilakukan, hasilnya ditukar kembali kepada nombor JavaScript 64-bit.

Pengendali bitwise

DAN (&)

Jika dua bit ialah 1, hasilnya ialah 1, jika tidak 0.

Note

The GIFs below show the numbers as 8-bit strings, but when doing bitwise operations, remember they are converted to 32-bit numbers.

const n = 17;

console.log(n.toString(2)); // 10001

ATAU (|)

Jika salah satu bit ialah 1, hasilnya ialah 1, jika tidak 0.

console.log(parseInt(10001, 2)); // 17

XOR (^)

Jika bit berbeza (satu ialah 1 dan satu lagi adalah 0), hasilnya ialah 1, jika tidak 0.

console.log(0b10001); // 17
console.log(0b101); // 5

BUKAN (~)

Terbalikkan bit (1 menjadi 0, 0 menjadi 1).

0b1 === 0b00000001 // true

Note

Bitwise NOTing any 32-bit integer x yields -(x 1).

Jika kami menggunakan fungsi pembantu untuk melihat perwakilan binari, ia adalah seperti yang kami jangkakan:

const n = 17;

console.log(n.toString(2)); // 10001

Bit paling kiri menunjukkan isyarat — sama ada nombor itu negatif atau positif.

Ingat bahawa kami berkata JavaScript menggunakan integer ditandatangani 32-bit untuk operasi bitwise.
Bit paling kiri ialah 1 untuk nombor negatif dan 0 untuk nombor positif.
Selain itu, pengendali beroperasi pada perwakilan bit operan dalam pelengkap dua. Operator digunakan pada setiap bit, dan hasilnya dibina bitwise.

Perhatikan bahawa pelengkap dua membolehkan kita mendapatkan nombor dengan isyarat songsang.
Satu cara untuk melakukannya ialah dengan menyongsangkan bit nombor dalam perwakilan positif dan menambah 1 padanya:

console.log(parseInt(10001, 2)); // 17

Anjakan kiri (isi sifar) (<<)

Menganjak bilangan bit yang diberikan ke kiri, menambah sifar bit yang dialihkan masuk dari kanan.

console.log(0b10001); // 17
console.log(0b101); // 5

Perhatikan bahawa bit ke-32 (yang paling kiri) dibuang.

Anjakan kanan (tanda dipelihara) (>>)

Menganjak bilangan bit yang diberikan ke kanan, mengekalkan tanda apabila menambah bit dari kiri.

0b1 === 0b00000001 // true

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 & x2; // 1 (0b1)

Anjakan kanan (tidak ditandatangani) (>>>)

Menganjak bilangan bit yang diberikan ke kanan, menambah 0s apabila menambah bit dari kiri, tidak kira apa tandanya.

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 | x2; // 21 (0b10101)

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 ^ x2; // 20 (0b10100)

---

Mendapat sedikit

Untuk mendapatkan bit tertentu, kita perlu mencipta bitmask dahulu.
Kita boleh melakukan ini dengan mengalihkan 1 ke kiri mengikut indeks bit yang kita mahu dapatkan.
Hasilnya ialah dan nombor binari dan bitmask.

Walau bagaimanapun, menggunakan JavaScript, kami juga boleh melakukan anjakan kanan yang tidak ditandatangani oleh indeks untuk meletakkan bit di tempat pertama (supaya kami tidak mendapat nilai sebenar yang berada dalam kedudukan itu, tetapi sama ada ia adalah 1 atau 0):

const n = 17;

const result = ~n; // -18

Sebagai contoh, mari cuba 13, iaitu 1101 dalam binari:

console.log(createBinaryString(n));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(result));
// -> 11111111 11111111 11111111 11101110

Tetapkan sedikit

Jika kita mahu bertukar sedikit kepada 1 (dengan kata lain, kepada "tetapkan sedikit"), kita boleh melakukan perkara yang serupa.

Pertama, kita boleh mencipta bitmask sekali lagi dengan mengalihkan 1 ke kiri dengan indeks bit yang ingin kita tetapkan kepada 1.
Hasilnya ialah atau nombor dan bitmask:

function twosComplement(n) {
  return ~n + 0b1;
}

Ingat bahawa dalam contoh 13 kita ialah 1101 dalam binari, katakan kita mahu menetapkan 0 pada indeks 1:

const n = 17;
const result = n << 1; // 34


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(34));
// -> 00000000 00000000 00000000 00100010

---

Kami melihat secara ringkas operasi bitwise, serta mendapatkan/menetapkan sedikit. Dalam bab terakhir ini, kita akan melihat lima masalah, bermula dengan Bilangan 1 Bit. Sehingga itu, selamat mengekod.

Sumber

• "Keperluan Mutlak untuk Manipulasi Bit dalam JavaScript" - Lucas F. Costa
• Operator Bitwise JS
• Nombor (MDN)
• Bitwise DAN (MDN)
• Bitwise NOT (MDN)
• Bitwise ATAU (MDN)
• Bitwise XOR (MDN)
• Anjakan kiri (MDN)
• Anjakan kanan (MDN)
• Anjakan kanan tidak ditandatangani (MDN)

Atas ialah kandungan terperinci Meditasi LeetCode — Manipulasi Bit Bab. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!