Since you asked for suggestions / optimizations:
You can map y/m/d tuples to 32-bit integers that monotonically increase with increasing dates. This reduces the problem to finding the min
of a sequence of int32_t
/ int_least32_t
/ long
, or whatever type you prefer1.
I'm not sure I understood why we want to leave the loop on month == 0
or day == 0
but not other invalid input conditions, especially not after already updating earliest_...
from those values. Your do{}while
has an earlier if()break
for the documented exit condition of all-zeros, so I just kept that and made it a while(1)
.
I like do{}while()
loops, but using one in this case would require rotating the loop and partially peeling the first iteration so the scanf and exit condition could be written at the bottom, with the update using values from the previous iteration if the do{}while
condition was true. So perhaps scanf("...", &earliest_year, &earliest_month, &earliest_day)
and error-check ahead of the first iteration and initialize vars so those don't get overwritten. Do that manually if writing in asm; in C let the compiler do it unless there's a condition that naturally fits at the bottom of the loop. Writing a while(1){ ... }
loop hints human readers to look for a break;
somewhere, and it's usually easiest to reason about loops that have one exit point. (So all else equal prefer that, but don't go out of your way to avoid a loop condition and a break
.)
Prefer initializing variables when you declare them, and don't declare them until you're ready to use them. Note that long date = ...
is only declared inside the loop; it doesn't exist outside. (Unfortunately for do{}while()
syntax, loop variables aren't in scope in the while(expression)
so you need to declare them outside the loop if you want to use them there.)
long earliest_date = LONG_MAX; // no dates seen yet. Has invalid m=d=0
while (1) {
scanf ...
check for I/O errors and optionally for out-of-range months and days...
long date = ((long)y << 16) + (m<<8) + d;
if (date == 0) // also makes checking for all-zero easy
break;
earliest_date = date < earliest_date ? date : earliest_date;
}
if (earliest_date == LONG_MAX) {
puts("no valid dates were entered");
return EXIT_SUCCESS;
}
int earliest_year = earliest_date >> 16; // hopefully an arithmetic right shift so we can handle negative years, but ISO C leaves that implementation defined.
int earliest_month = (earliest_date >> 8) & 0xFF; // second byte
int earliest_day = earliest_date & 0xFF; // low byte
I used the term "byte" in a comment only to be concise; I actually meant "octet" but I figured "byte" would be more helpful to most readers. ISO C doesn't guarantee that a byte is 8 bits, but this code just uses shifts and integer constants without making any assumptions about CHAR_BIT
or sizeof(long)
, e.g. we used & 0xFF
instead of (unsigned char)earliest_date
to extract the low 8 bits, to match the shift by 8 we did when packing.
Note that this is just integer math, no byte addressing of memory. So endianness isn't a factor, unlike J_H's answer suggesting memcmp
.
It might be a good idea to make pack
and unpack
helper functions so the code using it can look like Date date = date_pack(y, m, d);
and date_unpack(earliest_date, &earliest_year, &earliest_month, &earliest_day)
. That separates the pack/unpack logic from the loop using it to find the earliest, so you tweak the packing format all in one place, not mixed with other logic. Making those functions static inline
will let them most easily optimize away.
#include <limits.h> // for LONG_MAX
// an integer type that allows < and == compares, and is all 0 for d=m=y=0
typedef long Date;
#define DATE_MIN LONG_MIN
#define DATE_MAX LONG_MAX
// and use Date earliest_date = DATE_MAX;
static inline
Date date_pack(int y, int m, int d){
return ((Date)y<<16) + (m<<8) + d;
}
static inline int date_year(Date date){
// hopefully an arithmetic right shift so we can handle negative years, but ISO C leaves that implementation defined.
return date >> 16;
}
static inline int date_month(Date date){
return (date >> 8) & 0xFF; // second byte
}
static inline int date_day(Date date){
return date & 0xFF; // low byte
}
static inline
void date_unpack(Date date, int *y, int *m, int *d){
*y = date_year(date);
*m = date_month(date);
*d = date_day(date);
}
These compile efficiently for x86-64 and AArch64 as expected (Godbolt); when inlining into a caller that passes the address of local vars, the actual stores would be optimized away. It's also significantly more source lines than just doing it directly inside the loop, so there's a tradeoff in terms of over-engineering if you're not actually going to reuse this pack/unpack code in other functions (yet).
We could use smaller shifts if we wanted; month = 1..12
will fit in 4 bits, and d = 1..31
will fit in 5 bits. But even with 8 bits for each, that's still 16 bits of space for a year in a 32-bit long
. (And much more in a 64-bit long
.)
If you want to support negative dates (e.g. 10 BCE as -10
, the current year 2023 CE as +2023
), this pack/unpack method would depend on long >>
being an arithmetic right shift (shifting in copies of the sign bit for 2's complement systems), rather than logical (shifting in zeros). ISO C unfortunately leaves that choice up to the implementation, and a few embedded compilers for CPUs without arithmetic right shift choose logical. (Fun fact: it's possible to portably emulate arithmetic right shift using bitwise operations, and mainstream compilers are even able to optimize that back into a single arithmetic right-shift instruction.)
This mapping is still monotonic for negative years, and across the year-zero boundary. For example March 1st in year -10 is later than Jan 1st in year -10, so still adding (rather than subtracting) the m
and d
components gives the right ordering.
If users enter nonsense numbers for y/m/d, for example day=1000000, that's big enough to "carry" into the month and year part of the integer. Your version allows full 32-bit integers for all 3 components while still maintaining ordering. But they're supposed to be dates so this is basically just a behaviour quirk on bad input, or something that would never come up if range-checking the input.
Footnote 1: what integer type to use for 32-bit integers
int
is often 32 bits, but ISO C only guarantees that it's at least 16-bit. Some real-world C implementations (for microcontrollers these days) have 16-bit int
, so that's not the most portable choice.
For a single local variable, long
is fine; ISO C requires it to be at least 32 bits wide. 64-bit systems often use 64-bit long
, but on such systems, compare and shift aren't slower than with 32-bit types. (Except a bit of extra machine-code size on x86-64 for REX prefixes). If you were making more use of this, e.g. in structs and/or arrays, you'd want to use something like int_least32_t
, or int32_t
if you don't mind requiring that optional type to exist. (Pretty much everything these days uses 2's complement integers with power-of-2 bit widths so do support int32_t
.) Unfortunately int_fast32_t
is not usable for use-cases like this because of bad choices by some major platforms.
If you were storing arrays of these, you'd want to put more effort into making sure you didn't get an unnecessarily-wide type that would over-align your structs and cost memory bandwidth / cache footprint.
You don't actually need 32 bits; 24 would be sufficient, especially if you pack m
and d
more tightly in 4 and 5 bits. Some DSPs have 24-bit int
. Especially using unsigned
would get you an extra bit for non-negative years which could be useful.
Perhaps you could check #ifdef INT_MAX > (1LL << 23)
and use int
in that case. In C++, you'd check std::numeric_limits<int>::digits
. The int_leastN_t
types only come in power-of-2 sizes so don't fit the bill here. In C23, there's _BitInt(24)
, but that would be less efficient than a 32-bit type on a normal 32 or 64-bit CPU.
16-bit Date
is only enough for 7 bits of year, which isn't enough for 4-decimal-digit dates. 2-digit dates have been obsolete since before the turn of the century, and writing new code that can't handle 4-digit dates would be a serious mistake. It's surprising that an assignment would ask you to write code using them. The current year, 2023, needs 11 bits (unsigned), and 2048 isn't too far away. That uses 12 bits (unsigned).
It's also bad that it asks for date input in a backwards order, not y/m/d (https://xkcd.com/1179/). Perhaps that's to stop you from requiring a strict text format with a leading zero for one-digit numbers, because that would produce a string you could compare with strcmp
or memcmp
; lexical sorting of date strings in ISO 8601 format (2023-11-23
) orders them correctly. That's why that date order is superior.
13/33/13
? And what about negative years - yes, they also exist! I assume you are still young, thus you never heard about the Year-2k-Bug \$\endgroup\$java.util.time
or Joda time, I don't know what the best practice is for C). Cheers :) \$\endgroup\$earliest_year
with a high value, likeINT_MAX
, you can completely get rid of theearliest_month == 0 && earliest_day == 0 && earliest_year == 0
check/block. \$\endgroup\$