Algorithm to find the sequence of bits that makes up to a given number

Question

int* binary (int nBits, int number)
{
    int*    bits    = calloc(abs(number)+1, sizeof(int));
    int     i       = 0;
    int     l       = nBits - 1;

    while(number > 0)
    {
        while(l >= 0)
        {
            int ln = 1 << l;

            if(ln < number)
            {
                bits[i] = ln;
                i++;
                number -= ln;
            }
            else if(ln > number)
            {
                l--;
            }
            else /* Equal */
            {
                bits[i] = ln;
                i++;
                number -= ln;
                return bits;
            }
        }
    }

    return bits;
}

I wrote this function in one go so it is probably quite rustic and I was curious to see what will happen if I subjected it to a review.

Provided any decimal @number and number of bits @nBits (for example 3 would mean that the function has to work with 1, 2, 4 bit representations) the function shall return the smallest sequence of bit representations (as an array of ints) that when added, makes up to @number In case the number is too big, bits may repeat.

I only tested it with the numbers 0-20 for which the result is:

0:
1: 1
2: 2
3: 2 1
4: 4
5: 4 1
6: 4 2
7: 4 2 1
8: 4 4
9: 4 4 1
10: 4 4 2
11: 4 4 2 1
12: 4 4 4
13: 4 4 4 1
14: 4 4 4 2
15: 4 4 4 2 1
16: 4 4 4 4
17: 4 4 4 4 1
18: 4 4 4 4 2
19: 4 4 4 4 2 1
20: 4 4 4 4 4

I am pretty sure the code can be optimized in terms of code quality, performance and memory. I intend to use it as an optimization for a large quantity of small entities in a game that I've been working on.

---

Example purpose:

Imagine in a game two objects A and B and we must create N number of entities E between them depending on the distance between A and B. Now to do that, C must be 1 pixel wide or tall (depending on the direction), which can result in a lot of C being created, which is inefficient. I figured I can draw the C entities with varying length (1, 2, 4, as much as I find for sufficient) and use such a function to distribute the appropriate number of them with the appropriate length. That way I will have much less entities created, but the line Cs make across A and B will be the same.

Answer 1

The function has Undefined Behaviour. Since calloc() can return a null pointer, we must not dereference bits (e.g. using bits[i]) unless we're sure it has a non-null value.

We're missing necessary includes to define calloc and abs.

We start off allowing for negative values, but then return any empty sequence (all zero). We should either handle them fully (it's not clear from the description what the expected results should be), reject them outright (return a null pointer, perhaps? Or change the argument to an unsigned type?), or return a minimal empty set.

The documentation needs to be a bit more specific (well, we need to have some documentation at all). Notably, users need to know that the function returns memory that requires free() to release, and how to interpret the result array (it seems to be 0-terminated).

There's no documentation on the valid range of nBits, nor any checking of it. Why do we accept negative values here? And values larger than CHAR_BIT * sizeof (int) are unlikely to work how users expect right now.

The use of l as a variable name is a poor choice. It's far too similar to 1 (and I) at a glance, which makes it hard to quickly comprehend the code.

We appear to over-allocate by a large amount. That calculation is very pessimistic and therefore wasteful. It shouldn't be too hard to compute the correct length to allocate.

Since we are change-making using a complete binary sequence of coins, the repeated subtraction is unnecessary. For positive numbers, we can simply mask bits to obtain the count of max-value coins and the presence or absence of the smaller ones. (E.g. the number of max-value coins is simply number >> nBits).

We could avoid allocating entirely, if we change our result format to return the count of each value returned, and require the user to provide a buffer of nBits + 1 in length for the result.

Answer 2

In addition to Toby's excellent advice, I'd like to point out that the code can be simplified without changing the algorithm.

I'll keep your variable names so that the suggested changes can be more easily compared with the original code.

First note that l in the inner loop can never decrease to zero. Therefore the inner loop while(l >= 0) is not needed at all:

while (number > 0) {
    int ln = 1 << l;
    
    if (ln < number) {
        bits[i] = ln;
        i++;
        number -= ln;
    } else if (ln > number) {
        l--;
    } else /* Equal */ {
        bits[i] = ln;
        i++;
        number -= ln;
        return bits;
    }
}

Now we see that there is no need to distinguish between the cases ln < number and ln <= number. In the latter case, number will become zero and the (outer) loop terminates. The early return is not needed:

while (number > 0) {
    int ln = 1 << l;
    
    if (ln <= number) {
        bits[i] = ln;
        i++;
        number -= ln;
    } else if (ln > number) {
        l--;
    }
}

Finally, instead of computing the “bit mask” 1 << l in each iteration, we can compute it once and update it by shifting. The variable l is no longer needed.

int ln = 1 << (nBits - 1);
while (number > 0) {
    if (ln <= number) {
        bits[i] = ln;
        i++;
        number -= ln;
    } else {
        ln >>= 1;
    }
}