Compruebe si los bits están en un patrón alternativo en el rango dado | Conjunto-2

Posted on by Rudeus Greyrat

Dado un número no negativo  N y dos valores  L y  R . El problema es verificar si N tiene o no un patrón alternativo en su representación binaria en el rango  L a R.
Aquí, patrón alternativo significa que los bits activados y desactivados ocurren en orden alternativo. Los bits se numeran de derecha a izquierda, es decir, se considera que el bit menos significativo está en la primera posición.
Ejemplos : 
 

Input : N = 18, L = 1, R = 3
Output : Yes
(18)10 = (10010)2
The bits in the range 1 to 3 in the
binary representation of 18 are in
alternate order.

Input : N = 22, L = 2, R = 4
Output : No
(22)10 = (10110)2
The bits in the range 2 to 4 in the
binary representation of 22 are not in
alternate order.

Enfoque simple: se ha discutido en esta publicación que tiene una complejidad de tiempo en el peor de los casos de O (log 2 n).
Enfoque eficiente: Los siguientes son los pasos:
 

  1. Declare dos variables num y left_shift .
  2. Compruebe si el bit r -ésimo está establecido o no en n . Consulte esta publicación. Si se configura entonces, asigne num = n y left_shift = r, de lo contrario, configure el (r+1)th bit en n y asígnelo a num . Consulte esta publicación. También asigne left_shift = r + 1.
  3. Ejecute num = num & ((1 << left_shift) – 1).
  4. Ejecute num = num >> (l – 1).
  5. Finalmente, verifique si los bits están en un patrón alternativo en num o no. Consulte esta publicación.

La idea completa del enfoque anterior es crear un número num en el que los bits estén en el mismo patrón que en el rango dado de n y luego verificar si los bits están en un patrón alternativo en num o no.
 

C++

// C++ implementation to check whether bits are in
// alternate pattern in the given range
#include <bits/stdc++.h>
 
using namespace std;
 
// function to check whether rightmost
// kth bit is set or not in 'n'
bool isKthBitSet(unsigned int n,
                 unsigned int k)
{
    if ((n >> (k - 1)) & 1)
        return true;
    return false;
}
 
// function to set the rightmost kth bit in 'n'
unsigned int setKthBit(unsigned int n,
                       unsigned int k)
{
    // kth bit of n is being set by this operation
    return ((1 << (k - 1)) | n);
}
 
// function to check if all the bits are set or not
// in the binary representation of 'n'
bool allBitsAreSet(unsigned int n)
{
    // if true, then all bits are set
    if (((n + 1) & n) == 0)
        return true;
 
    // else all bits are not set
    return false;
}
 
// function to check if a number
// has bits in alternate pattern
bool bitsAreInAltOrder(unsigned int n)
{
    unsigned int num = n ^ (n >> 1);
 
    // to check if all bits are set
    // in 'num'
    return allBitsAreSet(num);
}
 
// function to check whether bits are in
// alternate pattern in the given range
bool bitsAreInAltPatrnInGivenRange(unsigned int n,
                                   unsigned int l,
                                   unsigned int r)
{
    unsigned int num, left_shift;
 
    // preparing a number 'num' and 'left_shift'
    // which can be further used for the check
    // of alternate pattern in the given range
    if (isKthBitSet(n, r)) {
        num = n;
        left_shift = r;
    }
    else {
        num = setKthBit(n, (r + 1));
        left_shift = r + 1;
    }
 
    // unset all the bits which are left to the
    // rth bit of (r+1)th bit
    num = num & ((1 << left_shift) - 1);
 
    // right shift 'num' by (l-1) bits
    num = num >> (l - 1);
 
    return bitsAreInAltOrder(num);
}
 
// Driver program to test above
int main()
{
    unsigned int n = 18;
    unsigned int l = 1, r = 3;
    if (bitsAreInAltPatrnInGivenRange(n, l, r))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Java

// Java implementation to check whether bits are in
// alternate pattern in the given range
class GFG
{
 
// function to check whether rightmost
// kth bit is set or not in 'n'
static boolean isKthBitSet(int n,
                            int k)
{
    if ((n >> (k - 1)) == 1)
        return true;
    return false;
}
 
// function to set the rightmost kth bit in 'n'
static int setKthBit(int n,
                    int k)
{
    // kth bit of n is being set by this operation
    return ((1 << (k - 1)) | n);
}
 
// function to check if all the bits are set or not
// in the binary representation of 'n'
static boolean allBitsAreSet(int n)
{
    // if true, then all bits are set
    if (((n + 1) & n) == 0)
        return true;
 
    // else all bits are not set
    return false;
}
 
// function to check if a number
// has bits in alternate pattern
static boolean bitsAreInAltOrder(int n)
{
    int num = n ^ (n >> 1);
 
    // to check if all bits are set
    // in 'num'
    return allBitsAreSet(num);
}
 
// function to check whether bits are in
// alternate pattern in the given range
static boolean bitsAreInAltPatrnInGivenRange(int n,
                                int l, int r)
{
    int num, left_shift;
 
    // preparing a number 'num' and 'left_shift'
    // which can be further used for the check
    // of alternate pattern in the given range
    if (isKthBitSet(n, r))
    {
        num = n;
        left_shift = r;
    }
    else
    {
        num = setKthBit(n, (r + 1));
        left_shift = r + 1;
    }
 
    // unset all the bits which are left to the
    // rth bit of (r+1)th bit
    num = num & ((1 << left_shift) - 1);
 
    // right shift 'num' by (l-1) bits
    num = num >> (l - 1);
 
    return bitsAreInAltOrder(num);
}
 
// Driver code
public static void main(String[] args)
{
    int n = 18;
    int l = 1, r = 3;
    if (bitsAreInAltPatrnInGivenRange(n, l, r))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python 3 implementation to check
# whether bits are in alternate pattern
# in the given range
 
# function to check whether rightmost
# kth bit is set or not in 'n'
def isKthBitSet(n, k):
    if((n >> (k - 1)) & 1):
        return True
    return False
 
# function to set the rightmost kth bit in 'n'
def setKthBit(n, k):
     
    # kth bit of n is being set
    # by this operation
    return ((1 << (k - 1)) | n)
 
# function to check if all the bits are set or not
# in the binary representation of 'n'
def allBitsAreSet(n):
     
    # if true, then all bits are set
    if (((n + 1) & n) == 0):
        return True
 
    # else all bits are not set
    return False
 
# function to check if a number
# has bits in alternate pattern
def bitsAreInAltOrder(n):
    num = n ^ (n >> 1)
 
    # to check if all bits are set
    # in 'num'
    return allBitsAreSet(num)
 
# function to check whether bits are in
# alternate pattern in the given range
def bitsAreInAltPatrnInGivenRange(n, l, r):
     
    # preparing a number 'num' and 'left_shift'
    # which can be further used for the check
    # of alternate pattern in the given range
    if (isKthBitSet(n, r)):
        num = n
        left_shift = r
 
    else:
        num = setKthBit(n, (r + 1))
        left_shift = r + 1
     
    # unset all the bits which are left to the
    # rth bit of (r+1)th bit
    num = num & ((1 << left_shift) - 1)
 
    # right shift 'num' by (l-1) bits
    num = num >> (l - 1)
 
    return bitsAreInAltOrder(num)
 
# Driver Code
if __name__ == '__main__':
    n = 18
    l = 1
    r = 3
    if (bitsAreInAltPatrnInGivenRange(n, l, r)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation to check whether bits are in
// alternate pattern in the given range
using System;
 
class GFG
{
 
// function to check whether rightmost
// kth bit is set or not in 'n'
static bool isKthBitSet(int n,
                            int k)
{
    if ((n >> (k - 1)) == 1)
        return true;
    return false;
}
 
// function to set the rightmost kth bit in 'n'
static int setKthBit(int n,
                    int k)
{
    // kth bit of n is being set by this operation
    return ((1 << (k - 1)) | n);
}
 
// function to check if all the bits are set or not
// in the binary representation of 'n'
static bool allBitsAreSet(int n)
{
    // if true, then all bits are set
    if (((n + 1) & n) == 0)
        return true;
 
    // else all bits are not set
    return false;
}
 
// function to check if a number
// has bits in alternate pattern
static bool bitsAreInAltOrder(int n)
{
    int num = n ^ (n >> 1);
 
    // to check if all bits are set
    // in 'num'
    return allBitsAreSet(num);
}
 
// function to check whether bits are in
// alternate pattern in the given range
static bool bitsAreInAltPatrnInGivenRange(int n,
                                int l, int r)
{
    int num, left_shift;
 
    // preparing a number 'num' and 'left_shift'
    // which can be further used for the check
    // of alternate pattern in the given range
    if (isKthBitSet(n, r))
    {
        num = n;
        left_shift = r;
    }
    else
    {
        num = setKthBit(n, (r + 1));
        left_shift = r + 1;
    }
 
    // unset all the bits which are left to the
    // rth bit of (r+1)th bit
    num = num & ((1 << left_shift) - 1);
 
    // right shift 'num' by (l-1) bits
    num = num >> (l - 1);
 
    return bitsAreInAltOrder(num);
}
 
// Driver code
public static void Main()
{
    int n = 18;
    int l = 1, r = 3;
    if (bitsAreInAltPatrnInGivenRange(n, l, r))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// Javascript implementation to check whether bits are in
// alternate pattern in the given range
 
// function to check whether rightmost
// kth bit is set or not in 'n'
function isKthBitSet(n, k)
{
    if ((n >> (k - 1)) & 1)
        return true;
    return false;
}
 
// function to set the rightmost kth bit in 'n'
function setKthBit(n, k)
{
    // kth bit of n is being set by this operation
    return ((1 << (k - 1)) | n);
}
 
// function to check if all the bits are set or not
// in the binary representation of 'n'
function allBitsAreSet(n)
{
    // if true, then all bits are set
    if (((n + 1) & n) == 0)
        return true;
 
    // else all bits are not set
    return false;
}
 
// function to check if a number
// has bits in alternate pattern
function bitsAreInAltOrder(n)
{
    var num = n ^ (n >> 1);
 
    // to check if all bits are set
    // in 'num'
    return allBitsAreSet(num);
}
 
// function to check whether bits are in
// alternate pattern in the given range
function bitsAreInAltPatrnInGivenRange(n,
                                   l,
                                   r)
{
    var num, left_shift;
 
    // preparing a number 'num' and 'left_shift'
    // which can be further used for the check
    // of alternate pattern in the given range
    if (isKthBitSet(n, r)) {
        num = n;
        left_shift = r;
    }
    else {
        num = setKthBit(n, (r + 1));
        left_shift = r + 1;
    }
 
    // unset all the bits which are left to the
    // rth bit of (r+1)th bit
    num = num & ((1 << left_shift) - 1);
 
    // right shift 'num' by (l-1) bits
    num = num >> (l - 1);
 
    return bitsAreInAltOrder(num);
}
 
// Driver program to test above
var n = 18;
var l = 1, r = 3;
if (bitsAreInAltPatrnInGivenRange(n, l, r))
    document.write( "Yes");
else
    document.write( "No");
 
 
</script>   
Producción: 

Yes

 

Complejidad temporal : O(1).
 

Publicación traducida automáticamente

Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *