Suma de diferencias de bits para números de 0 a N

Dado un número N , la tarea es calcular el número total de bits diferentes correspondientes en la representación binaria para cada número consecutivo de 0 a N.
Ejemplos: 
 

Entrada: N = 5 
Salida:
Explicación: 
Representación binaria de números son: 
0 -> 000, 
1 -> 001, 
2 -> 010, 
3 -> 011, 
4 -> 100, 
5 -> 101 
Entre 1 y 0 – > 1 bit es diferente 
Entre 2 y 1 -> 2 bits son diferentes 
Entre 3 y 2 -> 1 bit es diferente 
Entre 4 y 3 -> 3 bits son diferentes 
Entre 5 y 4 -> 1 bit es diferente 
Total = 1 + 2 + 1 + 3 + 1 = 8
Entrada: N = 11 
Salida: 19 
 

Enfoque ingenuo: la idea es iterar de 0 a N y, para cada par de elementos consecutivos, encontrar la cantidad de bits diferentes para cada par de elementos utilizando el enfoque que se analiza en este artículo.
Complejidad de Tiempo: O(N*log N)  
Espacio Auxiliar: (1)
Enfoque Eficiente: Para el enfoque eficiente tenemos que observar lo siguiente: 
 

number:   1 2 3 4 5 6  7  8
bit_diff: 1 2 1 3 1 2  1  4
sum_diff: 1 3 4 7 8 10 11 15

De los cálculos anteriores podemos observar lo siguiente: 
 

  1. Si N es una potencia perfecta de 2, entonces la suma total de los diferentes bits correspondientes de 0 a N viene dada por: 
     

suma_diferencia = (2 x+1 -1) 
donde x = log2(N) 
 

  1.  
  2. Si N no es una potencia perfecta de 2, entonces se puede representar como la suma de la potencia perfecta de 2 como: 
     

norte = 2 un + 2 segundo + … + 2 x 
 

  1. Por lo tanto, la suma total de los diferentes bits correspondientes de 0 a N se puede calcular como: 
     

sum_diff = (2 a+1 -1) + (2 b+1 -1) + … + (2 x+1 -1). 
 

  1.  

Por ejemplo: 
 

Si N = 8, entonces 
La representación binaria de 8 es “1000” 
Por lo tanto, 11 = 2 3 
cuenta total = (2 3+1 – 1) 
cuenta total = 8 – 1 = 7.
Si N = 11, entonces 
La representación binaria de 11 es “1011” 
Por lo tanto, 11 = 2 3 + 2 1 + 2 0 
=> recuento total = (2 3+1 – 1) + (2 1+1 – 1) + (2 0+1 – 1) 
=> total cuenta = 15 + 3 + 1 = 19. 
 

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to implement fast
// exponentiation
int binpow(int a, int b)
{
    int res = 1;
 
    while (b) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b /= 2;
    }
    return res;
}
 
// Function to return the value
// for powers of 2
int find(int x)
{
    if (x == 0)
        return 0;
    int p = log2(x);
    return binpow(2, p + 1) - 1;
}
 
// Function to convert N into binary
string getBinary(int n)
{
    // To store binary representation
    string ans = "";
 
    // Iterate each digit of n
    while (n) {
        int dig = n % 2;
        ans += to_string(dig);
        n /= 2;
    }
 
    // Return binary representation
    return ans;
}
 
// Function to find difference in bits
int totalCountDifference(int n)
{
    // Get binary representation
    string ans = getBinary(n);
 
    // total number of bit
    // differences from 0 to N
    int req = 0;
 
    // Iterate over each binary bit
    for (int i = 0; i < ans.size(); i++) {
 
        // If current bit is '1' then add
        // the count of current bit
        if (ans[i] == '1') {
 
            req += find(binpow(2, i));
        }
    }
    return req;
}
 
// Driver Code
int main()
{
    // Given Number
    int N = 5;
 
    // Function Call
    cout << totalCountDifference(N);
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.Math;
 
class GFG{
     
// Function to implement fast
// exponentiation
static int binpow(int a, int b)
{
    int res = 1;
 
    while (b > 0)
    {
        if (b % 2 == 1)
            res = res * a;
        a = a * a;
        b /= 2;
    }
    return res;
}
 
// Function to return the
// value for powers of 2
static int find(int x)
{
    if (x == 0)
        return 0;
         
    int p = (int)(Math.log(x) / Math.log(2));
    return binpow(2, p + 1) - 1;
}
 
// Function to convert N into binary
static String getBinary(int n)
{
     
    // To store the binary representation
    String ans = "";
 
    // Iterate each digit of n
    while (n > 0)
    {
        int dig = n % 2;
        ans += dig;
        n /= 2;
    }
 
    // Return binary representation
    return ans;
}
 
// Function to find difference in bits
static int totalCountDifference(int n)
{
     
    // Get binary representation
    String ans = getBinary(n);
 
    // total number of bit
    // differences from 0 to N
    int req = 0;
 
    // Iterate over each binary bit
    for(int i = 0; i < ans.length(); i++)
    {
        
       // If current bit is '1' then add
       // the count of current bit
       if (ans.charAt(i) == '1')
       {
           req += find(binpow(2, i));
       }
    }
    return req;
}
 
// Driver code
public static void main (String[] args)
{
    // Given number
    int n = 5;
     
    System.out.print(totalCountDifference(n));
}
}
 
// This code is contributed by spp____

Python3

# Python3 program for the above approach
from math import log
 
# Function to implement fast
# exponentiation
def binpow(a, b):
     
    res = 1
    while (b > 0):
        if (b % 2 == 1):
            res = res * a
        a = a * a
        b //= 2
    return res
 
# Function to return the value
# for powers of 2
def find(x):
     
    if (x == 0):
        return 0
    p = log(x) / log(2)
    return binpow(2, p + 1) - 1
 
# Function to convert N into binary
def getBinary(n):
     
    # To store binary representation
    ans = ""
     
    # Iterate each digit of n
    while (n > 0):
        dig = n % 2
        ans += str(dig)
        n //= 2
     
    # Return binary representation
    return ans
 
# Function to find difference in bits
def totalCountDifference(n):
     
    # Get binary representation
    ans = getBinary(n)
     
    # total number of bit
    # differences from 0 to N
    req = 0
     
    # Iterate over each binary bit
    for i in range(len(ans)):
         
        # If current bit is '1' then add
        # the count of current bit
        if (ans[i] == '1'):
            req += find(binpow(2, i))
    return req
 
# Driver Code
 
# Given Number
N = 5
 
# Function Call
print(totalCountDifference(N))
 
# This code is contributed by shubhamsingh10

C#

// C# program for the above approach
using System;
class GFG{
     
// Function to implement fast
// exponentiation
static int binpow(int a, int b)
{
    int res = 1;
 
    while (b > 0)
    {
        if (b % 2 == 1)
            res = res * a;
        a = a * a;
        b /= 2;
    }
    return res;
}
 
// Function to return the
// value for powers of 2
static int find(int x)
{
    if (x == 0)
        return 0;
         
    int p = (int)(Math.Log(x) / Math.Log(2));
    return binpow(2, p + 1) - 1;
}
 
// Function to convert N into binary
static String getBinary(int n)
{
     
    // To store the binary representation
    String ans = "";
 
    // Iterate each digit of n
    while (n > 0)
    {
        int dig = n % 2;
        ans += dig;
        n /= 2;
    }
 
    // Return binary representation
    return ans;
}
 
// Function to find difference in bits
static int totalCountDifference(int n)
{
     
    // Get binary representation
    string ans = getBinary(n);
 
    // total number of bit
    // differences from 0 to N
    int req = 0;
 
    // Iterate over each binary bit
    for(int i = 0; i < ans.Length; i++)
    {
        
       // If current bit is '1' then add
       // the count of current bit
       if (ans[i] == '1')
       {
           req += find(binpow(2, i));
       }
    }
    return req;
}
 
// Driver code
public static void Main()
{
    // Given number
    int n = 5;
     
    Console.Write(totalCountDifference(n));
}
}
 
// This code is contributed by Nidhi_biet

Javascript

<script>
// Javascript program for the above approach\
 
// Function to implement fast
// exponentiation
function binpow(a, b) {
    let res = 1;
 
    while (b) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b = Math.floor(b / 2);
    }
    return res;
}
 
// Function to return the value
// for powers of 2
function find(x) {
    if (x == 0)
        return 0;
    let p = Math.log2(x);
    return binpow(2, p + 1) - 1;
}
 
// Function to convert N into binary
function getBinary(n) {
    // To store binary representation
    let ans = "";
 
    // Iterate each digit of n
    while (n) {
        let dig = n % 2;
        ans += String(dig);
        n = Math.floor(n / 2);
    }
 
    // Return binary representation
    return ans;
}
 
// Function to find difference in bits
function totalCountDifference(n)
{
 
    // Get binary representation
    let ans = getBinary(n);
 
    // total number of bit
    // differences from 0 to N
    let req = 0;
 
    // Iterate over each binary bit
    for (let i = 0; i < ans.length; i++) {
 
        // If current bit is '1' then add
        // the count of current bit
        if (ans[i] == '1') {
 
            req += find(binpow(2, i));
        }
    }
    return req;
}
 
// Driver Code
 
// Given Number
let N = 5;
 
// Function Call
document.write(totalCountDifference(N));
 
// This code is contributed by _saurabh_jaiswal
</script>
Producción: 

8

 

Complejidad de Tiempo: O((log N) 2 )  
Espacio Auxiliar: (1)
 

Publicación traducida automáticamente

Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *