StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Since I made the comment about using ints (or indeed int64), I may as well write it up and you can evaluate whether it's worth it. It would be something like this. Forgive any errors, as I'm just bunging this into a browser while my kids are watching ridiculously trashy saturday-morning cartoons.</p> <pre><code>// I'm gonna assume 32-bit ints here. Makes the other maths clearer. // Sorry about all the '4' and '32' constants =P const size_t arrLen = 100000 / 4 + 1; int arr[arrLen]; //This gets filled with your data... memset((void*)arr, 0, arrLen*4); cin >> x >> y; int leftMask = 0xffffffff >> (x % 32); // "(x & 0x1f)" faster? int rightMask = ~(0x7fffffff >> (y % 32)); // "(y & 0x1f)" faster? x /= 32; // "x >>= 5" faster? y /= 32; // "y >>= 5" faster? if( x == y ) { // Intersect the masks leftMask &= rightMask; arr[x] = (arr[x] & ~leftMask) | (~arr[x] & leftMask); } else if( x < y ) { // Flip the left and right ends arr[x] = (arr[x] & ~leftMask) | (~arr[x] & leftMask); arr[y] = (arr[y] & ~rightMask) | (~arr[y] & rightMask); // Flip everything in between for( int i = x+1; i < y; i++ ) { arr[i] ^= 0xffffffff; // Or arr[i] = ~arr[i] -- whichever is faster } } </code></pre> <p>Alternative for the above loop, if it makes any difference...</p> <pre><code>// Flip everything in between for( int *a = arr+x+1, *b = arr+y; a < b; a++ ) { *a = ~*a; } </code></pre> <p>Exercise is to try with 64-bit integers. Personally, I reckon this approach would be faster than anything else except in the cases where you are only flipping a few bits.</p> <p>I might have an off-by-one-bit error in the right-hand mask. If anyone spots it please comment. Brain empty. =)</p>

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