Compare two version numbers

Question

Given two version numbers, version1 and version2, compare them.

Version numbers consist of one or more revisions joined by a dot '.'. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character.

To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their integer values ignoring any leading zeros. This means that revisions 1 and 001 are considered equal. If a version number does not specify a revision at an index, then treat the revision as 0. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.

int compareVersion(const char * v1, const char * v2)
{
    while (*v1 || * v2) 
    {
        int a=0, b=0;
        
        while (*v1 && *v1 != '.')  a = 10*a + (*v1++ - '0');
        while (*v2 && *v2 != '.')  b = 10*b + (*v2++ - '0');
        if (*v1) v1++;
        if (*v2) v2++;
        if (a < b) return -1;
        if (a > b) return +1;
    }
    return 0;
}

Answer 1

This code is nicely presented and easy to follow. It's immediately clear how it works.

For code like this, I strongly recommend writing unit tests to verify the behaviour and exercise the border-line cases. A good test case is compareVersion("1", "1.0"). This function considers those to be equal - that may or may not be a reasonable interpretation of the requirements, but it's worth documenting, perhaps in a comment. If we want 1.0 to sort greater than 1, then only a simple change is needed:

while (*v1 && * v2) 
{
    ⋮
}

return !*v2 - !*v1;

That last line may be cryptic enough to be worth a comment - it's based on the standard comparison idiom (a > b) - (b > a).

Another set of inputs that we should test is of invalid inputs - at the moment we'll get fairly arbitrary results if we're called with non-numeric characters in the input. Though I'm not really sure what we should do with them - perhaps ignore non-digits. Remember to convert to unsigned char if using standard isdigit() function!

Since version number components can't be negative, it might be better to use unsigned types for a and b. We could use strtoul() or similar to convert the digits to numbers, but hold that though - at present, there's no check for overflow, but we could make an overflow-proof version quite easily by identifying the significant digits in each component (i.e. ignoring leading zeros). If one component has more significant digits than the other, it's greater, otherwise compare the significant digits as strings (strncmp()).

Answer 2

Your code is clear in my opinion, I will suggest some improvements that are not really necessary on this scale but will help when you will start dealing with more complex and longer code:

Commenting the why

What are these lines doing:

    if (*v1) v1++;
    if (*v2) v2++;

They are skipping the dot right? This explains why you are doing the comparison and incrementing the counter, so add a comment:

    // Skip the dots
    if (*v1) v1++;
    if (*v2) v2++;

Self descriptive names

a and b are very generic names that could represent anything, I renamed them v1_current and v2_current

Modularity

What is

    while (*v1 && *v1 != '.')  a = 10*a + (*v1++ - '0');

doing? It is updating the value of a adding the value found between two dots, this can be extracted into a function to be tested separately to increase the robustness and readability of the code:

void update_count(const char * version, int *current_count) {
    // Update the current count with the value between the dots.
    while (*version && *version != '.')  (*current_count) = 10*(*current_count) + (*version++ - '0');
}

Automatic testing

How can I be sure that I did not break anything while doing these changes? A very lightweight automated testing using assert can benefit even simple project to making it simpler to both optimize and refactor the code.

Final revision

Here I applied all the improvements, the code is longer, but much of the added length are tests that can double as documentation for a potential future user and the helper function, that is a good practice.

#include <stdio.h>
#include <assert.h>

void update_count(const char * version, int *current_count) {
    // Update the current count with the value between the dots.
    while (*version && *version != '.')  (*current_count) = 10*(*current_count) + (*version++ - '0');
}

int compareVersion(const char * v1, const char * v2)
{
    // Compare two version numbers of the form
    // dd.d.dd where d is a digit (ex: 2.1.3 is bigger than 1.2.1)
    // Returns:
    //  +1 if the first version number is bigger than the second one
    //  -1 if the second one is bigger
    //   0 if they are equal

    while (*v1 || * v2) 
    {
        int v1_current=0, v2_current=0;
        
        // Read the number between two dots (or the first or last one)
        update_count(v1, &v1_current);
        update_count(v2, &v2_current);

        // Skip the dots
        if (*v1) v1++;
        if (*v2) v2++;

        // +1 if the first version number is bigger than the second one
        if (v1_current < v2_current) return -1;
        if (v1_current > v2_current) return +1;
    }
    return 0;
}

int main() {

    int a = 0;
    update_count("1.0.32", &a);
    assert(a == 1);

    int b = 0;
    update_count("23.4.1", &b);
    assert(b == 23);

    assert(compareVersion("1.0.32", "1.0.32") == 0);
    assert(compareVersion("1.0.32", "1.0.33") == -1);
    assert(compareVersion("1.0.36", "1.0.34") == 1);
    assert(compareVersion("2.0.32", "1.0.32") == 1);

}

Answer 3

Overflow

Using int can have trouble with integers as small as 32K. Consider a version using a time stamp of 14 digits as one of the fields 20220302101901. Use some unsigned type, perhaps uintmax_t. Even then I would consider detecting overflow - or see below.

What if non-digit or non-dot?

Since separators like ,, and letters are treated pathologically like digits, how about giving those meaning as separators and not using them to compute the version value?

// while (*v1 && *v1 != '.')  a = 10*a + (*v1++ - '0');
while (isdigit(*v1))  a = 10*a + (*v1++ - '0');

Pedantically, should use unsigned char values with is...()

while (isdigit(*(const unsigned char*)v1))  a = 10*a + (*v1++ - '0');

... or use (*v1 >= '0' && *v1 <= '9') if avoiding libraries.

NULL?

Since version compare is often done near the beginning of code and the result is very important, I'd like the comparison to tolerate more of the usual mistakes like NULL or effect some error message.

int compareVersion(const char * v1, const char * v2) {
  if (v1 == NULL) v1 = "";
  if (v2 == NULL) v2 = "";
  ...

Unlimited integer precision

No multiplication, no precision limit.

// Used unsigned access.  Avoid UB with `isdigit()` and correct for non-2's complement.
const unsigned char *u1 = v1;
const unsigned char *u2 = v2;

while (*u1 || *u2) {
  // Consume leading uninformative zero digits.
  while (*u1 == '0') u1++; 
  while (*u2 == '0') u2++; 

  int compare = 0;
  while (isdigit(*u1) && isdigit(*u2)) {
    if (*u1 != *u2 && compare == 0) { 
      compare = *u1 > *u2 ? 1 : -1;
    }
    u1++;
    u2++;
  }
  // Compare meaningful here only if same number of digits in u1, u2.

  // If one string has more significant digits, it is larger
  if (isdigit(*u1)) {
    return 1;
  }
  if (isdigit(*u2)) {
    return -1;
  }

  if (compare) {
    return compare;
  }
  if (*u1) u1++;
  if (*u2) u2++;
}
return 0;