Рубрики

Побитовое и (или &) диапазона

Для двух неотрицательных длинных целых чисел, x и y, для x <= y, задача состоит в том, чтобы найти побитовое и целое число из x и y, т. Е. Нам нужно вычислить значение x & (x + 1) & … & (Y-1) & y.7

Примеры:

Input  : x = 12, y = 15
Output : 12 
12 & 13 & 14 & 15 = 12 

Input  : x = 10, y = 20
Output : 0 

Простое решение состоит в том, чтобы перебрать все числа от x до y, выполнить побитовое и все числа в диапазоне.

Эффективным решением является выполнение следующих шагов.
1) Найти позицию старшего значащего бита (MSB) в обоих числах.
2) Если позиции MSB разные, то результат равен 0.
3) Если позиции одинаковы. Пусть позиции будут msb_p.
…… а) Мы добавляем 2 msb_p к результату.
…… б) Мы вычитаем 2 msb_p из x и y,
… C) Повторите шаги 1, 2 и 3 для новых значений x и y.

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 ++

// Эффективная программа на C ++, чтобы найти побитовое и все
// числа от х до у.
#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

  
// Найти позицию MSB в n. Например, если n = 17,
// тогда позиция MSB равна 4. Если n = 7, значение MSB
// это 3

int msbPos(ll n)

{

    int msb_p = -1;

    while (n)

    {

        n = n>>1;

        msb_p++;

    }

    return msb_p;

}

  
// Функция для нахождения побитового числа всех чисел из x
// к тебе.
ll andOperator(ll x, ll y)
{

    ll res = 0; // Инициализировать результат

  

    while (x && y)

    {

        // Найти позиции MSB в х и у

        int msb_p1 = msbPos(x);

        int msb_p2 = msbPos(y);

  

        // Если позиции не совпадают, возвращаем

        if (msb_p1 != msb_p2)

            break;

  

        // Добавить 2 ^ msb_p1 к результату

        ll msb_val =  (1 << msb_p1);

        res = res + msb_val;

  

        // вычитаем 2 ^ msb_p1 из x и y.

        x = x - msb_val;

        y = y - msb_val;

    }

  

    return res;

}

  
// Код драйвера

int main()

{

    ll x = 10, y = 15;

    cout << andOperator(x, y);

    return 0;

}

Джава

// Эффективная Java-программа для поиска по битам
// & всех чисел от x до y.

class GFG { 

      

    // Найти позицию MSB в n. Например

    // если n = 17, то позиция MSB равна 4.

    // Если n = 7, значение MSB равно 3

    static int msbPos(long n) 

    

          

        int msb_p = -1

        while (n > 0) { 

            n = n >> 1

            msb_p++; 

        

          

        return msb_p; 

    

  

    // Функция поиска по битам и всего

    // числа от х до у.

    static long andOperator(long x, long y) 

    

          

        long res = 0; // Инициализировать результат

  

        while (x > 0 && y > 0) { 

              

            // Найти позиции MSB в х и у

            int msb_p1 = msbPos(x); 

            int msb_p2 = msbPos(y); 

  

            // Если позиции не совпадают, возвращаем

            if (msb_p1 != msb_p2) 

                break

  

            // Добавить 2 ^ msb_p1 к результату

            long msb_val = (1 << msb_p1); 

            res = res + msb_val; 

  

            // вычитаем 2 ^ msb_p1 из x и y.

            x = x - msb_val; 

            y = y - msb_val; 

        

  

        return res; 

    

      

    // Код драйвера

    public static void main(String[] args) 

    

          

        long x = 10, y = 15

          

        System.out.print(andOperator(x, y)); 

    

  
// Этот код предоставлен Anant Agarwal.

python3

# Эффективная программа Python для поиска
# побитово & всех чисел от х до у.

  
# Найти позицию MSB в п. Например
# если n = 17, то позиция MSB равна 4.
# Если n = 7, значение MSB равно 3

def msbPos(n): 

  

    msb_p = -1

    while (n > 0): 

      

        n = n >> 1

        msb_p += 1

      

    return msb_p 

  
# Функция поиска по битам
# все числа от х до у.

def andOperator(x, y): 

  

    res = 0 # Инициализировать результат

  

    while (x > 0 and y > 0): 

      

        # Найти позиции MSB в х и у

        msb_p1 = msbPos(x) 

        msb_p2 = msbPos(y) 

  

        # Если позиции не совпадают, вернуть

        if (msb_p1 != msb_p2): 

            break

  

        # Добавить 2 ^ msb_p1 к результату

        msb_val = (1 << msb_p1) 

        res = res + msb_val 

  

        # вычтите 2 ^ msb_p1 из x и y.

        x = x - msb_val 

        y = y - msb_val 

  

    return res 

      
# Код драйвера

x, y = 10, 15

print(andOperator(x, y)) 

  
# Этот код предоставлен Anant Agarwal.

C #

// Эффективная программа на C #, чтобы найти побитовое и все
// числа от х до у.

using System; 

  

class GFG 

    // Найти позицию MSB в n.

    // Например, если n = 17,

    // тогда позиция MSB равна 4.

    // Если n = 7, значение MSB

    // это 3

    static int msbPos(long n) 

    

        int msb_p = -1; 

        while (n > 0) 

        

            n = n >> 1; 

            msb_p++; 

        

        return msb_p; 

    

      

    // Функция для поиска по битам

    // & всех чисел из x

    // к тебе.

    static long andOperator(long x, long y) 

    

        // Инициализировать результат

        long res = 0; 

      

        while (x > 0 && y > 0) 

        

            // Найти позиции MSB в х и у

            int msb_p1 = msbPos(x); 

            int msb_p2 = msbPos(y); 

      

            // Если позиции не совпадают, возвращаем

            if (msb_p1 != msb_p2) 

                break

      

            // Добавить 2 ^ msb_p1 к результату

            long msb_val = (1 << msb_p1); 

            res = res + msb_val; 

      

            // вычитаем 2 ^ msb_p1 из x и y.

            x = x - msb_val; 

            y = y - msb_val; 

        

      

        return res; 

    

      

    // Код драйвера

    public static void Main() 

    

        long x = 10, y = 15; 

        Console.WriteLine(andOperator(x, y)); 

    

  
// Этот код предоставлен Anant Agarwal.

PHP

<?php
// Эффективная программа на C ++
// найти побитовый и всего
// числа от х до у.

  
// Найти позицию MSB в n.
// Например, если n = 17, то
// позиция MSB равна 4. Если n = 7,
// значение MSB равно 3

function msbPos($n)

{

    $msb_p = -1;

    while ($n > 0)

    {

        $n = $n >> 1;

        $msb_p++;

    }

    return $msb_p;

}

  
// Функция поиска по битам
// всех чисел от х до у.

function andOperator($x, $y)

{

    $res = 0; // Инициализировать результат

  

    while ($x > 0 && $y > 0)

    {

        // Найти позиции

        // MSB в х и у

        $msb_p1 = msbPos($x);

        $msb_p2 = msbPos($y);

  

        // Если позиции не

        // то же самое, возврат

        if ($msb_p1 != $msb_p2)

            break;

  

        // Добавить 2 ^ msb_p1 к результату

        $msb_val = (1 << $msb_p1);

        $res = $res + $msb_val;

  

        // вычитаем 2 ^ msb_p1

        // из х и у.

        $x = $x - $msb_val;

        $y = $y - $msb_val;

    }

  

    return $res;

}

  
// Код драйвера

$x = 10;

$y = 15;

echo andOperator($x, $y);

  
// Этот код добавлен
// от ihritik
?>


Выход:

8

Более эффективное решение

  1. Отразить младший бит б.
  2. И проверьте, находится ли новый номер в диапазоне (a <число <b) или нет
  • если число больше 'a' снова переверните lsb
  • если нет, то это ответ

ПРИМЕЧАНИЕ: мы не рассматриваем включающий диапазон, поэтому, если число «а», мы не должны больше переворачивать, то есть «а» будет ответом.

Example 1 :
x = 10, y = 20
y = 10100
Flip LSB of y New Number = 10000 i.e. 16
16 is in range so Again flip : 00000 i.e. 0 and 0 is not in range so 0 is the answer.

Example 2 :
x = 17, y = 19
y = 10011
Flip LSB of y so New Number = 10010 i.e. 18
18 is in range so Again flip : 10000 i.e. 16 and 16 is 'a' so Stop , answer is 16.

C ++

// Эффективная программа на C ++, чтобы найти побитовое и все
// числа от х до у.
#include <bits/stdc++.h>
#define ll long long

  

using namespace std;

ll andOperator(ll a, ll b){

while(a < b){

    // -b является дополнением 2 к b, если делать это поразрядно или с b

    // мы получаем LSB и вычитаем это из b

    b -= (b & -b);

}

return b;

}
// Код драйвера

int main(){

    ll a, b;

    a = 10; b = 15;

    cout << andOperator(a, b);

}

python3

# Эффективная программа Python3 для поиска
# побитово & всех чисел от х до у.

def andOperator(a, b):

    while(a < b):

          

        # -b является дополнением 2 к b

        # когда делать поразрядно или с б мы

        # получаем LSB, и мы вычитаем это из b

        b -= (b & -b) 

    return

  
# Код драйвера

a, b = 10, 15

print(andOperator(a, b))

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)


Выход:

8

Эта статья предоставлена Шивам Прадхан (anuj_charm) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Побитовое и (или &) диапазона

0.00 (0%) 0 votes