Thread: Determining cardinality

I'm taking a c programming course, and I don't have any idea where to start on a project. The project is to take a series of denary numbers inputted by the user (between 0 and 1023, I think), determine which have the highest cardinality (the number of ones when it's written in binary), and print the lowest number in the series with the highest cardinality.

The project is designed to make us use user-defined functions. I have a few ideas on how to determine the cardinality, which i will detail below, but I'm not even sure if that will work, or how to assemble the rest of the program. If someone could give me some pointers that would be awesome.

My idea on how to calculate cardinality:

Code:

int num; /*A number from the user*/
int lcv; /*The loop control variable*/
int card; /*The cardinality of num*/

for(lcv = 10; lcv >= 0; lcv--)
{
   if((num - (2^lcv)) >= 0)
      num = num - (2^lcv);
      card = card++;
}

printf("%d", card);

You're basically counting set bits in a value. This can be done easily by just testing the first bit and shifting right by one until the value is 0.

Code:

unsigned count(unsigned value)
{
    int n = 0;

    while (value != 0) {
        if (value & 1)
            n++;
        value >>= 1;
    }

    return n;
}

This is arguably the simplest way to get what you want. There are other methods, but they have a tendency toward being opaque.

I'm not sure I understand. Since the number the user inputs is denary, how are you testing whether it equals one or zero? Also, what does the ampersand in line 4 do?

how are you testing whether it equals one or zero?

How a number is represented is irrelevant when working with binary. Decimal, octal, hexadecimal are all the same when viewed as a sequence of bits. The code simply tests a single bit at a time with the bitwise AND operator.

Code:

if (value & 1)

This tests the first bit in value and the condition is true if that bit is not 0. If you haven't worked with the bitwise operators yet, the same effect can be achieved with simple arithmetic.

Code:

unsigned count(unsigned value)
{
    int n = 0;

    while (value != 0) {
        if (value % 2)
            n++;
        value /= 2;
    }

    return n;
}