仅在第L个和第R个索引之间具有设置位的数字-yiteyi-C++库

给定L和R。任务是找到一个数字，在该数字的二进制表示中，第L和第R个索引之间的所有位都已设置，其余位未设置。二进制表示为32位。

null

例如：

输入： L=2，R=5 输出： 60 说明： 二进制表示是 0..0111100 => 60

输入： L=1，R=3 输出： 14 说明： 二进制表示是 0..01110 => 14

天真的方法： 求这个数的简单方法是从i=L迭代到i=R，然后计算2的所有幂的加法 ^我 . 下面的程序说明了这种天真的方法：

C++

                         // CPP program to print the integer                       
                         // with all the bits set in range L-R                       
                         // Naive Approach                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to return the integer                       
                         // with all the bits set in range L-R                       
                         int                                     getInteger(                                     int                                     L,                                     int                                     R)                       
                         {                       
           
                                                 int                                     number = 0;                       
           
                                                 // iterate from L to R                       
                                                 // and add all powers of 2                       
                                                 for                                     (                                     int                                     i = L; i <= R; i++)                       
                                                 number +=                                     pow                                     (2, i);                       
           
                                                 return                                     number;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     L = 2, R = 5;                       
                                                 cout << getInteger(L, R);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print the                       
                         // integer with all the bits                       
                         // set in range L-R Naive Approach                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Function to return the                       
                         // integer with all the                       
                         // bits set in range L-R                       
                         static                                     int                                     getInteger(                                     int                                     L,                       
                                                 int                                     R)                       
                         {                       
                                                 int                                     number =                                     0                                     ;                       
           
                                                 // iterate from L to R                       
                                                 // and add all powers of 2                       
                                                 for                                     (                                     int                                     i = L; i <= R; i++)                       
                                                 number += Math.pow(                                     2                                     , i);                       
           
                                                 return                                     number;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     L =                                     2                                     , R =                                     5                                     ;                       
                                                 System.out.println(getInteger(L, R));                       
                         }                       
                         }                       
           
                         // This code is contributed by anuj_67..                       

Python3

                         # Python 3 program to print the integer                       
                         # with all the bits set in range L-R                       
                         # Naive Approach                       
                         from                                     math                                     import                                     pow                       
           
                         # Function to return the integer                       
                         # with all the bits set in range L-R                       
                         def                                     getInteger(L, R):                       
                                                 number                                     =                                     0                       
           
                                                 # iterate from L to R                       
                                                 # and add all powers of 2                       
                                                 for                                     i                                     in                                     range                                     (L, R                                     +                                     1                                     ,                                     1                                     ):                       
                                                 number                                     +                                     =                                     pow                                     (                                     2                                     , i)                       
           
                                                 return                                     number                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 L                                     =                                     2                       
                                                 R                                     =                                     5                       
                                                 print                                     (                                     int                                     (getInteger(L, R)))                       
           
                         # This code is contributed by                       
                         # Surendra_Gangwar                       

C#

                         // C# program to print the                       
                         // integer with all the bits                       
                         // set in range L-R Naive Approach                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         // Function to return the                       
                         // integer with all the                       
                         // bits set in range L-R                       
                         static                                     int                                     getInteger(                                     int                                     L,                       
                                                 int                                     R)                       
                         {                       
                                                 int                                     number = 0;                       
           
                                                 // iterate from L to R                       
                                                 // and add all powers of 2                       
                                                 for                                     (                                     int                                     i = L; i <= R; i++)                       
                                                 number += (                                     int                                     )Math.Pow(2, i);                       
           
                                                 return                                     number;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main ()                       
                         {                       
                                                 int                                     L = 2, R = 5;                       
                                                 Console.Write(getInteger(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 Naive Approach                       
           
                         // Function to return the                       
                         // integer with all the                       
                         // bits set in range L-R                       
                         function                                     getInteger(                                     $L                                     ,                                     $R                                     )                       
                         {                       
                                                 $number                                     = 0;                       
           
                                                 // iterate from L to R                       
                                                 // and add all powers of 2                       
                                                 for                                     (                                     $i                                     =                                     $L                                     ;                                     $i                                     <=                                     $R                                     ;                                     $i                                     ++)                       
                                                 $number                                     += pow(2,                                     $i                                     );                       
           
                                                 return                                     $number                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $L                                     = 2;                       
                         $R                                     = 5;                       
                         echo                                     getInteger(                                     $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                       
                         // Naive Approach                       
           
                         // Function to return the integer                       
                         // with all the bits set in range L-R                       
                         function                                     getInteger(L, R)                       
                         {                       
           
                                                 var                                     number = 0;                       
           
                                                 // iterate from L to R                       
                                                 // and add all powers of 2                       
                                                 for                                     (                                     var                                     i = L; i <= R; i++)                       
                                                 number += Math.pow(2, i);                       
           
                                                 return                                     number;                       
                         }                       
           
                         // Driver Code                       
                         var                                     L = 2, R = 5;                       
                         document.write( getInteger(L, R));                       
           
                         </script>                       

输出：

一 有效的方法 就是从右边开始计算所有（R）位的数字，然后从右边开始减去所有（L-1）位的数字，得到所需的数字。

1.使用下面的公式计算从右边开始包含所有R个设置位的数字。

(1 << (R+1)) - 1.

2.从右边减去包含所有（L-1）设定位的数字。

(1<<L) - 1

因此，通过计算（（1<

（1<

下面的程序说明了有效的方法：

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）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章