A C Programming Contest
This is the summary of a programming "contest" from the newsgroup
The original problem statement was from Seika Abe (firstname.lastname@example.org). I'll
paraphrase only here:
The measure for the length of the function is the number of characters.
The first algorithm to appear uses an unsigned counter that is left shifted
by 1 in each iteration of the loop; it terminates when this counter wraps
around to zero:
which can be shortened a little bit by using "
Then, a somewhat modified algorithm turned up: instead of shifting
This also could be shortened by one character:
But the big surprise was the appearance of the following gem...
This was finally considered the "winner".
In the introduction I said that we tried to come up with ANSI conforming
solutions. Did we succeed? No. Let me explain why.
What does "ANSI Conforming" mean?
The ANSI/ISO standard for C (ISO/IEC 9899:1990(E)) does not specify the language in all details. There are a lot of places where the standard leaves it to the compiler writer to choose some behavior, and there are even more places where the standard explicitly sais, that the "behavior is undefined".
The standard makes the following distinctions:
A conforming program is a program that does not invoke any of above problem categories, i.e. that does not contain constructs labeled as either undefined, unspecified or implementation-defined behavior. The intent of this is that an ANSI conforming program should be maximally portable.
Are above solutions ANSI conforming?
Let's start with an obvious improvement: use
What's wrong with this? On the last iteration,
This looks much better: neither
Well then, is the "winner" ANSI conforming?
The problem with this "solution" is another: it works only for
implementations using 2's complement to represent
In these number representations, there are two ways to express 0. Both these bit patterns mean 0, and the compiler is required to treat them both as zero. These patterns have some 1-bits, though. As a result, the function cannot correctly invert these bit patterns: it just returns zero.
What about the other solutions?
None of the other solutions are ANSI conforming. The reason is that the standard explicitly states (18.104.22.168):
When a signed integer is converted to an unsigned integer with equal or greater size, if the value of the signed integer is nonnegative, its value is unchanged.
When ... an unsigned integer is converted to its corresponding signed integer, if the value cannot be represented the result is implementation-defined.
This means: if we have an assignment
It also means: if the result
Furthermore, all solutions involving
What would an ANSI conforming solution look like?
With all the above in mind, we can list the following criteria:
All this leads to something that looks remarkably similar to the very first entry:
Unfortunately, this is quite a bit longer than the other entries and not half as
elegant! (Note that
Most of the problems with ANSI conformance stem from the careless
specification of the problem. In real life, bit operations should be
is far more natural for a function that's supposed to do bit manipulations. The surprising recursive solution then becomes
(Note that "
Copyright © 2000 by
Thomas Wolf. All rights
TW, Aug 02, 2000