Número de enteros con un número impar de bits establecidos

Dado un número n, cuente el número de enteros menores o iguales a n que tienen un número impar de bits establecidos.
Ejemplos: 
 

Input : 5
Output : 3
Explanation :
Integers with odd number of 
set bits in range 1 to 5 :
0 contains 0 set bits
1 contains 1 set bits
2 contains 1 set bits
3 contains 2 set bits
4 contains 1 set bits
5 contains 2 set bits

Input : 10
Output : 5
Explanation :
Integers with odd set bits are 1, 2,
4, 7 and 8.

Requisitos previos: Contar el número de bits establecidos
La idea se basa en el siguiente hecho.
 

Si n es impar, entonces hay un total de n+1 enteros menores o iguales que n (0, 1, 2… n) y la mitad de estos enteros contienen un número impar de bits establecidos.

¿Cómo manejar el caso cuando n es par? Sabemos resultado para n-1. Contamos bits establecidos en n y sumamos 1 a n/2 si el conteo es impar. De lo contrario, devolvemos n/2.
 

// CPP code to find numbers with
// odd number of set bits
#include <bits/stdc++.h>
using namespace std;
 
// function that returns the number
// of integers with odd number of
// set bits
int countWithOddSetBits(int n)
{
    // If n is odd, then half of the
    // integers in (0, 1, .. n) contain
    // odd number of set bits.
    if (n % 2 != 0)
        return (n + 1) / 2;
 
    // If n is even, we know result for
    // n-1. We explicitly compute set bit
    // count in n.
    int count = __builtin_popcount(n);
 
    int ans = n / 2;
    if (count % 2 != 0)
        ans++;
    return ans;
}
 
// Driver code
int main()
{
    int n = 10;
    cout << countWithOddSetBits(n);
    return 0;
}

// C code to find numbers with
// odd number of set bits
#include <stdio.h>
 
// function that returns the number
// of integers with odd number of
// set bits
int countWithOddSetBits(int n)
{
    // If n is odd, then half of the
    // integers in (0, 1, .. n) contain
    // odd number of set bits.
    if (n % 2 != 0)
        return (n + 1) / 2;
 
    // If n is even, we know result for
    // n-1. We explicitly compute set bit
    // count in n.
    int count = __builtin_popcount(n);
 
    int ans = n / 2;
    if (count % 2 != 0)
        ans++;
    return ans;
}
 
// Driver code
int main()
{
    int n = 10;
    printf("%d",countWithOddSetBits(n));
    return 0;
}
 
// This code is contribute by kothavvsaaash.

// Java code to find numbers
// with odd number of set bits
import java.io.*;
 
class GFG
{
     
// function that returns the
// number of integers with
// odd number of set bits
static int countWithOddSetBits(int n)
{
    // If n is odd, then half
    // of the integers in
    // (0, 1, .. n) contain
    // odd number of set bits.
    if (n % 2 != 0)
        return (n + 1) / 2;
 
    // If n is even, we know
    // result for n-1. We
    // explicitly compute set
    // bit count in n.
    int count = (n);
 
    int ans = n / 2;
    if (count % 2 != 0)
        ans++;
    return ans;
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 10;
    System.out.println( countWithOddSetBits(n));
}
}
 
// This code is contributed by aj_36

# Python 3 code to find numbers with
# odd number of set bits
 
# function that returns the number
# of integers with odd number of
# set bits
def countWithOddSetBits(n):
     
    # If n is odd, then half of the
    # integers in (0, 1, .. n) contain
    # odd number of set bits.
    if (n % 2 != 0):
        return (n + 1) / 2
 
    # If n is even, we know result for
    # n-1. We explicitly compute set
    # bit count in n.
    count = bin(n).count('1')
 
    ans = n / 2
    if (count % 2 != 0):
        ans += 1
    return ans
 
# Driver code
if __name__ == '__main__':
    n = 10
    print(int(countWithOddSetBits(n)))
 
# This code is contributed by
# Surendra_Gangwar

// C# code to find numbers
// with odd number of set bits
using System;
 
class GFG
{
     
// function that returns the
// number of integers with
// odd number of set bits
static int countWithOddSetBits(int n)
{
    // If n is odd, then half
    // of the integers in
    // (0, 1, .. n) contain
    // odd number of set bits.
    if (n % 2 != 0)
        return (n + 1) / 2;
 
    // If n is even, we know
    // result for n-1. We
    // explicitly compute set
    // bit count in n.
    int count = (n);
 
    int ans = n / 2;
    if (count % 2 != 0)
        ans++;
    return ans;
}
 
// Driver Code
static public void Main ()
{
    int n = 10;
    Console.WriteLine(countWithOddSetBits(n));
}
}
 
// This code is contributed by ajit

<?php
// PHP code to find numbers with
// odd number of set bits
 
// function that returns the number
// of integers with odd number of
// set bits
function countWithOddSetBits($n)
{
    // If n is odd, then half of
    // the integers in (0, 1, .. n)
    // contain odd number of set bits.
    if ($n % 2 != 0)
        return ($n + 1) / 2;
 
    // If n is even, we know result
    // for n-1. We explicitly compute
    // set bit count in n.
    $count = ($n);
 
    $ans = $n / 2;
    if ($count % 2 != 0)
        $ans++;
    return $ans;
}
 
// Driver code
$n = 10;
echo countWithOddSetBits($n);
 
// This code is contributed by aj_36
?>

<script>
 
    // Javascript code to find numbers
    // with odd number of set bits
     
    // function that returns the
    // number of integers with
    // odd number of set bits
    function countWithOddSetBits(n)
    {
        // If n is odd, then half
        // of the integers in
        // (0, 1, .. n) contain
        // odd number of set bits.
        if (n % 2 != 0)
            return parseInt((n + 1) / 2, 10);
 
        // If n is even, we know
        // result for n-1. We
        // explicitly compute set
        // bit count in n.
        let count = (n);
 
        let ans = parseInt(n / 2, 10);
        if (count % 2 != 0)
            ans++;
        return ans;
    }
     
    let n = 10;
    document.write(countWithOddSetBits(n));
     
</script>

5