Recuento de todos los valores posibles de X cuyo Bitwise XOR con N es mayor que N

Dado un número entero N , cuente el número de valores de X tales que  X ⊕ N > N ,  donde   ⊕ denota operación XOR bit a bit

Ejemplos:

Entrada: N = 10
Salida: 5 
Explicación: Los cinco valores posibles que satisfacen la condición anterior son :
1⊕10 = 11, 4⊕10 = 14, 5⊕10 = 15, 6⊕10 = 12, 7⊕10 = 13

Entrada: N = 8
Salida: 7
Explicación: Los siete valores posibles que satisfacen la condición anterior son:
1⊕8 = 9, 2⊕8 = 10, 3⊕8 = 11, 4⊕8 = 12, 5⊕8 = 13, 6 ⊕8 = 14, 7⊕8 = 15

Enfoque ingenuo: el enfoque simple para este problema es iterar de 1 a N e incrementar el conteo si  X XOR N >N   para 0 < X ​​< N . Finalmente, devuelva el recuento del número de valores.

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)

Enfoque eficiente: el enfoque más eficiente es encontrar el número más cercano a la siguiente potencia de 2 que tiene todos sus bits configurados y finalmente restarlo del número original. A continuación se muestra la observación matemática de la solución:

Si el número N se puede escribir usando k bits, entonces el número  X debe usar k-1 bits como máximo porque:

• Si un número X tiene los mismos bits que el número N , haciendo Xor ambos el número resultará en un número menor que N que no satisfará nuestra condición X xor N > N.
• Si un número X es mayor que el número N , al hacer Xoring en ambos, el número siempre dará como resultado que X es mayor que N , lo que no satisfará nuestra desigualdad.
  Entonces, el problema se reduce a encontrar la cuenta del número que se encuentra en el rango dado [x, 2 ^k – 1] . Estamos tomando 2 ^k – 1 porque este es el número máximo que se puede formar cuando se establecen todos sus n bits.
• El número requerido es igual a  2 ^k – 1 -N.

Siga los pasos a continuación para resolver el problema:

• Encuentra la siguiente potencia de 2 más cercana.
• Resta 1 de la potencia de 2 más cercana para que el número dado tenga todos sus bits establecidos
• Finalmente, resta del número original y devuélvelo

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for find the count of
// number of value of X such that  N XOR X >N
 
#include <bits/stdc++.h>
using namespace std;
 
// Function for  calculating the total
// possible value satisfy the condition
// X⊕N > N and 0 < X < N
void maximumXor(long long N)
{
    long long num = N;
    long long int count;
 
    count = 0;
    while (N > 0) {
 
        // Count the total number of bits
        count++;
        N = N / 2;
    }
    long long next_power = ((long long)1 << count);
 
    // Finding the next power of 2
    // of the given number
    long long result = next_power - 1;
 
    // Finding the number nearest to
    // the nextpower of 2 which has all
    // its bits set
    cout << result - num;
}
 
// Driver Code
int main()
{
    int N = 10;
    maximumXor(N);
    return 0;
}

// Java program for find the count of
// number of value of X such that  N XOR X >N
import java.util.*;
public class GFG {
 
  // Function for  calculating the total
  // possible value satisfy the condition
  // X⊕N > N and 0 < X < N
  static void maximumXor(long N)
  {
    long num = N;
    long count = 0;
 
    count = 0;
    while (N > 0) {
 
      // Count the total number of bits
      count++;
      N = N / 2;
    }
    long next_power = ((long)1 << count);
 
    // Finding the next power of 2
    // of the given number
    long result = next_power - 1;
 
    // Finding the number nearest to
    // the nextpower of 2 which has all
    // its bits set
    System.out.print(result - num);
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int N = 10;
    maximumXor(N);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# python3 program for find the count of
# number of value of X such that N XOR X >N
 
# Function for calculating the total
# possible value satisfy the condition
# X⊕N > N and 0 < X < N
def maximumXor(N):
 
    num = N
    count = 0
 
    while (N > 0):
 
        # Count the total number of bits
        count += 1
        N = N // 2
 
    next_power = (1 << count)
 
    # Finding the next power of 2
    # of the given number
    result = next_power - 1
 
    # Finding the number nearest to
    # the nextpower of 2 which has all
    # its bits set
    print(result - num)
 
# Driver Code
if __name__ == "__main__":
 
    N = 10
    maximumXor(N)
 
# This code is contributed by rakeshsahni

// C# program for find the count of
// number of value of X such that  N XOR X >N
using System;
 
public class GFG
{
 
  // Function for  calculating the total
  // possible value satisfy the condition
  // X⊕N > N and 0 < X < N
  static void maximumXor(long N)
  {
    long num = N;
    long count = 0;
 
    count = 0;
    while (N > 0) {
 
      // Count the total number of bits
      count++;
      N = N / 2;
    }
    long next_power = (1 << (int)count);
 
    // Finding the next power of 2
    // of the given number
    long result = next_power - 1;
 
    // Finding the number nearest to
    // the nextpower of 2 which has all
    // its bits set
    Console.Write(result - num);
  }
 
  // Driver Code
  public static void Main(String []args)
  {
    int N = 10;
    maximumXor(N);
  }
}
 
// This code is contributed by 29AjayKumar

<script>
       // JavaScript code for the above approach
 
       // Function for  calculating the total
       // possible value satisfy the condition
       // X⊕N > N and 0 < X < N
       function maximumXor(N) {
           let num = N;
           let count;
 
           count = 0;
           while (N > 0) {
 
               // Count the total number of bits
               count++;
               N = Math.floor(N / 2);
           }
           let next_power = (1 << count);
 
           // Finding the next power of 2
           // of the given number
           let result = next_power - 1;
 
           // Finding the number nearest to
           // the nextpower of 2 which has all
           // its bits set
           document.write(result - num);
       }
 
       // Driver Code
       let N = 10;
       maximumXor(N);
 
    // This code is contributed by Potta Lokesh
   </script>

5

Complejidad de tiempo : O(log(N))
Espacio auxiliar : O(1)