A C Programming Contest 
This is the summary of a programming "contest" from the newsgroup
comp.programming.contests . The original
specification for this came from Seika Abe
(abe@hallab.co.jp). I found this contest quite interesting for a
couple of reasons:


The Problem 

The original problem statement was from Seika Abe (abe@hallab.co.jp). I'll
paraphrase only here:
The measure for the length of the function is the number of characters. 

Entries 

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 "  " instead of
"+ ", thereby doing away with a pair of parentheses:
Then, a somewhat modified algorithm turned up: instead of shifting n and alwas doing a n&1 , this algorithm uses j
directly to get single bits. Two variants were proposed:
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". 

ANSI Conformance 

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 implementationdefined 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 "
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 1bits, 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 (6.2.1.2): 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 implementationdefined.
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 

Conclusion 

Most of the problems with ANSI conformance stem from the careless
specification of the problem. In real life, bit operations should be
done on unsigned exactly to avoid all these problems. An
interface like
is far more natural for a function that's supposed to do bit manipulations. The surprising recursive solution then becomes (Note that " *2 " on unsigned does not overflow,
the standard defines moduloarithmetic for unsigned , i.e. the
argument silently wraps around to zero.)

Copyright © 2000 by
Thomas Wolf. All rights
reserved.
TW, Aug 02, 2000 