Cari nombor dengan hanya set bit antara indeks Lth dan Rth menggunakan C++

Dalam masalah yang diberikan, kita perlu mencari nilai nombor yang mempunyai semua bit set antara julat L, R yang diberikan. Contohnya −

Input: L = 1, R = 5
Output: 62
Explanation: representation of given L and R in binary form is 0..0111110

Input: L = 1, R = 4
Output: 30
Explanation: representation of given L and R in binary form is 0..11110

Kaedah mencari penyelesaian

Dalam masalah yang diberikan, kita akan membincangkan dua kaedah, kaedah brute force dan kaedah cekap.

Kaedah brute force

Dalam kaedah ini kita hanya mengulangi julat yang diberikan dan menjumlahkan semua kuasa 2 dalam julat yang diberikan dan itu akan menjadi jawapan kita.

Contoh

#include<bits/stdc++.h>
using namespace std;
int main() {
   int L = 1, R = 3; // the given range
   int ans = 0; // our answer
   for(int i = L; i <= R; i++) // traversing through the whole range
      ans += pow(2, i); // adding values to the answer.
   cout << ans << "\n";
}

Output

14

Dalam kaedah ini, kami hanya mengulangi julat dan hanya menambah kuasa 2 nombor dalam julat. Kerumitan masa program ini ialah O(N), dengan N ialah saiz julat kami. Tetapi kita boleh meningkatkan lagi kerumitan masa dengan menggunakan sedikit pengetahuan dalam masalah yang diberikan.

Kaedah Cekap

Dalam kaedah ini kita hanya akan membina formula untuk mengira jawapan kita.

Contoh

#include<bits/stdc++.h>
using namespace std;
int main() {
   int L = 1, R = 3; // the given range
   int ans = 0; // our answer
   for(int i = L; i <= R; i++) // traversing through the whole range
      ans += pow(2, i); // adding values to the answer.
   cout << ans << "\n";
}

Output

14

Dalam kaedah ini, kami merumuskan formula untuk mengira jawapan.

Penjelasan kod di atas

Seperti yang anda tahu kita perlu mengira nombor dengan set bit dalam julat tertentu, jadi dalam kaedah ini kita mencari nombor dari 0 hingga R dengan semua bit ditetapkan. Kami kemudiannya perlu menolak nombor dengan semua bit ditetapkan dari 1 hingga (L-1), jadi kami merumuskan pemerhatian ini. Kerumitan masa keseluruhan kod yang diberikan ialah O(1), iaitu kerumitan masa malar, yang bermaksud kita boleh mengira sebarang jawapan dalam masa tetap.

Kesimpulan

Artikel ini akan menulis program untuk "nombor dengan set bit hanya antara indeks L-th dan R-th". Kami juga mempelajari program C++ dan kaedah lengkap (biasa dan cekap) untuk menyelesaikan masalah ini. Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan lain-lain. Semoga artikel ini membantu anda.

Atas ialah kandungan terperinci Cari nombor dengan hanya set bit antara indeks Lth dan Rth menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!