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

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.

• (You haven't been that active lately.) I was curious to see what will happen if I subjected it to a review CR is about insights into working code (from one of your projects). You may be prompted to tell more about what the code is intended for (How does this [optimise large quantities] of small entities?), and what makes you think it works. How about binary(30, 987654321)? Mar 3 at 7:43
• I can agree with half of what you said, but what is the point of telling more about what the code is intended for? I don't see a reason, at all. I need it for something so specific that the chances of even everyone in the community using it for this are insignificant. Instead, I am just sharing my code, in case someone finds it for useful. I don't require help or anything. Everyone is free to ignore it, in which case I might as well delete it. Or improve it myself. Mar 3 at 7:59
• What is a decimal @number, how do you pass it to binary(), and how would you pass a non-decimal one? Mar 3 at 8:33
• @TobySpeight this is essentially exacted what I stated later in the same comment. I did not change the code, because I don't want to potentially invalidate someone's answer in the process of writing it. Mar 3 at 8:47
• I possibly should have read the rest of the comment! ;-) Mar 3 at 8:49

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.

• It DOES NOT "have undefined behavior". The program compiles, executes and excerts undefined behavior only if calloc fails, which usually /but not always/ happens when large numbers are provided. Mar 3 at 8:50
• It's a semantic argument to say it has undefined behaviour only when we follow the code path where bits is null, given there is no way to guarantee that we never follow the other path. In the absence of any test, that path is reachable, which is why I say it does have UB. Mar 3 at 9:06
• That's quite a useful description and would make quite an improvement to the question - I recommend you edit to include that motivating statement! Mar 3 at 9:22
• What I did was to return the number the first bit repeats and use the array for the values. That also works. Mar 3 at 22:10
• The number >> nBits repeat count is so simple that this probably doesn't even need to be a separate function with an output format, just something you do as part of your drawing (?) or whatever other algorithm, with the full-size count generated in one place when you need it, and then the number & ((1<<nBits)-1) left-over elements done later. If you want to break that up further, you can start with size = 1<<(nBits-1); and if (size & number) then that bit is set so do that size. Otherwise not. size >>= 1; to right-shift it. This will iterate the low bits in number, @Edenia. Mar 4 at 2:33

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;
}
}

• Nice! That's what I expected. Mar 3 at 11:46