Recuento de valores distintos para XOR bit a bit de X e Y para X, Y como máximo N

Dado un número entero N , la tarea es encontrar el número de valores distintos posibles para el XOR bit a bit de X e Y donde 1 ≤ X, Y ≤ N.

Ejemplos:

Entrada: N = 1
Salida: 1
Explicación: Los posibles valores de xor son 1⊕1=0 que tiene 1 valor único.

Entrada: N = 2
Salida: 2
Explicación: Los posibles valores de xor son 1⊕1 = 0, 1⊕2 = 1, 2⊕2 = 0 que tiene 2 valores únicos.

Planteamiento: Para los valores de N igual a 1 y 2 , la respuesta es simple. Para los casos restantes, considere N≥3. Considere p como la potencia más alta para la cual 2^p ≤ N. Suponga que 2^p < N , entonces se pueden obtener todos los números de 0 a 2^{p+1} -1 . Esto se puede lograr de la siguiente manera:

Por ejemplo,  
sea N = 12, luego x = 3. 
El número 12 (1100 en binario) puede estar formado por (2^3(1000), 4(0100)).
Por la propiedad de xor, num⊕1 es num +1 o num -1. 
Entonces, si 1 < num ≤ 2^p < N, 1 ≤ num⊕1 ≤ N. 
Por lo tanto, estos pares de números siempre serán válidos.

Ahora, ¿qué pasa si 2^p = N? Todos los casos anteriores son válidos excepto el caso de num = 2^p. Esto no se puede obtener de ningún par xor (X, Y) donde (1 ≤ X, Y ≤ 2^p) . Dado que el único número con el bit p establecido es 2^p , debemos mantener i = 2^p . Entonces para X ⊕ Y=2*p, Mantenga Y = 0 , lo cual no se puede hacer ya que Y ≥ 1 . Por lo tanto, en este caso, excepto 2^p , x o par para cualquier número de 0 a 2^{p + 1} -1 se puede obtener. Siga los pasos a continuación para resolver el problema:

• Inicialice la variable ans como 1.
• Si N es igual a 2 , imprima 2 y regrese.
• Recorra un ciclo while hasta que ans sea menor que N y multiplique ans por 2.
• Si ans es igual a N , multiplique ans por 2 y reduzca su valor en 1.
• Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int MOD = 1e9 + 7;
 
// Function to find the possible values
void find(long long N)
{
    long long ans = 1;
 
    // Special case
    if (N == 2) {
        cout << 2 << endl;
        return;
    }
 
    while (ans < N) {
        ans *= 2;
    }
 
    if (ans == N) {
        ans *= 2;
        ans--;
    }
 
    cout << ans % MOD;
}
 
// Driver Code
int main()
{
    long long N = 7;
    find(N);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to find the possible values
  static void find(long N)
  {
    long MOD = 1000000007;
    long ans = 1;
 
    // Special case
    if (N == 2) {
      System.out.println("2");
      return;
    }
 
    while (ans < N) {
      ans *= 2;
    }
 
    if (ans == N) {
      ans *= 2;
      ans--;
    }
    long temp = ans % MOD;
    System.out.print(temp);
  }
 
  // Driver Code
  public static void main (String[] args) {
    long N = 7;
    find(N);
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python program for the above approach
 
# Function to find the possible values
def find(N):
   
    MOD = 1000000007
    ans = 1
 
    # Special case
    if (N == 2):
        print(2)
        return;
 
    while ans < N:
        ans *= 2
     
 
    if (ans == N):
        ans *= 2
        ans -= 1
 
    print(ans % MOD)
 
if __name__ == "__main__":
 
    N = 7
    find(N)
    
  # This code is contributed by hrithikgarg03188.

// C# program to implement
// the above approach
using System;
class GFG
{
 
// Function to find the possible values
  static void find(long N)
  {
    long MOD = 1000000007;
    long ans = 1;
 
    // Special case
    if (N == 2) {
      Console.WriteLine("2");
      return;
    }
 
    while (ans < N) {
      ans *= 2;
    }
 
    if (ans == N) {
      ans *= 2;
      ans--;
    }
    long temp = ans % MOD;
    Console.Write(temp);
  }
 
// Driver Code
public static void Main()
{
    long N = 7;
    find(N);
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
       let MOD = 1e9 + 7;
 
       // Function to find the possible values
       function find(N)
       {
           let ans = 1;
 
           // Special case
           if (N == 2) {
               document.write(2 + '<br>')
               return;
           }
           while (ans < N) {
               ans *= 2;
           }
           if (ans == N) {
               ans *= 2;
               ans--;
           }
           document.write(ans % MOD);
       }
 
       // Driver Code
       let N = 7;
       find(N);
 
      // This code is contributed by Potta Lokesh
   </script>

8

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