Best search algorithm to find condition within a range

[Alain Ketterlin]

Marko Rauhamaa <marko at pacujo.net> writes:

> Dave Angel <davea at davea.name>:
>
>> 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).
>
> Alain did have a point. *If* I had used int64_t in my algorithm, it
> might not have worked because the compiler could legally produce code
> that crashes or does weird things in case of a signed integer
> overflow.

Yes, exactly. Since the language semantics don't guarantee anything, the
compiler can do whatever it likes. Changing your example to use int64_t
instead of uint64_t would let the compiler remove the "overflow" test.
Because, in:

    z = x+y; // all signed ints
    if ( z < x )
        ...

either there was no overflow (and the condition is false), or there was,
and the result is undefined, i.e., "z<x" can be considered false also.

> In this day and age, heavily optimized compilers (including gcc)
> actively exploit undefined behavior in code generation.

They do. Moreover, it looks like it is very difficult to warn the user
(I'm not even sure compilers catch cases like the one above).

> However, I didn't use int64_t, I used uint64_t.

Yes, your code was ok.

-- Alain.