Pusingan Bit Minimum untuk Menukar Nombor

2220. Pusingan Bit Minimum untuk Menukar Nombor

Kesukaran: Mudah

Topik: Manipulasi Bit

Sebuah selak bit nombor x sedang memilih sedikit dalam perwakilan perduaan x dan terbalikkan daripada sama ada 0 kepada 1 atau 1 kepada 0.

• Sebagai contoh, forx = 7, perwakilan binari ialah 111 dan kami boleh memilih mana-mana bit (termasuk mana-mana sifar pendahuluan yang tidak ditunjukkan) dan membalikkannya. Kita boleh flip bit pertama dari kanan untuk mendapatkan 110, flip bit kedua dari kanan untuk mendapatkan 101, flip bit kelima dari kanan (sifar pendahuluan) untuk mendapatkan 10111, dsb.

Memandangkan dua integer bermula dan gol, kembalikan nombor minimum bit flip untuk menukar permulaan kepada matlamat.

Contoh 1:

• Input: mula = 10, matlamat = 7
• Output: 3
• Penjelasan: Perwakilan binari 10 dan 7 masing-masing ialah 1010 dan 0111. Kita boleh menukar 10 kepada 7 dalam 3 langkah:
  • Terbalikkan bit pertama dari kanan: 1010 -> 1011.
  • Terbalikkan bit ketiga dari kanan: 1011 -> 1111.
  • Terbalikkan bit keempat dari kanan: 1111 -> 0111.
  • Ia boleh ditunjukkan bahawa kita tidak boleh menukar 10 kepada 7 dalam masa kurang daripada 3 langkah. Oleh itu, kami kembalikan 3.

Contoh 2:

• Input: mula = 3, matlamat = 4
• Output: 3
• Penjelasan: Perwakilan binari 3 dan 4 masing-masing ialah 011 dan 100. Kita boleh menukar 3 kepada 4 dalam 3 langkah:
  • Terbalikkan bit pertama dari kanan: 011 -> 010.
  • Terbalikkan bit kedua dari kanan: 010 -> 000.
  • Terbalikkan bit ketiga dari kanan: 000 -> 100.
  • Ia boleh ditunjukkan bahawa kita tidak boleh menukar 3 kepada 4 dalam masa kurang daripada 3 langkah. Oleh itu, kami kembalikan 3.

Kekangan:

• 0 <= mula, matlamat <= 10⁹

Petunjuk:

1. Jika nilai sedikit pada permulaan dan matlamat berbeza, maka kita perlu menukar sedikit itu.
2. Pertimbangkan untuk menggunakan operasi XOR untuk menentukan bit yang memerlukan sedikit flip.

Penyelesaian:

Kita perlu menentukan berapa banyak kedudukan bit yang berbeza antara permulaan dan matlamat. Ini boleh dicapai dengan mudah menggunakan operasi XOR (^), yang mengembalikan 1 untuk setiap kedudukan bit di mana dua nombor berbeza.

Langkah-langkah:

1. Lakukan operasi XOR antara permulaan dan matlamat. Hasilnya ialah nombor yang mempunyai 1 dalam semua kedudukan di mana permulaan dan matlamat berbeza.
2. Kira berapa banyak 1 hadir dalam perwakilan binari hasil (iaitu, jarak Hamming).
3. Nombor 1s akan memberi kita bilangan minimum lilitan bit yang diperlukan.

Mari kita laksanakan penyelesaian ini dalam PHP: 2220. Flips Bit Minimum untuk Menukar Nombor

  
  
  Penjelasan:



Operasi ^ (XOR) membandingkan setiap bit permulaan dan matlamat. Jika bit berbeza, bit yang sepadan dalam hasilnya ialah 1.
Kami kemudian mengira bilangan 1s dalam keputusan, yang memberikan bilangan bit yang berbeza, iaitu, bilangan lilitan bit yang diperlukan.
Operasi & 1 menyemak sama ada bit terakhir ialah 1 dan >>= 1 mengalihkan nombor ke kanan untuk memproses bit seterusnya.



  
  
  Kerumitan Masa:



Kerumitan masa ialah (O(log N)), di mana (N) ialah permulaan atau matlamat yang lebih besar, kerana kami sedang menyemak setiap bit nombor. Dalam kes yang paling teruk, kami akan mengulangi semua bit integer 32-bit (memandangkan PHP 5.6 berfungsi dengan integer 32-bit atau 64-bit bergantung pada sistem).



  
  
  Output:



Untuk permulaan = 10 dan matlamat = 7, output ialah 3.
Untuk permulaan = 3 dan matlamat = 4, output ialah 3.


Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
        
Atas ialah kandungan terperinci Pusingan Bit Minimum untuk Menukar Nombor. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!