Число с установленными битами только между L-м и R-м индексом

Опубликовано: 16 Января, 2022

Для заданных L и R. Задача состоит в том, чтобы найти число, в двоичном представлении которого установлены все биты между L-м и R-м индексами, а остальные биты не установлены. Двоичное представление составляет 32 бита.

Примеры:

Input: L = 2, R = 5
Output: 60
Explanation: The binary representation is
0..0111100 => 60
Input: L = 1, R = 3
Output: 14
Explanation: The binary representation is
0..01110 => 14

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: наивный подход к нахождению числа состоит в том, чтобы выполнить итерацию от i = L до i = R и вычислить сложение всех степеней 2 ⁱ .
Программа ниже иллюстрирует наивный подход:

Выход:

Эффективный подход состоит в том, чтобы вычислить число со всеми (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>

Выход:

Сложность времени : O (1)
Вспомогательное пространство : O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

Число с установленными битами только между L-м и R-м индексом

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ