StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>OK, the issue is, if you want your ranges to span all of n-bits, any calculations based on start/end has the potential to overflow.</p> <p>So the trick is to do a linear transform to a place where your start/end calculations do not overflow, do your calcs, and then linear transform back.</p> <p><strong>NOTES</strong></p> <p>Below the <em>we can safely call end() now</em> line, you can call the ordering checks (your original code) and it will be safe since the ordering is preserved during a linear transform.</p> <p>Also, as I noted in the previous post, there is a special boundary case where even if you do this transform, you will overflow (where you span the entire line) - but you can code for that special boundary condition.</p> <p><strong>OUTPUT</strong></p> <p>5 11</p> <p><strong>CODE</strong></p> <pre><code>#include <iostream> using type = uint8_t; struct segment { type start, length; type end() const { return start + length; } }; static segment intersect( segment s, segment t ) { type shift = std::min( s.start, t.start ); // transform so we can safely call end() s.start -= shift; // doesn't affect length t.start -= shift; // doesn't affect length // we can safely call end() now ---------------------------------------------- type u_start = std::max( s.start, t.start ); type u_end = std::min( s.end(), t.end() ); type u_length = u_end - u_start; segment u{ u_start, u_length }; // transform back u.start += shift; return u; } int main() { segment s{ 3, 13 }, t{ 5, 11 }; segment u = intersect( s, t ); std::cerr << uint32_t( u.start ) << " " << uint32_t( u.length ) << std::endl; return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload