Dado un número entero positivo N , la tarea es encontrar el recuento total de bits establecidos realizando Bitwise XOR en todos los elementos adyacentes posibles en el rango [0, N] .
Ejemplos:
Entrada: N = 4
Salida: 7
Explicación:
XOR bit a bit de 0 y 1 = 001 y conteo de bits establecidos = 1
XOR bit a bit de 1 y 2 = 011 y conteo de bits establecidos = 2
XOR bit a bit de 2 y 3 = 001 y conteo de bits establecidos = 1
XOR bit a bit de 3 y 4 = 111 y recuento de bits establecidos = 3
Por lo tanto, el recuento total de bits establecidos al realizar la operación XOR en todos los elementos adyacentes posibles del rango [0, N] = (1 + 2 + 1 + 3) = 7Entrada: N = 7
Salida: 11
Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre el rango [0, N] y contar todos los bits establecidos posibles realizando Bitwise XOR en cada elemento adyacente sobre el rango [0, N] . Finalmente, imprima el recuento total de todos los bits establecidos posibles.
Complejidad de tiempo: O(N * log 2 N)
Espacio auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
Si la posición del bit establecido más a la derecha de X es K , entonces el recuento de bits establecidos en (X ^ (X – 1)) debe ser K .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos bit_position para almacenar todos los valores posibles del bit más a la derecha en el rango [0, N] .
- Inicialice una variable, digamos total_set_bits para almacenar la suma de todos los bits establecidos posibles realizando la operación Bitwise XOR en todos los elementos adyacentes posibles en el rango [0, N] .
- Iterar sobre el rango [0, N] y Actualizar N = N – (N + 1) / 2 y total_set_bits += ((N + 1) / 2 * bit_position) .
- Finalmente, imprima el valor de total_set_bits .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count of set bits in Bitwise
// XOR of adjacent elements up to N
int countXORSetBitsAdjElemRange1_N(int N)
{
// Stores count of set bits by Bitwise
// XOR on adjacent elements of [0, N]
int total_set_bits = 0;
// Stores all possible values on
// right most set bit over [0, N]
int bit_Position = 1;
// Iterate over the range [0, N]
while (N) {
total_set_bits += ((N + 1) / 2
* bit_Position);
// Update N
N -= (N + 1) / 2;
// Update bit_Position
bit_Position++;
}
return total_set_bits;
}
// Driver Code
int main()
{
int N = 4;
cout << countXORSetBitsAdjElemRange1_N(N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to count of set bits in Bitwise
// XOR of adjacent elements up to N
static int countXORSetBitsAdjElemRange1_N(int N)
{
// Stores count of set bits by Bitwise
// XOR on adjacent elements of [0, N]
int total_set_bits = 0;
// Stores all possible values on
// right most set bit over [0, N]
int bit_Position = 1;
// Iterate over the range [0, N]
while (N != 0)
{
total_set_bits += ((N + 1) / 2 *
bit_Position);
// Update N
N -= (N + 1) / 2;
// Update bit_Position
bit_Position++;
}
return total_set_bits;
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
System.out.println(countXORSetBitsAdjElemRange1_N(N));
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program to implement # the above approach # Function to count of set bits in Bitwise # XOR of adjacent elements up to N def countXORSetBitsAdjElemRange1_N(N): # Stores count of set bits by Bitwise # XOR on adjacent elements of [0, N] total_set_bits = 0 # Stores all possible values on # right most set bit over [0, N] bit_Position = 1 # Iterate over the range [0, N] while (N): total_set_bits += ((N + 1) // 2 * bit_Position) # Update N N -= (N + 1) // 2 # Update bit_Position bit_Position += 1 return total_set_bits # Driver Code if __name__ == '__main__': N = 4 print(countXORSetBitsAdjElemRange1_N(N)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to count of set bits in Bitwise
// XOR of adjacent elements up to N
static int countXORSetBitsAdjElemRange1_N(int N)
{
// Stores count of set bits by Bitwise
// XOR on adjacent elements of [0, N]
int total_set_bits = 0;
// Stores all possible values on
// right most set bit over [0, N]
int bit_Position = 1;
// Iterate over the range [0, N]
while (N != 0)
{
total_set_bits += ((N + 1) / 2 *
bit_Position);
// Update N
N -= (N + 1) / 2;
// Update bit_Position
bit_Position++;
}
return total_set_bits;
}
// Driver Code
public static void Main()
{
int N = 4;
Console.Write(countXORSetBitsAdjElemRange1_N(N));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count of set bits in Bitwise
// XOR of adjacent elements up to N
function countXORSetBitsAdjElemRange1_N(N)
{
// Stores count of set bits by Bitwise
// XOR on adjacent elements of [0, N]
let total_set_bits = 0;
// Stores all possible values on
// right most set bit over [0, N]
let bit_Position = 1;
// Iterate over the range [0, N]
while (N) {
total_set_bits += (Math.floor((N + 1) / 2) * bit_Position);
// Update N
N -= Math.floor((N + 1) / 2);
// Update bit_Position
bit_Position++;
}
return total_set_bits;
}
// Driver Code
let N = 4;
document.write(countXORSetBitsAdjElemRange1_N(N));
// This code is contributed by _saurabh_jaiswal
</script>
7
Complejidad temporal: O(Log 2 N)
Espacio auxiliar: O(1)