disabling unary "-" for unsigned types

dsimcha dsimcha at yahoo.com
Tue Feb 16 07:53:40 PST 2010


== Quote from Daniel Keep (daniel.keep.lists at gmail.com)'s article
> Ellery Newcomer wrote:
> > On 02/15/2010 09:15 PM, Steven Schveighoffer wrote:
> >>
> >> For example, there is no possible way a person unfamiliar with computers
> >> (and most programmers who have not run into this) would believe that
> >>
> >> b = 5;
> >> a = -b;
> >>
> >
> > Tell any math major that fixnum arithmetic is really just arithmetic
> > modulo 2^32 and they would believe you, even if they had never heard of
> > computers
> >
> >> would result in a being some large positive number. It's just totally
> >> unexpected, and totally avoidable.
> >>
> >> -Steve
> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
> > Fast forward to 2006. I was shocked to learn that the binary search
> > program that Bentley proved correct and subsequently tested in Chapter
> > 5 of Programming Pearls contains a bug. Once I tell you what it is,
> > you will understand why it escaped detection for two decades. Lest you
> > think I'm picking on Bentley, let me tell you how I discovered the
> > bug: The version of binary search that I wrote for the JDK contained
> > the same bug. It was reported to Sun recently when it broke someone's
> > program, after lying in wait for nine years or so.
> >
> > ...
> >
> > The bug is in this line:
> >
> > 6:             int mid = (low + high) / 2;
> >
> > ...
> >
> > In Programming Pearls, Bentley says "While the first binary search was
> > published in 1946, the first binary search that works correctly for
> > all values of n did not appear until 1962." The truth is, very few
> > correct versions have ever been published, at least in mainstream
> > programming languages.
> It's fun to note that one of the fixes the author proposes in the
> article was actually shown to itself be wrong... nearly two years later.
> Clearly, knowing that computers use two's complement fixed-width integer
> arithmetic is insufficient to write correct code.  To believe otherwise
> is to believe that humans are infallible.
> In which case, I have literature on the Invisible Pink Unicorn [1] that
> might interest you...
> [1] http://en.wikipedia.org/wiki/Invisible_Pink_Unicorn

I **HATE** this example because it's a classic example of extreme nitpicking.  On
most modern computers, (void*).sizeof == size_t.sizeof.  Furthermore, usually half
your address space is reserved for kernel use.  Therefore, this bug would only
show up when you're searching an array of bytes **and** very close to exhausting
available address space (i.e. when you probably have bigger problems anyhow).  I
have intentionally written binary searches like this even though I'm aware of this
bug because it's more readable and efficient than doing it "right" and would only
fail in corner cases too extreme to be worth considering.



More information about the Digitalmars-d mailing list