Encuentre todos los M en el rango [2, N] tales que bit a bit OR hasta que M sea igual al valor hasta M-1

Dado un entero N , la tarea es encontrar todos los enteros M posibles en el rango [2, N] de modo que el OR bit a bit de todos los valores positivos hasta M sea el mismo que el OR bit a bit de todos los valores positivos hasta M-1 .

Ejemplos:

Entrada : N = 4
Salida : 1
Explicación : Bitwise OR hasta 3 = 1 | 2 | 3 = 3.
O bit a bit hasta 2 = 1 | 2 = 3.

Entrada : N = 7
Salida : 4

Enfoque: El enfoque para resolver este problema se basa en la siguiente observación:

Considere p(x) al OR bit a bit hasta x. Entonces p(x) = 1 | 2 | 3 | . . . | (x-1) | x
Dado p(x) = 1 | 2 | 3 | . . . | x – 1 | X. Por lo tanto, p(x + 1) será diferente de p(x) si hay un nuevo bit «1» en (x + 1) que no está presente en la secuencia binaria de p(x).

Ahora, observemos el patrón:

Número decimal	Número binario
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001

Podemos ver que un nuevo bit «1» que no ha aparecido previamente en el rango [1, x] aparece en cada potencia de 2.
Como tal, p(x) = 1 | 2 | 3 | . . . | x – 1 | x 
                     = 2 ^a+1 – 1 , donde a = log ₂ x. Esto implica que, para un a
dado , habrá ( 2 ^{a + 1} – 2 ^a – 1 ) valores de x donde p(x) = p(x – 1).

Siga el siguiente paso para resolver este problema:

• Calcular a = log ₂ N. 
• Iterar a través de las potencias (por ejemplo, usando la variable exp ) de 2 de 1 a a e incrementar ans (inicialmente 0) en (2 ^{exp + 1} – 2 ^exp – 1) .
• Finalmente, cuente los pares entre N y 2 ^a sumando (n – 2 ^a ) a ans .

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// total matches in the range
int checkXORrange(int n)
{
    int ans = 0;
    int a = log2(n);
 
    for (int exp = 1; exp <= a; exp++)
        ans += pow(2, exp) - pow(2, exp - 1) - 1;
 
    ans += n - pow(2, a);
    return ans;
}
 
// Driver code
int main()
{
    int N = 7;
 
    // Function call
    cout << checkXORrange(N) << endl;
    return 0;
}

// C code to implement the approach
 
#include <math.h>
#include <stdio.h>
 
// Function to calculate
// total matches in the range
int checkXORrange(int n)
{
    int ans = 0;
    int a = log2(n);
    for (int exp = 1; exp <= a; exp++)
        ans += pow(2, exp) - pow(2, exp - 1) - 1;
    ans += n - pow(2, a);
    return ans;
}
 
// Driver code
int main()
{
    int N = 7;
 
    // Function call
    printf("%d\n", checkXORrange(N));
    return 0;
}

// Java code to implement the approach
import java.io.*;
 
class GFG {
  public static int log2(int N)
  {
 
    // calculate log2 N indirectly
    // using log() method
    int result = (int)(Math.log(N) / Math.log(2));
    return result;
  }
 
  // Function to calculate
  // total matches in the range
  public static int checkXORrange(int n)
  {
    int ans = 0;
    int a = log2(n);
 
    for (int exp = 1; exp <= a; exp++)
      ans += Math.pow(2, exp) - Math.pow(2, exp - 1)
      - 1;
 
    ans += n - Math.pow(2, a);
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 7;
 
    // Function call
    System.out.print(checkXORrange(N));
  }
}
 
// This code is contributed by Rohit Pradhan

// C# code to implement the approach
using System;
 
public class GFG {
 
  // Function to calculate
  // total matches in the range
  public static int checkXORrange(int n)
  {
    int ans = 0;
    int a = (int)Math.Log(n, 2);
 
    for (int exp = 1; exp <= a; exp++)
      ans += (int)(Math.Pow(2, exp)
                   - Math.Pow(2, exp - 1) - 1);
 
    ans += (int)(n - (Math.Pow(2, a)));
    return ans;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 7;
 
    // Function call
    Console.Write(checkXORrange(N));
  }
}
 
// This code is contributed by phasing17

# Python3 code to implement the approach
 
import math
 
# Function to calculate
# total matches in the range
def checkXORrange(n):
    ans = 0
    a = int(math.log2(n))
    for exp in range(1, a + 1):
        ans += 2 ** exp - 2 ** (exp - 1) - 1
    ans += n - 2 ** a
    return ans
 
# Driver Code
if __name__ == "__main__":
    N = 7
    print(checkXORrange(N))

<script>
    // JavaScript code to implement the approach
 
 
    // Function to calculate
    // total matches in the range
    const checkXORrange = (n) => {
        let ans = 0;
        let a = parseInt(Math.log2(n));
 
        for (let exp = 1; exp <= a; exp++)
            ans += Math.pow(2, exp) - Math.pow(2, exp - 1) - 1;
 
        ans += n - Math.pow(2, a);
        return ans;
    }
 
    // Driver code
 
    let N = 7;
 
    // Function call
    document.write(checkXORrange(N));
 
// This code is contributed by rakeshsahni
 
</script>

4

Complejidad del tiempo:
Espacio Auxiliar: