Valor XOR máximo de elementos k como máximo de 1 a n

Te dan dos enteros positivos n y k. Debe calcular el valor XOR máximo posible de, como máximo, k elementos de 1 a n. 
Nota: k > 1
Ejemplos: 
 

Input : n = 7, k = 3
Output : 7
Explanation : You can select 1, 2, 4 for maximum XOR-value

Input : n = 7, k = 2
Output : 7
Explanation : You can select 3 and 4 for maximum value.

Para cualquier valor de k, podemos seleccionar al menos dos números del 1 al n y, para obtener el resultado requerido, debemos observar más de cerca la representación de bits de n. Así que vamos a entenderlo a través de un ejemplo. Supongamos que n = 6 y k = 2: 
Representación de bits de 6 = 110 
Representación de bits de 5 = 101 
Representación de bits de 4 = 100 
Representación de bits de 3 = 011 
Representación de bits de 2 = 010 
Representación de bits de 1 = 001
Ahora, puede ver que después de seleccionar tantos números como desee y seleccionar cualquiera de ellos, no puede obtener un valor XOR mayor que 111, es decir, 7. Entonces, para un n y k > 1 dado, el valor XOR máximo posible es 2 ^log2(n)+1 -1 (Ese es el valor cuando todos los bits de n se convierten en 1). 
 

// Program to obtain maximum XOR value sub-array
#include <bits/stdc++.h>
using namespace std;
 
// function to calculate maximum XOR value
int maxXOR(int n, int k) {
  int c = log2(n) + 1;
 
  // Return (2^c - 1)
  return ((1 << c) - 1);
}
 
// driver program
int main() {
  int n = 12;
  int k = 3;
  cout << maxXOR(n, k);
  return 0;
}

// Program to obtain maximum
// XOR value sub-array
import java.lang.*;
 
class GFG
{
// function to calculate
// maximum XOR value
static int maxXOR(int n, int k)
{
int c = (int) (Math.log(n) /
               Math.log(2)) + 1;
 
// Return (2^c - 1)
return ((1 << c) - 1);
}
 
// Driver Code
public static void main(String[] args)
{
int n = 12;
int k = 3;
System.out.println(maxXOR(n, k));
}
}
 
// This code is contributed by Smitha

# Python3 program to obtain maximum
# XOR value sub-array
import math
 
# Function to calculate maximum XOR value
def maxXOR(n, k):
    c = int(math.log(n, 2)) + 1
 
    # Return (2^c - 1)
    return ((1 << c) - 1)
 
# Driver Code
n = 12; k = 3
print (maxXOR(n, k))
 
# This code is contributed by shreyanshi_arun.

// Program to obtain maximum
// XOR value sub-array
using System;
 
class GFG
{
// function to calculate
// maximum XOR value
static int maxXOR(int n, int k)
{
int c = (int) (Math.Log(n) /
               Math.Log(2)) + 1;
 
// Return (2^c - 1)
return ((1 << c) - 1);
}
 
// Driver Code
public static void Main(String[] args)
{
int n = 12;
int k = 3;
Console.Write(maxXOR(n, k)) ;
}
}
 
// This code is contributed by Smitha

<?php
// Program to obtain maximum
// XOR value sub-array
 
// function to calculate
// maximum XOR value
function maxXOR($n, $k)
{
    $c = log($n, 2) + 1;
     
    // Return (2^c - 1)
    return ((1 << $c) - 1);
}
 
// Driver Code
$n = 12;
$k = 3;
echo maxXOR($n, $k);
 
// This code is contributed by aj_36
?>

<script>
 
// JavaScript program to obtain maximum
// XOR value sub-array
 
// function to calculate
// maximum XOR value
function maxXOR(n, k)
{
let c = (Math.log(n) /
               Math.log(2)) + 1;
   
// Return (2^c - 1)
return ((1 << c) - 1);
}   
  
// Driver code
 
        let n = 12;
        let k = 3;
        document.write(maxXOR(n, k));
 
</script>

15

Complejidad de tiempo : O(1)

Complejidad espacial : O(1)