给定两个非负长整数，x和y给定x<=y，任务是从x和y中找出所有整数的位和，即我们需要计算x&（x+1）&…&（y-1）&y.7的值 例如：
null
Input : x = 12, y = 15Output : 12 12 & 13 & 14 & 15 = 12 Input : x = 10, y = 20Output : 0
A. 简单解决方案 就是从x到y遍历所有数字，并对范围内的所有数字进行逐位and运算。 一 有效解决方案 就是要遵循以下步骤。 1） 查找两个数字中最高有效位（MSB）的位置。 2） 如果MSB的位置不同，则结果为0。 3） 如果位置相同。让位置为msb_p。 ……a）我们加上2 msb_p 结果呢。 ……b）我们减去2 msb_p 从x和y， ……c）对x和y的新值重复步骤1、2和3。
Example 1 :x = 10, y = 20Result is initially 0.Position of MSB in x = 3Position of MSB in y = 4Since positions are different, return result.Example 2 :x = 17, y = 19Result is initially 0.Position of MSB in x = 4Position of MSB in y = 4Since positions are same, we compute 24.We add 24 to result. Result becomes 16.We subtract this value from x and y.New value of x = x - 24 = 17 - 16 = 1New value of y = y - 24 = 19 - 16 = 3Position of MSB in new x = 1Position of MSB in new y = 2Since positions are different, we return result.
C++
// An efficient C++ program to find bit-wise & of all // numbers from x to y. #include<bits/stdc++.h> using namespace std; typedef long long int ll; // Find position of MSB in n. For example if n = 17, // then position of MSB is 4. If n = 7, value of MSB // is 3 int msbPos(ll n) { int msb_p = -1; while (n) { n = n>>1; msb_p++; } return msb_p; } // Function to find Bit-wise & of all numbers from x // to y. ll andOperator(ll x, ll y) { ll res = 0; // Initialize result while (x && y) { // Find positions of MSB in x and y int msb_p1 = msbPos(x); int msb_p2 = msbPos(y); // If positions are not same, return if (msb_p1 != msb_p2) break ; // Add 2^msb_p1 to result ll msb_val = (1 << msb_p1); res = res + msb_val; // subtract 2^msb_p1 from x and y. x = x - msb_val; y = y - msb_val; } return res; } // Driver code int main() { ll x = 10, y = 15; cout << andOperator(x, y); return 0; } |
JAVA
// An efficient Java program to find bit-wise // & of all numbers from x to y. class GFG { // Find position of MSB in n. For example // if n = 17, then position of MSB is 4. // If n = 7, value of MSB is 3 static int msbPos( long n) { int msb_p = - 1 ; while (n > 0 ) { n = n >> 1 ; msb_p++; } return msb_p; } // Function to find Bit-wise & of all // numbers from x to y. static long andOperator( long x, long y) { long res = 0 ; // Initialize result while (x > 0 && y > 0 ) { // Find positions of MSB in x and y int msb_p1 = msbPos(x); int msb_p2 = msbPos(y); // If positions are not same, return if (msb_p1 != msb_p2) break ; // Add 2^msb_p1 to result long msb_val = ( 1 << msb_p1); res = res + msb_val; // subtract 2^msb_p1 from x and y. x = x - msb_val; y = y - msb_val; } return res; } // Driver code public static void main(String[] args) { long x = 10 , y = 15 ; System.out.print(andOperator(x, y)); } } // This code is contributed by Anant Agarwal. |
Python3
# An efficient Python program to find # bit-wise & of all numbers from x to y. # Find position of MSB in n. For example # if n = 17, then position of MSB is 4. # If n = 7, value of MSB is 3 def msbPos(n): msb_p = - 1 while (n > 0 ): n = n >> 1 msb_p + = 1 return msb_p # Function to find Bit-wise & of # all numbers from x to y. def andOperator(x, y): res = 0 # Initialize result while (x > 0 and y > 0 ): # Find positions of MSB in x and y msb_p1 = msbPos(x) msb_p2 = msbPos(y) # If positions are not same, return if (msb_p1 ! = msb_p2): break # Add 2^msb_p1 to result msb_val = ( 1 << msb_p1) res = res + msb_val # subtract 2^msb_p1 from x and y. x = x - msb_val y = y - msb_val return res # Driver code x, y = 10 , 15 print (andOperator(x, y)) # This code is contributed by Anant Agarwal. |
C#
// An efficient C# program to find bit-wise & of all // numbers from x to y. using System; class GFG { // Find position of MSB in n. // For example if n = 17, // then position of MSB is 4. // If n = 7, value of MSB // is 3 static int msbPos( long n) { int msb_p = -1; while (n > 0) { n = n >> 1; msb_p++; } return msb_p; } // Function to find Bit-wise // & of all numbers from x // to y. static long andOperator( long x, long y) { // Initialize result long res = 0; while (x > 0 && y > 0) { // Find positions of MSB in x and y int msb_p1 = msbPos(x); int msb_p2 = msbPos(y); // If positions are not same, return if (msb_p1 != msb_p2) break ; // Add 2^msb_p1 to result long msb_val = (1 << msb_p1); res = res + msb_val; // subtract 2^msb_p1 from x and y. x = x - msb_val; y = y - msb_val; } return res; } // Driver code public static void Main() { long x = 10, y = 15; Console.WriteLine(andOperator(x, y)); } } // This code is contributed by Anant Agarwal. |
PHP
<?php // An efficient C++ program // to find bit-wise & of all // numbers from x to y. // Find position of MSB in n. // For example if n = 17, then // position of MSB is 4. If n = 7, // value of MSB is 3 function msbPos( $n ) { $msb_p = -1; while ( $n > 0) { $n = $n >> 1; $msb_p ++; } return $msb_p ; } // Function to find Bit-wise & // of all numbers from x to y. function andOperator( $x , $y ) { $res = 0; // Initialize result while ( $x > 0 && $y > 0) { // Find positions of // MSB in x and y $msb_p1 = msbPos( $x ); $msb_p2 = msbPos( $y ); // If positions are not // same, return if ( $msb_p1 != $msb_p2 ) break ; // Add 2^msb_p1 to result $msb_val = (1 << $msb_p1 ); $res = $res + $msb_val ; // subtract 2^msb_p1 // from x and y. $x = $x - $msb_val ; $y = $y - $msb_val ; } return $res ; } // Driver code $x = 10; $y = 15; echo andOperator( $x , $y ); // This code is contributed // by ihritik ?> |
Javascript
<script> // Javascript program to find bit-wise // & of all numbers from x to y. // Find position of MSB in n. For example // if n = 17, then position of MSB is 4. // If n = 7, value of MSB is 3 function msbPos(n) { let msb_p = -1; while (n > 0) { n = n >> 1; msb_p++; } return msb_p; } // Function to find Bit-wise & of all // numbers from x to y. function andOperator(x, y) { let res = 0; // Initialize result while (x > 0 && y > 0) { // Find positions of MSB in x and y let msb_p1 = msbPos(x); let msb_p2 = msbPos(y); // If positions are not same, return if (msb_p1 != msb_p2) break ; // Add 2^msb_p1 to result let msb_val = (1 << msb_p1); res = res + msb_val; // subtract 2^msb_p1 from x and y. x = x - msb_val; y = y - msb_val; } return res; } // Driver Code let x = 10, y = 15; document.write(andOperator(x, y)); // This code is contributed by avijitmondal1998. </script> |
输出
8
更有效的解决方案
- 翻转b的LSB。
- 并检查新号码是否在范围内（a
- 如果数字再次大于“a”，则翻转lsb
- 如果不是，那就是答案
C++
// An efficient C++ program to find bit-wise & of all // numbers from x to y. #include<bits/stdc++.h> using namespace std; typedef long long int ll; // Function to find Bit-wise & of all numbers from x // to y. ll andOperator(ll x, ll y) { // Iterate over all bits of y, starting from the lsb, if it's equal to 1, flip it for ( int i=0; i<( int )log2(y)+1;i++) { //repeat till x >= y, otherwise return the answer. if (y <= x) { return y; } if (y & (1 << i)) { y &= ~(1UL << i); } } return y; } // Driver code int main() { ll x = 10, y = 15; cout << andOperator(x, y); return 0; } |
输出
8
另一种方法
我们知道如果一个数num是2的幂，那么（num&（num–1））等于0。因此，如果a小于2^k，b大于或等于2^k，那么a和b之间的所有值的和都应该为零，因为（2^k&（2^k–1））等于0。所以，如果a和b都在相同的位数内，那么唯一的答案就不会是零。现在，在任何情况下，最后一位都一定是零，因为即使a和b是并排的两个数字，最后一位也会不同。类似地，如果a和b之间的差值大于2，则第二个最后一位将为零，并且每一位都是如此。现在，以a=1100（12）和b=1111（15）为例，那么最后一位应该是答案的零。对于最后的第二位，我们需要检查a/2==b/2，因为如果它们相等，那么我们知道b–a<=2。如果a/2和b/2不相等，我们继续。现在，最后第三位的差值应该是4，可以通过a/4进行检查！=b/4。因此，我们从最后一刻开始检查每一点，直到最后一刻=在每一步中，我们修改a/=2（a>>1）和b/=2（b>>1），从末尾减少一位。
- 运行一段时间的循环，只要一个！=b和a>0
- 右移a档1，右移b档1
- 增量移位计数
- while循环返回左*2^（移位计数）
C++
// An efficient C++ program to find bit-wise & of all // numbers from x to y. #include<bits/stdc++.h> using namespace std; #define int long long int // Function to find Bit-wise & of all numbers from x // to y. int andOperator( int a, int b) { // ShiftCount variables counts till which bit every value will convert to 0 int shiftcount = 0; //Iterate through every bit of a and b simultaneously //If a == b then we know that beyond that the and value will remain constant while (a != b and a > 0) { shiftcount++; a = a >> 1; b = b >> 1; } return int64_t(a << shiftcount); } // Driver code int32_t main() { int a = 10, b = 15; cout << andOperator(a, b); return 0; } |
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
