Meditasi LeetCode: Bit Songsang

Penerangan untuk Reverse Bits sangat ringkas:

Bit songsang bagi 32 bit integer tidak bertanda yang diberikan.

Terdapat juga nota:

• Perhatikan bahawa dalam sesetengah bahasa, seperti Java, tiada jenis integer yang tidak ditandatangani. Dalam kes ini, kedua-dua input dan output akan diberikan sebagai jenis integer yang ditandatangani. Ia tidak sepatutnya menjejaskan pelaksanaan anda, kerana perwakilan binari dalaman integer adalah sama, sama ada ia ditandatangani atau tidak ditandatangani.

• Di Java, pengkompil mewakili integer yang ditandatangani menggunakan tatatanda pelengkap 2. Oleh itu, dalam Contoh 2, input mewakili integer yang ditandatangani -3 dan output mewakili integer yang ditandatangani -1073741825.

Contohnya:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Atau:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Ia juga menyatakan bahawa Input mestilah rentetan binari panjang 32 dalam kekangan.

---

Memandangkan kita tahu bahawa input ialah integer 32-bit, kita boleh mengira kedudukan terbalik setiap bit dengan mudah. Contohnya, yang ke-0 sepadan dengan yang ke-31, yang ke-1 hingga ke-30, dan seterusnya.

Tetapi kami sedang melakukan manipulasi sedikit, yang bermaksud kami perlu menangani setiap bit satu demi satu.
Jadi, kita boleh menjalankan gelung for untuk melakukan perkara itu. Setiap kali, kita boleh mengalihkan bit mengikut indeks ke kedudukan paling kanan, yang boleh kelihatan seperti ini:

n >>> idx

Mendapat sedikit (sama ada 0 atau 1) boleh dilakukan dengan mudah dengan operasi DAN dengan 1.
Jika bit ialah 0, 0 & 1 akan menghasilkan 0.
Jika 1, 1 & 1 akan terhasil 1.

Nota Kita boleh menganggap

Note

We can think of ANDing with 1 as the multiplicative identity (for example, $7\cdot 1=7$7⋅1=7 ).

DAN dengan 1 sebagai identiti pendaraban (contohnya, $7\cdot 1=77\; cdot\; 1\; =\; 7$7⋅1=7 ).

Pertama, kita boleh mendapatkan sedikit:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Kemudian, kita perlu meletakkan bit yang kita ada pada kedudukan terbalik. Untuk itu, kita boleh meninggalkan anjakan sedikit, menambah kepada hasil semasa kita berbuat demikian:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Kita perlu mengembalikan hasilnya sebagai integer 32-bit, untuk melakukan itu, kita boleh melakukan helah menggunakan operator anjakan kanan yang tidak ditandatangani:

n >>> idx

Dan, penyelesaian akhir kelihatan seperti ini:

for (let i = 0; i < 32; i++) {
  let bit = (n >>> i) & 1;

  /* ... */
}

Kerumitan masa dan ruang

Kami tahu bahawa input dan hasil kami sentiasa integer 32-bit (dan, kami tidak perlu menggunakan struktur data tambahan lain), kami menjalankan gelung 32 kali juga, iaitu nombor tetap, jadi kedua-dua kerumitan masa dan ruang adalah $O(1)$O(1) .

---

Seterusnya, kita akan lihat Nombor Hilang. Sehingga itu, selamat mengekod.

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