Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Markus Armbruster]

Laszlo Ersek <address@hidden> writes:

> On 11/17/15 16:47, Markus Armbruster wrote:
>> Laszlo Ersek <address@hidden> writes:
>> 
>>> I accept this is a defensible, maybe even reasonable choice to make in
>>> the QEMU project. On the other hand, I personally cannot stop hating
>>> shifting negative values (any direction) -- indeed, the *original* code
>>> from <https://github.com/madler/zlib/pull/112> makes me barf too.
>>>
>>> Therefore,
>>>
>>> Grudgingly-reviewed-by: Laszlo Ersek <address@hidden>
>>>
>>> (I realize the flag for the pointer wraparound has been separated; this
>>> is strictly about shifts.)
>> 
>> What's so abhorrent about shifting negative values?  I know machines
>> with signed integer representations other than twos complement exist, as
>> do machines that can't do both logical and arithmetic shifts.  Mostly
>> inside computer museums, though.
>> 
>> C was standardized at a time when keeping the language sufficiently
>> loose to permit efficient implementation on these oddball machines made
>> a lot more sense than it does now.  Making it undefined behavior went
>> too far, though.  Implementation-defined or unspecified behavior would
>> have sufficed.
>> 
>> Learn to stop worrying and love the signed shifts :)
>
> I'm not worried. I hate it for the mental load it represents.
>
> For me, the fact that the negative sign is encoded (with *any* kind of
> representation) within the bit pattern subject to shifting, makes the
> negative sign *inherently* incompatible with shifting.
>
> In real life, *you don't shift a sign*. It just makes no sense. The sign
> is not a digit. You can append or cut off zeroes from the right, but the
> sign is not subject to that. The sign doesn't care.
>
> When you shift nonzero bits out of an unsigned variable to the left, its
> value changes in an intuitive, modular way. When you shift nonzero bits
> out of a signed, negative value variable, to the left, it might easily
> turn positive, in a completely screwed up way.
>
> Imagine that you have five cells on paper, in real life, decimal:
>
> +---+---+---+---+---+
> | - | 3 | 0 | 9 | 0 |
> +---+---+---+---+---+
>
> you multiply it by ten ("just append a zero"), and you end up with
>
> +---+---+---+---+---+
> | 3 | 0 | 9 | 0 | 0 |
> +---+---+---+---+---+
>
> It changed sign because you ran out of cells. Now does that make any sense?
>
> In any such case, in real life you have sign and magnitude, and the
> shifting doesn't effect the sign at all!
>
>     +---+---+---+---+
>   - | 3 | 0 | 9 | 0 |
>     +---+---+---+---+
>
> You might run out of magnitude, but that's a *completely* different,
> controlled and intuitive phenomenon.
>
> ... Paolo wrote
>
>     -(a << b) works but does not express that the intention is to
>     compute -a * 2^N, especially if "a" is a constant
>
> So apparently that's where I disagree.
>
> To me, the << operator doesn't communicate "multiply by 2^N"; it
> massages the bit pattern instead. For unsigned values, said massaging
> implies the multiplication *intuitively*. ("Append a zero", remember?)
> It remains intuitive even if the result gets truncated.

Yes, operator << is an operation on bits.

Yes, when you use it to multiply a two's complement integer by a power
of two *and* this changes the sign, you suffer integer overflow.

But integer overflow isn't specific to bad, bad <<.  Pretty much all
operations on two's complement numbers can overflow.  When a << n
overflows (0 <= n < width of the shift - 1), then inhowfar would a * 2^n
fare any better?

If it wouldn't, then why is a << n worth a warning (but only when a is a
compile-time negative constant), but a * b isn't?

Perhaps we should all program in languages where integer overflow is a
hard error, or can't happen (bignums to the rescue).  However, we
aren't.

Instead, we're using an "improvement" over mere shifting of bits!
Instead of "signed left shift gives you the bits you asked for, but
probably not the integer you asked for (assuming you asked for one)",
we're using "may give you whatever bits it likes, or crash, or even put
milk in your tea".  I'm sure it sounded like a good idea at the time.

> For signed / negative values, the shifting only *happens* to imply the
> multiplication, and only because of two's complement. If you shift the
> negative value out of range, you're busto (the sign might change). And
> even if you stay within range, two's complement is a non-intuitive, ugly
> hack. It has useful properties, yes, but it's hard to reason about safely.

Well, with sign-magnitude / sign in the MSB, a left shift *also* is a
multiplication by a power of two.  It just overflows more easily.

> The problem with two's complement is not that "there could be other
> representations". (No, there aren't other representations; not today.)
> The problem with two's complement is that it is a mathematical construct
> that is hard to reason about, despite its intentionally useful properties.
>
> Nevermind, anyway

Yes, integer overflow is a pain.  No, it's not two's complement's fault,
it's using-a-finite-number-of-bits-to-represent-the-infinite-set-of-
integers' fault.

Learn to stop worrying and love the two's complement ;)