Число с установленными битами только между L-м и R-м индексом
Для заданных L и R. Задача состоит в том, чтобы найти число, в двоичном представлении которого установлены все биты между L-м и R-м индексами, а остальные биты не установлены. Двоичное представление составляет 32 бита.
Примеры:
Input: L = 2, R = 5
Output: 60
Explanation: The binary representation is
0..0111100 => 60Input: L = 1, R = 3
Output: 14
Explanation: The binary representation is
0..01110 => 14
Наивный подход: наивный подход к нахождению числа состоит в том, чтобы выполнить итерацию от i = L до i = R и вычислить сложение всех степеней 2 i .
Программа ниже иллюстрирует наивный подход:
Выход:
60
Эффективный подход состоит в том, чтобы вычислить число со всеми (R) битами, установленными справа, и вычесть число со всеми (L-1) битами, установленными справа, чтобы получить требуемое число.
1. Вычислите число, в котором все биты R установлены справа, используя формулу ниже.
(1 << (R + 1)) - 1.
2. Вычтите число, у которого все (L-1) установлены биты справа.
(1 << L) - 1
Следовательно, вычисляя ((1 << (R + 1)) - 1) - ((1 << L) -1), мы получаем окончательную формулу как:
(1<<(R+1))-(1<<L)
The program below illustrates the efficient approach:
C++
// CPP program to print the integer // with all the bits set in range L-R // Efficient Approach #include <bits/stdc++.h> using namespace std; // Function to return the integer // with all the bits set in range L-R int setbitsfromLtoR( int L, int R) { return (1 << (R + 1)) - (1 << L); } // Driver Code int main() { int L = 2, R = 5; cout << setbitsfromLtoR(L, R); return 0; } |
Java
// Java program to print // the integer with all // the bits set in range // L-R Efficient Approach import java.io.*; class GFG { // Function to return the // integer with all the // bits set in range L-R static int setbitsfromLtoR( int L, int R) { return ( 1 << (R + 1 )) - ( 1 << L); } // Driver Code public static void main (String[] args) { int L = 2 , R = 5 ; System.out.println(setbitsfromLtoR(L, R)); } } // This code is contributed // by shiv_bhakt. |
Python3
# Python3 program to print # the integer with all the # bits set in range L-R # Efficient Approach # Function to return the # integer with all the # bits set in range L-R def setbitsfromLtoR(L, R): return (( 1 << (R + 1 )) - ( 1 << L)) # Driver Code L = 2 R = 5 print (setbitsfromLtoR(L, R)) # This code is contributed # by Smita |
C#
// C# program to print // the integer with all // the bits set in range // L-R Efficient Approach using System; class GFG { // Function to return the // integer with all the // bits set in range L-R static int setbitsfromLtoR( int L, int R) { return (1 << (R + 1)) - (1 << L); } // Driver Code public static void Main () { int L = 2, R = 5; Console.WriteLine(setbitsfromLtoR(L, R)); } } // This code is contributed // by shiv_bhakt. |
PHP
<?php // PHP program to print // the integer with all // the bits set in range // L-R Efficient Approach // Function to return the // integer with all the // bits set in range L-R function setbitsfromLtoR( $L , $R ) { return (1 << ( $R + 1)) - (1 << $L ); } // Driver Code $L = 2; $R = 5; echo setbitsfromLtoR( $L , $R ); // This code is contributed // by shiv_bhakt. ?> |
Javascript
<script> // Javascript program to print the integer // with all the bits set in range L-R // Efficient Approach // Function to return the integer // with all the bits set in range L-R function setbitsfromLtoR(L, R) { return (1 << (R + 1)) - (1 << L); } // Driver Code var L = 2, R = 5; document.write( setbitsfromLtoR(L, R)); // This code is contributed by famously. </script> |
Выход:
60
Сложность времени : O (1)
Вспомогательное пространство : O (1)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.