Best search algorithm to find condition within a range

Dave Angel davea at davea.name
Thu Apr 9 15:19:07 CEST 2015


On 04/09/2015 08:56 AM, Alain Ketterlin wrote:
> Marko Rauhamaa <marko at pacujo.net> writes:
>
>> Alain Ketterlin <alain at dpt-info.u-strasbg.fr>:
>>
>>> No, it would not work for signed integers (i.e., with lo and hi of
>>> int64_t type), because overflow is undefined behavior for signed.
>>
>> All architectures I've ever had dealings with have used 2's-complement
>> integers. Overflow is well-defined, well-behaved and sign-independent
>> wrt addition, subtraction and multiplication (but not division).
>
> You are confused: 2's complement does not necessarily mean modular
> arithmetic. See, e.g.,
> http://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c
>

So the C standard can specify such things as undefined.  The 
architecture still will do something specific, right or wrong, and 
that's what Marko's claim was about.  The C compiler has separate types 
for unsigned and for signed, while the underlying architecture of every 
twos complement machine I have used did add, subtract, and multiply as 
though the numbers were unsigned (what you call modular arithmetic).

In my microcoding days, the ALU did only unsigned arithmetic, while the 
various status bits had to be interpreted to decide whether a particular 
result was overflow or had a carry.  It was in interpreting those status 
bits that you had to use the knowledge of whether a particular value was 
signed or unsigned.

Then the microcode had to present those values up to the machine 
language level.  And at that level, we had no carry bits, or overflow, 
or anything directly related.

-- 
DaveA



More information about the Python-list mailing list