Recuento de bits totales alternados/volteados en representación binaria de 0 a N

Dado un número entero N , la tarea es encontrar el número total de bits alternados para obtener todos los números de 0 a N secuencialmente.

Ejemplos:

Entrada: N = 5 
Salida: 8 
Explicación: 
Representemos los números del 0 al 5 en binario: 
000 -> 001 : 1 bit alternado 
001 -> 010 : 2 bits alternados 
010 -> 011 : 1 bit alternado 
011 -> 100 : 3 bits alternados 
100 -> 101: 1 bit alternado 
Por lo tanto, 8 bits alternados

Entrada: N = 1 
Salida: 1

Enfoque: 
siga los pasos a continuación para resolver los problemas:

• Es necesario hacer las siguientes observaciones para resolver el problema:

 
 El bit más a la derecha cambia cada vez. 
(00 0 ) -> (00 1 ) -> (01 0 ) -> (01 1 ) 
Entonces, la contribución de este bit al conteo será N . 
El siguiente bit cambia después de cada 2 números. 
(0 0 0) -> (0 0 1) -> (0 1 0) -> (0 1 1) -> (1 0 0) 
Por lo tanto, la contribución de este bit a la cuenta será N/2 .

 

• Por lo tanto, podemos concluir que el i ^-ésimo bit menos significativo contribuirá con N/( ²ⁱ ) al recuento de alternancias.
• Por lo tanto, la suma de N/(2 ⁱ ) donde i está en el rango [0, log ₂ N] da la respuesta requerida.
• Por lo tanto, inicialice una variable ans . Agregue N a ans y actualice N a N/2 . Repita este proceso hasta que N se convierta en 0, para obtener el resultado final.

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

// C++ program to count
// the number of toggles
// required to generate
// all numbers from 0 to N
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
 
// Function to count and print
// the required number of
// toggles
void solve(ll N)
{
    // Store the count
    // of toggles
    ll ans = 0;
 
    while (N != 0) {
 
        // Add the contribution
        // of the current LSB
        ans += N;
 
        // Update N
        N /= 2;
    }
    // Print the result
    cout << ans << endl;
}
// Driver code
int main()
{
    ll N = 5;
    solve(N);
    return 0;
}

// Java program to count the
// number of toggles required
// to generate all numbers
// from 0 to N
class GFG{
 
// Function to count and print
// the required number of
// toggles
static void solve(int N)
{
     
    // Store the count
    // of toggles
    int ans = 0;
 
    while (N != 0)
    {
         
        // Add the contribution
        // of the current LSB
        ans += N;
 
        // Update N
        N /= 2;
    }
     
    // Print the result
    System.out.println(ans);
}
 
// Driver code
public static void main(String []args)
{
    int N = 5;
     
    solve(N);
}
}
 
// This code is contributed by Ritik Bansal

# Python3 program to count
# the number of toggles
# required to generate
# all numbers from 0 to N
 
# Function to count and pr
# the required number of
# toggles
def solve(N):
     
    # Store the count
    # of toggles
    ans = 0
 
    while (N != 0):
 
        # Add the contribution
        # of the current LSB
        ans += N
 
        # Update N
        N //= 2
     
    # Print the result
    print(ans)
 
# Driver code
N = 5
 
solve(N)
 
# This code is contributed by code_hunt

// C# program to count the
// number of toggles required
// to generate all numbers
// from 0 to N
using System;
 
class GFG{
 
// Function to count and print
// the required number of
// toggles
static void solve(int N)
{
     
    // Store the count
    // of toggles
    int ans = 0;
 
    while (N != 0)
    {
         
        // Add the contribution
        // of the current LSB
        ans += N;
 
        // Update N
        N /= 2;
    }
     
    // Print the result
    Console.Write(ans);
}
 
// Driver code
public static void Main(string []args)
{
    int N = 5;
     
    solve(N);
}
}
 
// This code is contributed by rock_cool

<script>
 
// Javascript program to count the
// number of toggles required to
// generate all numbers from 0 to N
 
// Function to count and print
// the required number of
// toggles
function solve(N)
{
     
    // Store the count
    // of toggles
    let ans = 0;
 
    while (N != 0)
    {
         
        // Add the contribution
        // of the current LSB
        ans += N;
 
        // Update N
        N = parseInt(N / 2, 10);
    }
     
    // Print the result
    document.write(ans);
}
     
// Driver code   
let N = 5;
 
solve(N);
     
// This code is contributed by divyeshrabadiya07
 
</script>

Producción:

8

Complejidad temporal: O(log N)  
Espacio auxiliar: O(1)