给定两个整数L和R。确定[L，R]范围内所有整数的位或（均含）。
null
例子 :
Input: L = 3, R = 8Output: 153 | 4 | 5 | 6 | 7 | 8 = 15Input: L = 12, R = 18Output: 3112 | 13 | 14 | 15 | 16 | 17 | 18 = 31
A. 缺乏经验的 方法是遍历L和R之间的所有整数，并对所有数字按位或进行运算。
一 有效率的 方法是遵循以下步骤：
- 查找两个数字（L和R）中最高有效位（MSB）的位置
- 如果两个MSB的位置不同，则将最大值（MSB1，MSB2）中的所有位（包括此不同位）设置为其他位，即为所有0添加值（1<
- 如果两个MSB的位置相同，则
- 将此位设置为与MSB相对应，或在答案中添加值（1<
- 从两个数字（L和R）中减去值（1<
- 重复步骤1、2和3。
- 从两个数字（L和R）中减去值（1<
- 如果两个MSB的位置相同，则
下面给出了L=18和R=21时上述算法的工作情况。
L = 18, R = 21The result is initially 0.The position of Most Significant Bit in L = 4Position of Most Significant Bit in R = 4Since positions are same, add value (1 << 4) i.e. 16 to the result.Subtract (1 << 4) from L, L becomes 2.Subtract (1 << 4) from R, R becomes 5.Now, Position of MSB in L is 1Position of MSB in R is 2Since positions are different all value (1 << i) for all 0 ≤ i ≤ max(MSB1, MSB2)i.e. Add ((1 << 2) + (1 << 1) + (1 << 0)) = 7Hence, final result is 16 + 7 = 23.
以下是上述方法的实施情况。
C++
// C++ Program to find the bitwise // OR of all the integers in range L-R #include <bits/stdc++.h> using namespace std; // Returns the Most Significant Bit // Position (MSB) int MSBPosition( long long int N) { int msb_p = -1; while (N) { N = N >> 1; msb_p++; } return msb_p; } // Returns the Bitwise OR of all // integers between L and R long long int findBitwiseOR( long long int L, long long int R) { long long int res = 0; // Find the MSB position in L int msb_p1 = MSBPosition(L); // Find the MSB position in R int msb_p2 = MSBPosition(R); while (msb_p1 == msb_p2) { long long int res_val = (1 << msb_p1); // Add this value until msb_p1 and // msb_p2 are same; res += res_val; L -= res_val; R -= res_val; // Calculate msb_p1 and msb_p2 msb_p1 = MSBPosition(L); msb_p2 = MSBPosition(R); } // Find the max of msb_p1 and msb_p2 msb_p1 = max(msb_p1, msb_p2); // Set all the bits from msb_p1 upto // 0th bit in the result for ( int i = msb_p1; i >= 0; i--) { long long int res_val = (1 << i); res += res_val; } return res; } // Driver Code int main() { int L = 12, R = 18; cout << findBitwiseOR(L, R) << endl; return 0; } |
JAVA
// Java Program to find // the bitwise OR of all // the integers in range L-R import java.io.*; class GFG { // Returns the Most Significant // Bit Position (MSB) static int MSBPosition( long N) { int msb_p = - 1 ; while (N > 0 ) { N = N >> 1 ; msb_p++; } return msb_p; } // Returns the Bitwise // OR of all integers // between L and R static long findBitwiseOR( long L, long R) { long res = 0 ; // Find the MSB // position in L int msb_p1 = MSBPosition(L); // Find the MSB // position in R int msb_p2 = MSBPosition(R); while (msb_p1 == msb_p2) { long res_val = ( 1 << msb_p1); // Add this value until // msb_p1 and msb_p2 are same; res += res_val; L -= res_val; R -= res_val; // Calculate msb_p1 // and msb_p2 msb_p1 = MSBPosition(L); msb_p2 = MSBPosition(R); } // Find the max of // msb_p1 and msb_p2 msb_p1 = Math.max(msb_p1, msb_p2); // Set all the bits // from msb_p1 upto // 0th bit in the result for ( int i = msb_p1; i >= 0 ; i--) { long res_val = ( 1 << i); res += res_val; } return res; } // Driver Code public static void main (String[] args) { int L = 12 , R = 18 ; System.out.println(findBitwiseOR(L, R)); } } // This code is contributed // by anuj_67. |
Python3
# Python3 Program to find the bitwise # OR of all the integers in range L-R # Returns the Most Significant Bit # Position (MSB) def MSBPosition(N) : msb_p = - 1 while (N) : N = N >> 1 msb_p + = 1 return msb_p # Returns the Bitwise OR of all # integers between L and R def findBitwiseOR(L, R) : res = 0 # Find the MSB position in L msb_p1 = MSBPosition(L) # Find the MSB position in R msb_p2 = MSBPosition(R) while (msb_p1 = = msb_p2) : res_val = ( 1 << msb_p1) # Add this value until msb_p1 and # msb_p2 are same; res + = res_val L - = res_val R - = res_val # Calculate msb_p1 and msb_p2 msb_p1 = MSBPosition(L) msb_p2 = MSBPosition(R) # Find the max of msb_p1 and msb_p2 msb_p1 = max (msb_p1, msb_p2) # Set all the bits from msb_p1 upto # 0th bit in the result for i in range (msb_p1, - 1 , - 1 ) : res_val = ( 1 << i) res + = res_val return res # Driver Code if __name__ = = "__main__" : L , R = 12 , 18 print (findBitwiseOR(L, R)) # This code is contributed by Ryuga |
C#
// C# Program to find // the bitwise OR of all // the integers in range L-R using System; class GFG { // Returns the Most Significant // Bit Position (MSB) static int MSBPosition( long N) { int msb_p = -1; while (N > 0) { N = N >> 1; msb_p++; } return msb_p; } // Returns the Bitwise // OR of all integers // between L and R static long findBitwiseOR( long L, long R) { long res = 0; // Find the MSB // position in L int msb_p1 = MSBPosition(L); // Find the MSB // position in R int msb_p2 = MSBPosition(R); while (msb_p1 == msb_p2) { long res_val = (1 << msb_p1); // Add this value until // msb_p1 and msb_p2 are same; res += res_val; L -= res_val; R -= res_val; // Calculate msb_p1 // and msb_p2 msb_p1 = MSBPosition(L); msb_p2 = MSBPosition(R); } // Find the max of // msb_p1 and msb_p2 msb_p1 = Math.Max(msb_p1, msb_p2); // Set all the bits // from msb_p1 upto // 0th bit in the result for ( int i = msb_p1; i >= 0; i--) { long res_val = (1 << i); res += res_val; } return res; } // Driver Code public static void Main () { int L = 12, R = 18; Console.WriteLine(findBitwiseOR(L, R)); } } // This code is contributed // by anuj_67. |
PHP
<?php // PHP Program to find the // bitwise OR of all the // integers in range L-R // Returns the Most Significant // Bit Position (MSB) function MSBPosition( $N ) { $msb_p = -1; while ( $N ) { $N = $N >> 1; $msb_p ++; } return $msb_p ; } // Returns the Bitwise // OR of all integers // between L and R function findBitwiseOR( $L , $R ) { $res = 0; // Find the MSB // position in L $msb_p1 = MSBPosition( $L ); // Find the MSB // position in R $msb_p2 = MSBPosition( $R ); while ( $msb_p1 == $msb_p2 ) { $res_val = (1 << $msb_p1 ); // Add this value until // msb_p1 and msb_p2 are same; $res += $res_val ; $L -= $res_val ; $R -= $res_val ; // Calculate msb_p1 // and msb_p2 $msb_p1 = MSBPosition( $L ); $msb_p2 = MSBPosition( $R ); } // Find the max of // msb_p1 and msb_p2 $msb_p1 = max( $msb_p1 , $msb_p2 ); // Set all the bits from msb_p1 // upto 0th bit in the result for ( $i = $msb_p1 ; $i >= 0; $i --) { $res_val = (1 << $i ); $res += $res_val ; } return $res ; } // Driver Code $L = 12; $R = 18; echo findBitwiseOR( $L , $R ); // This code is contributed // by anuj_67. ?> |
Javascript
<script> // Javascript Program to find // the bitwise OR of all // the integers in range L-R // Returns the Most Significant // Bit Position (MSB) function MSBPosition(N) { let msb_p = -1; while (N > 0) { N = N >> 1; msb_p++; } return msb_p; } // Returns the Bitwise // OR of all integers // between L and R function findBitwiseOR(L, R) { let res = 0; // Find the MSB // position in L let msb_p1 = MSBPosition(L); // Find the MSB // position in R let msb_p2 = MSBPosition(R); while (msb_p1 == msb_p2) { let res_val = (1 << msb_p1); // Add this value until // msb_p1 and msb_p2 are same; res += res_val; L -= res_val; R -= res_val; // Calculate msb_p1 // and msb_p2 msb_p1 = MSBPosition(L); msb_p2 = MSBPosition(R); } // Find the max of // msb_p1 and msb_p2 msb_p1 = Math.max(msb_p1, msb_p2); // Set all the bits // from msb_p1 upto // 0th bit in the result for (let i = msb_p1; i >= 0; i--) { let res_val = (1 << i); res += res_val; } return res; } let L = 12, R = 18; document.write(findBitwiseOR(L, R)); </script> |
输出：
31
时间复杂性： O（N），其中N是最高有效位。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
