Count numbers 1 in binary number after decimal base conversion

Question

In this program I need to count the number 1 present in the binary number after decimal base conversion. Follow the code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>


int main ()
{

    char valor[1000], tmp;
    long long int count, valor_i, valor_c = 0, r_div, i, count2;

    scanf("%lld", &valor_i);

    count = 0;
    i = 0;

    while (i != 1)
    {
        r_div =  valor_i / 2;

        if (r_div < 2)
        {
            i = 1;
            if(valor_i % 2 == 0)
            {
                valor[count] = '0';
            }
            else
            {
                valor[count] = '1';
            }
            if(r_div == 0)
            {
                valor[count + 1] = '0';
            }
            else
            {
                valor[count + 1] = '1';
            }
            valor[count + 2] = '\0';
        }
        else
        {
            if (valor_i % 2 == 0)
            {
                valor[count] = '0';
            }
            else
            {
                valor[count] = '1';
            }
        }
        count++;
        valor_i = r_div;
    }

    count2 = strlen(valor) - 1;

    for(count = 0; count == count2 || count < count2; count++)
    {
        tmp = valor[count];
        valor[count] = valor[count2];
        valor[count2] = tmp;
        count2--;
    }
    printf("%s\n", valor);

    return 0;

}

Answer 1

A simple way to do it:

#include<stdio.h>
#include<string.h>

int main() {
    char valor[1000];
    long long int valor_i;
    int position = 0, count = 0;
    scanf("%lld", &valor_i);
    while (valor_i > 0) { //não precisa de flag, use a condição que encerra o laço
        int bit = valor_i % 2; //descobre se é 0 ou 1
        valor[position++] = '0' + bit; //adiciona o caractere de acordo com o bit calculado
        count += bit; //adiciona 0 ou 1 no contador
        valor_i /= 2; //vamos pra próxima, resolvemos metade do valor
    }
    valor[position] = '\0'; //termina a string
    size_t size = strlen(valor); //vai começar inverter a string
    for (int count = 0; count <= size / 2 - 1; count++) { //basta inverter até a metade
        char tmp = valor[count];
        valor[count] = valor[size - count - 1]; //não precisa de dois contadores
        valor[size - count - 1] = tmp;
    }
    printf("%s - quantidade de '1' => %d\n", valor, count);
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

I changed the variables' names a little bit, but I left the main ones, although I don’t agree with them.

I organized the code and simplified it, doing only what was necessary using mathematics.

The big change to solve the count of 1 was to put a counter inside the adding loop whenever it was a.

I would prefer to have some constraints and facilitate the algorithm, but I left it as it is. I could avoid having to do the inversion. I made an example working in the ideone. And in the repl it.. Also put on the Github for future reference.

#include<stdio.h>
#include<string.h>
#include<stdint.h>

int main() {
    char binario[64];
    memset(binario, '0', 63);
    binario[63] = '\0';
    int64_t decimal;
    scanf("%jd", &decimal);
    int position = 62, count = 0;
    while (decimal > 0) {
        int bit = decimal & 1;
        binario[position--] = '0' + bit;
        count += bit;
        decimal /= 2;
    }
    printf("%s - quantidade de '1' => %d", &binario[position + 1], count);
}

Answer 2

Use a for:

for (i=0; i<strlen(valor); i++){

     if(valor[i]=='1'){
        count++;
     }
}

Answer 3

The algorithm capable of solving the proposed problem is known by several names: Hamming Weight, Population Count, popcount or Sideways Sum.

Wikipedia has an excellent article talking deeply on the subject here.

There is a solution to this problem proposed in Capítulo 2.9 of the Second Edition of famous book "The C Programming Language" published by the duo "Kernighan & Ritchie".

It follows a function (tested and commented) capable of counting the number of bits set in the binary representation of a decimal number, based on the solution proposed in the book:

int popcount( unsigned int num )
{
    unsigned int count = 0; /* Inicia o contador com 0  */

    while( num ) /* Enquanto houverem bits setados... */
    {
        num &= num - 1; /* Limpa o bit setado mais significante */

        count++; /* Incrementa contador de bits setados */
    }

    return count; /* Retorna o contador */
}

Follows complete code capable of solving the problem:

/* ************************************************************************** */
/* *                              popcount.c                                * */
/* ************************************************************************** */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>


char * byte_to_binary( unsigned int num )
{
    unsigned int i = 0;
    static char str[ 100 ] = {0};

    strcpy( str, "" );

    for( i = 128; i > 0; i >>= 1 )
        strcat( str, ((num & i) == i) ? "1" : "0");

    return str;
}


int popcount( unsigned int num )
{
    unsigned int count = 0;

    while( num )
    {
        num &= num - 1;

        count++;
    }

    return count;
}


int main( int argc, char ** argv )
{
    int i = 0;

    for( i = 0; i < 16; i++)
        printf( "dec=%d, hex=0x%x, bin=%s, popcount=%d\n", i, i, byte_to_binary(i), popcount(i) );

    return 0;
}

/* fim-de-arquivo */

Exit:

$ ./popcount 
dec=0, hex=0x0, bin=00000000, popcount=0
dec=1, hex=0x1, bin=00000001, popcount=1
dec=2, hex=0x2, bin=00000010, popcount=1
dec=3, hex=0x3, bin=00000011, popcount=2
dec=4, hex=0x4, bin=00000100, popcount=1
dec=5, hex=0x5, bin=00000101, popcount=2
dec=6, hex=0x6, bin=00000110, popcount=2
dec=7, hex=0x7, bin=00000111, popcount=3
dec=8, hex=0x8, bin=00001000, popcount=1
dec=9, hex=0x9, bin=00001001, popcount=2
dec=10, hex=0xa, bin=00001010, popcount=2
dec=11, hex=0xb, bin=00001011, popcount=3
dec=12, hex=0xc, bin=00001100, popcount=2
dec=13, hex=0xd, bin=00001101, popcount=3
dec=14, hex=0xe, bin=00001110, popcount=3
dec=15, hex=0xf, bin=00001111, popcount=4

I hope I’ve helped!