Cuente números más pequeños cuyo XOR con n produce mayor valor

Dado un entero positivo n, cuente números x tales que 0 < x <n y x^n > n donde ^ es una operación XOR bit a bit.
Ejemplos: 
 

Input  : n = 12
Output : 3
Numbers are 1, 2 and 3
1^12 > 12,  2^12 > 12 and 3^12 > 12

Input  : n = 11
Output : 4
Numbers are 4, 5, 6 and 7

Un número puede x producir un valor XOR mayor si x tiene un bit establecido en una posición donde n tiene un bit 0. Así que recorremos bits de n, y uno por uno consideramos todos los bits 0. Para cada bit establecido en la posición k (Considerando k = 0 para el bit más a la derecha, k = 1 para el segundo bit más a la derecha, ..), sumamos 2 2 k al resultado. Para un bit en la k-ésima posición, hay 2 k números con el bit 1 establecido. 
A continuación se muestra la implementación de la idea anterior. 
 

C++

// C++ program to count numbers whose XOR with n
// produces a value more than n.
#include<bits/stdc++.h>
using namespace std;
 
int countNumbers(int n)
{
    /* If there is a number like m = 11110000,
    then it is bigger than 1110xxxx. x can either
    0 or 1. So we have pow(2, k) greater numbers
    where k is  position of rightmost 1 in m. Now
    by using XOR bit at each  position can be changed.
    To change bit at any position, it needs to XOR
    it with 1. */
    int k = 0; // Position of current bit in n
 
    /* Traverse bits from LSB (least significant bit)
       to MSB */
    int count = 0;  // Initialize result
    while (n > 0)
    {
        // If current bit is 0, then there are
        // 2^k numbers with current bit 1 and
        // whose XOR with n produces greater value
        if ((n&1) == 0)
            count += pow(2, k);
 
        // Increase position for next bit
        k += 1;
 
        // Reduce n to find next bit
        n >>= 1;
    }
 
    return count;
}
 
// Driver code
int main()
{
    int n = 11;
    cout << countNumbers(n) << endl;
    return 0;
}

Java

// Java program to count numbers
// whose XOR with n produces a
// value more than n.
import java.lang.*;
class GFG {
 
    static int countNumbers(int n)
    {
 
        // If there is a number like
        // m = 11110000, then it is
        // bigger than 1110xxxx. x
        // can either be 0 or 1. So
        // where k is the position of
        // rightmost 1 in m. Now by
        // using the XOR bit at each
        // position can be changed.
        // To change the bit at any
        // position, it needs to
        // XOR it with 1.
        int k = 0;
        // Position of current bit in n
 
        // Traverse bits from LSB (least
        // significant bit) to MSB
 
        int count = 0;
        // Initialize result
        while (n > 0) {
            // If the current bit is 0, then
            // there are 2^k numbers with
            // current bit 1 and whose XOR
            // with n produces greater value
            if ((n & 1) == 0)
                count += (int)(Math.pow(2, k));
 
            // Increase position for next bit
            k += 1;
 
            // Reduce n to find next bit
            n >>= 1;
        }
 
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 11;
        System.out.println(countNumbers(n));
    }
}
 
// This code is contributed by Smitha.

Python3

# Python program to count numbers whose
# XOR with n produces a value more than n.
 
def countNumbers(n):
 
    ''' If there is a number like m = 11110000,
    then it is bigger than 1110xxxx. x can either
    0 or 1. So we have pow(2, k) greater numbers
    where k is position of rightmost 1 in m. Now
    by using XOR bit at each position can be changed.
    To change bit at any position, it needs to XOR
    it with 1. '''
     
    # Position of current bit in n
    k = 0
 
    # Traverse bits from
    # LSB to MSB
    count = 0 # Initialize result
    while (n > 0):
     
        # If current bit is 0, then there are
        # 2^k numbers with current bit 1 and
        # whose XOR with n produces greater value
        if ((n & 1) == 0):
            count += pow(2, k)
 
        # Increase position for next bit
        k += 1
 
        # Reduce n to find next bit
        n >>= 1
 
    return count
 
# Driver code
n = 11
print(countNumbers(n))
 
# This code is contributed by Anant Agarwal.

C#

// C# program to count numbers
// whose XOR with n produces a
// value more than n.
using System;
 
class GFG {
 
    static int countNumbers(int n)
    {
 
        // If there is a number like
        // m = 11110000, then it is
        // bigger than 1110xxxx. x
        // can either be 0 or 1. So
        // where k is the position of
        // rightmost 1 in m. Now by
        // using the XOR bit at each
        // position can be changed.
        // To change the bit at any
        // position, it needs to
        // XOR it with 1.
        int k = 0;
        // Position of current bit in n
 
        // Traverse bits from LSB (least
        // significant bit) to MSB
 
        int count = 0;
        // Initialize result
        while (n > 0) {
            // If the current bit is 0, then
            // there are 2^k numbers with
            // current bit 1 and whose XOR
            // with n produces greater value
            if ((n & 1) == 0)
                count += (int)(Math.Pow(2, k));
 
            // Increase position for next bit
            k += 1;
 
            // Reduce n to find next bit
            n >>= 1;
        }
 
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 11;
        Console.WriteLine(countNumbers(n));
    }
}
 
// This code is contributed by Anant Agarwal.

PHP

<?php
// PHP program to count
// numbers whose XOR with n
// produces a value more than n.
 
function countNumbers($n)
{
     
    /* If there is a number
       like m = 11110000,
       then it is bigger
       than 1110xxxx. x
       can either 0 or 1.
       So we have pow(2, k)
       greater numbers where
       k is position of
       rightmost 1 in m.
       Now by using XOR bit
       at each position can
       be changed. To change
       bit at any position,
       it needs to XOR it
       with 1. */
        
    // Position of current bit in n
    $k = 0;
     
    /* Traverse bits from LSB
       (least significant bit)
       to MSB */
        
    // Initialize result  
    $count = 0;
    while ($n > 0)
    {
         
        // If current bit is 0,
        // then there are 2^k
        // numbers with current
        // bit 1 and whose XOR
        // with n produces greater
        // value
        if (($n & 1) == 0)
            $count += pow(2, $k);
 
        // Increase position
        // for next bit
        $k += 1;
 
        // Reduce n to
        // find next bit
        $n >>= 1;
    }
 
    return $count;
}
 
    // Driver code
    $n = 11;
    echo countNumbers($n);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// Javascript program  to count numbers whose XOR with n
// produces a value more than n.
   
    function countNumbers(n)
    {
   
        // If there is a number like
        // m = 11110000, then it is
        // bigger than 1110xxxx. x
        // can either be 0 or 1. So
        // where k is the position of
        // rightmost 1 in m. Now by
        // using the XOR bit at each
        // position can be changed.
        // To change the bit at any
        // position, it needs to
        // XOR it with 1.
        let k = 0;
        // Position of current bit in n
   
        // Traverse bits from LSB (least
        // significant bit) to MSB
   
        let count = 0;
        // Initialize result
        while (n > 0) {
            // If the current bit is 0, then
            // there are 2^k numbers with
            // current bit 1 and whose XOR
            // with n produces greater value
            if ((n & 1) == 0)
                count += (Math.pow(2, k));
   
            // Increase position for next bit
            k += 1;
   
            // Reduce n to find next bit
            n >>= 1;
        }
   
        return count;
    }
 
// Driver Code
     
    let n = 11;
    document.write(countNumbers(n));
         
</script>

Producción: 

4

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)

Este artículo es una contribución de Smarak Chopdar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

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

Deja una respuesta

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