Dados dos enteros largos no negativos, x e y dados x <= y, la tarea es encontrar bit a bit y de todos los enteros de x e y, es decir, necesitamos calcular el valor de x & (x+1) & … & (y-1) & y.7
Ejemplos:
Input : x = 12, y = 15 Output : 12 12 & 13 & 14 & 15 = 12 Input : x = 10, y = 20 Output : 0
Una solución simple es atravesar todos los números de x a y y hacerlo bit a bit y de todos los números en el rango.
Una solución eficiente es seguir los siguientes pasos.
1) Encuentre la posición del bit más significativo (MSB) en ambos números.
2) Si las posiciones de MSB son diferentes, entonces el resultado es 0.
3) Si las posiciones son las mismas. Deje que las posiciones sean msb_p.
……a) Agregamos 2 msb_p al resultado.
……b) Restamos 2 msb_p de xey,
……c) Repita los pasos 1, 2 y 3 para nuevos valores de xey.
Example 1 : x = 10, y = 20 Result is initially 0. Position of MSB in x = 3 Position of MSB in y = 4 Since positions are different, return result. Example 2 : x = 17, y = 19 Result is initially 0. Position of MSB in x = 4 Position of MSB in y = 4 Since 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 = 1 New value of y = y - 24 = 19 - 16 = 3 Position of MSB in new x = 1 Position of MSB in new y = 2 Since 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>
Producción
8
Complejidad del tiempo: O(log(max(x, y)))
Espacio Auxiliar: O(1)
Solución más eficiente
- Da la vuelta al LSB de b.
- Y verifique si el nuevo número está dentro del rango (a <número <b) o no
- si el número es mayor que ‘a’ de nuevo voltear lsb
- si no es asi esa es la respuesta
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;
}
Java
// An efficient Java program to find bit-wise & of all
// numbers from x to y.
import java.util.*;
class GFG {
// Function to find Bit-wise & of all numbers from x
// to y.
static int andOperator(int x, int y)
{
// Iterate over all bits of y, starting from the
// lsb, if it's equal to 1, flip it
for (int i = 0; i < (Math.log(y) / Math.log(2)) + 1;
i++) {
// repeat till x >= y, otherwise return the
// answer.
if (y <= x) {
return y;
}
if ((y & (1 << i)) != 0) {
y &= ~(1 << i);
}
}
return y;
}
// Driver code
public static void main(String[] args)
{
int x = 10;
int y = 15;
System.out.print(andOperator(x, y));
}
}
// This code is contributed by phasing17
Python3
# An efficient Python program to find bit-wise & of # all numbers from x to y. # Importing math module for using logarithm import math # Function to find Bit-wise & of all numbers from x # to y. def andOperator(x, y): # Iterate over all bits of y, starting from the lsb, if it's equal to 1, flip it for i in range(int(math.log2(y) + 1)): # repeat till x >= y, otherwise return the answer if(y <= x): return y if(y & 1 << i): y = y & (~(1<<i)) return y # Driver code x, y = 10, 15 print(andOperator(x, y)) # This code is contributed by Pushpesh Raj
C#
// An efficient C# program to find bit-wise & of all
// numbers from x to y.
using System;
class GFG {
// Function to find Bit-wise & of all numbers from x
// to y.
static int andOperator(int x, int y)
{
// Iterate over all bits of y, starting from the
// lsb, if it's equal to 1, flip it
for (int i = 0; i < (Math.Log(y) / Math.Log(2)) + 1;
i++) {
// repeat till x >= y, otherwise return the
// answer.
if (y <= x) {
return y;
}
if ((y & (1 << i)) != 0) {
y &= ~(1 << i);
}
}
return y;
}
// Driver code
public static void Main(string[] args)
{
int x = 10;
int y = 15;
Console.Write(andOperator(x, y));
}
}
// This code is contributed by phasing17
Javascript
// An efficient JavaScript program to find bit-wise & of all
// numbers from x to y.
// Function to find Bit-wise & of all numbers from x
// to y.
function andOperator(x, y)
{
// Iterate over all bits of y, starting from the lsb, if it's equal to 1, flip it
for(var i=0; i<Math.log2(y)+1;i++)
{
//repeat till x >= y, otherwise return the answer.
if (y <= x) {
return y;
}
if (y & (1 << i)) {
y &= ~(1 << i);
}
}
return y;
}
// Driver code
var x = 10, y = 15;
console.log(andOperator(x, y));
//This code is contributed by phasing17
Producción
8
Complejidad del tiempo: O(log(y))
Espacio Auxiliar: O(1)
Otro enfoque
Sabemos que si un número num es una potencia de 2, entonces (num &(num – 1)) es igual a 0. Entonces, si a es menor que 2^k y b es mayor o igual que 2^k, entonces el & de todos los valores entre a y b debe ser cero ya que (2^k & (2^k – 1)) es igual a 0. Entonces, si tanto a como b se encuentran dentro del mismo número de bits, entonces solo la respuesta no será cero. Ahora, en todos los casos, el último bit está destinado a ser cero porque incluso si a y b son 2 números uno al lado del otro, el último bit será diferente. De manera similar, el segundo último bit será cero si la diferencia entre a y b es mayor que 2 y esto continúa para cada bit. Ahora, tome el ejemplo a = 1100 (12) y b = 1111 (15), luego el último bit debe ser cero de la respuesta. Para el segundo último bit, debemos verificar si a/2 == b/2 porque si son iguales, entonces sabemos que b – a <= 2. Entonces, si a/2 y b/2 no son iguales, entonces procedemos. Ahora, El 3er último bit debe tener una diferencia de 4 que puede verificarse con a/ 4 != b/4. Por lo tanto, comprobamos cada bit desde el último hasta a!=b y en cada paso modificamos a/=2(a >> 1) y b/=2(b >> 1) para reducir un bit desde el final.
- Ejecute un ciclo while mientras a != b y a > 0
- Desplazamiento a la derecha en 1 y desplazamiento a la derecha b en 1
- incrementar el número de turnos
- después de que el ciclo while regrese a la izquierda * 2^(shiftcount)
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;
}
Java
// An efficient Java program to find bit-wise & of all
// numbers from x to y.
import java.util.*;
class GFG {
// Function to find Bit-wise & of all numbers from x
// to y.
static long 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 && a > 0) {
shiftcount++;
a = a >> 1;
b = b >> 1;
}
return (long)(a << shiftcount);
}
// Driver code
public static void main(String[] args)
{
int a = 10, b = 15;
System.out.println(andOperator(a, b));
}
}
// This code is contributed by phasing17
Python3
# An efficient Python program to find bit-wise & of # all numbers from x to y. # Function to find Bit-wise & of all numbers from x # to y. def andOperator(a,b): # ShiftCount variables counts till which bit every value will convert to 0 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=shiftcount+1 a=a>>1 b=b>>1 return a<<shiftcount # Driver code a, b =10, 15 print(andOperator(a, b)) # This code is contributed by Pushpesh Raj
C#
// An efficient C# program to find bit-wise & of all
// numbers from x to y.
using System;
class GFG
{
// Function to find Bit-wise & of all numbers from x
// to y.
static Int64 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 && a > 0)
{
shiftcount++;
a = a >> 1;
b = b >> 1;
}
return (Int64)(a << shiftcount);
}
// Driver code
public static void Main(string[] args) {
int a = 10, b = 15;
Console.WriteLine(andOperator(a, b));
}
}
// This code is contributed by phasing17
Javascript
// An efficient JavaScript program to find bit-wise & of all
// numbers from x to y.
// Function to find Bit-wise & of all numbers from x
// to y.
function andOperator(a, b)
{
// ShiftCount variables counts till which bit every value will convert to 0
let 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 && a > 0) {
shiftcount++;
a = a >> 1;
b = b >> 1;
}
return (a << shiftcount);
}
// Driver code
let a = 10, b = 15;
console.log(andOperator(a, b));
// This code is contributed by phasing17
Salida :
8
Complejidad del tiempo : O(log(max(x, y)))
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA