The mapping after we have the leading 1's count can be done in 3 instructions (in 32-bit math) on either x86 or ARM: t = 0x2020c6 >> x return (t << (t & 31)) >> 27
If you want to optimize it a little more, you can combine isLess(s, 0x20) and isChar('"') into isLess(s ^ (kOnes * 0x02), 0x21) (this works since '"' is 0x22).
Thanks, fixed.
The article leaves out optimizing is_leap_year. Here is an interesting version that is correct (in the Proleptic Gregorian calendar) for 0 <= year <= 102499 and takes only 3 instructions: ((year * 1073750999) &…
Here is a cute variant that doesn't need lzcnt nor tables, but only works up to 99,999: (((x + 393206) & (x + 524188)) ^ ((x + 916504) & (x + 514288))) >> 17 This is for integer log 10, but could be adapted for number…
The author wonders: > In theory at least, the compiler can see that rule only has 256 values and create a reduced version of ca1d_rule_apply for each value. Whether it actually does is not of much practical concern when…
Similarly, the eexpect table can be done in 3 instructions with with t = 0x3c783023f + i; return ((t >> (t & 63)) & 0xf0808088.
I wrote a solver for Atomix (https://github.com/falk-hueffner/atomixer), a similar game. Technically, the only difference is that in Atomix the solution location is not predefined, although probably based on level…
On a related note, almost any task around shuffling or shifting bits can be improved with xor. For example the straightforward way to remove bit i is mask = -1 << i; return (x & ~mask) | ((x >> 1) & mask); but with xor…
It seems you're shifting the goal posts now. The fact that consensus criticisms are not as harsh as you'd like doesn't mean that Israel is "totally off limits". Discussions and criticisms are happening; and the fact…
I don't see that. For example, it has been the official position of the German government for at least 20 years to strongly criticize the Israeli settlements. There's regular critical reports in the press, endless TV…
I wrote an ingredient parser that is basically just one giant regular expression: https://github.com/falk-hueffner/metric-cooking/blob/master/... The use case is a bit different (the task includes finding ingredients…
For the quite similar puzzle Atomix, it also seems like the branching factor would be much higher for backward search because upper bounds are weaker, but you can show that on average the branching factor is actually…
You don't necessarily need a wider type (which might be slower to work with), you can just calculate (n|1) * ((n+1)/2). Clang does something much more complicated, probably because for it is just a special case of some…
Slightly simpler: c = x ^ y; return popcount(((c >> 1) | 0x8080808080808080) - c) & 0x8080808080808080);
Actually, e is the inverse of the xor, so (e & c1) is guaranteed to be c1, and you still need popcount(c1 & ((e & c2) + c3)).
The name SWAR is sometimes used (https://en.wikipedia.org/wiki/SWAR). Indeed, even 8-bit fields can be added in parallel, using the fact that ^ is like a + that does not produce a carry: uint64_t signmask =…
There is some work on automatically generating data structure implementations from high-level specifications: https://cozy.uwplse.org/
Since the shift count is implicitly modulo 32, you don't even need the subtraction: bool isvowel(char c) { return (1u << (c&31)) & 0x208222; }
I wrote a browser extension that does this (although it will of course occasionally get something wrong): https://github.com/falk-hueffner/metric-cooking
Here's a version that at least for 64 bit might be faster: bool isPerfect(uint64_t x) { int ctz = __builtin_ctzll(x); return ((0x40051056 >> ctz) & 1) && ((x >> ctz) + 1) == (uint64_t(1) << (ctz + 1)); }
Red-black tree presentations are often more complicated than necessary, mostly because of (premature?) optimizations. A simple presentation can be found here:…
That's very unlikely to happen, since finding a counterexample or proving there isn't one is much easier than finding a program candidate, so it'll usually time out in that phase.
I tried using https://github.com/falk-hueffner/sematrope. Best I can get is x - ((x >> 4) ^ 0x33), should be slightly faster. EDIT: unfortunately that works only for upper case letters.
This will not yield a minimal set; in a cycle, it is only necessary to remove at least one word. The problem is thus to delete the minimum number of vertices to remove all cycles. This is the NP-hard Feedback Vertex Set…
The mapping after we have the leading 1's count can be done in 3 instructions (in 32-bit math) on either x86 or ARM: t = 0x2020c6 >> x return (t << (t & 31)) >> 27
If you want to optimize it a little more, you can combine isLess(s, 0x20) and isChar('"') into isLess(s ^ (kOnes * 0x02), 0x21) (this works since '"' is 0x22).
Thanks, fixed.
The article leaves out optimizing is_leap_year. Here is an interesting version that is correct (in the Proleptic Gregorian calendar) for 0 <= year <= 102499 and takes only 3 instructions: ((year * 1073750999) &…
Here is a cute variant that doesn't need lzcnt nor tables, but only works up to 99,999: (((x + 393206) & (x + 524188)) ^ ((x + 916504) & (x + 514288))) >> 17 This is for integer log 10, but could be adapted for number…
The author wonders: > In theory at least, the compiler can see that rule only has 256 values and create a reduced version of ca1d_rule_apply for each value. Whether it actually does is not of much practical concern when…
Similarly, the eexpect table can be done in 3 instructions with with t = 0x3c783023f + i; return ((t >> (t & 63)) & 0xf0808088.
I wrote a solver for Atomix (https://github.com/falk-hueffner/atomixer), a similar game. Technically, the only difference is that in Atomix the solution location is not predefined, although probably based on level…
On a related note, almost any task around shuffling or shifting bits can be improved with xor. For example the straightforward way to remove bit i is mask = -1 << i; return (x & ~mask) | ((x >> 1) & mask); but with xor…
It seems you're shifting the goal posts now. The fact that consensus criticisms are not as harsh as you'd like doesn't mean that Israel is "totally off limits". Discussions and criticisms are happening; and the fact…
I don't see that. For example, it has been the official position of the German government for at least 20 years to strongly criticize the Israeli settlements. There's regular critical reports in the press, endless TV…
I wrote an ingredient parser that is basically just one giant regular expression: https://github.com/falk-hueffner/metric-cooking/blob/master/... The use case is a bit different (the task includes finding ingredients…
For the quite similar puzzle Atomix, it also seems like the branching factor would be much higher for backward search because upper bounds are weaker, but you can show that on average the branching factor is actually…
You don't necessarily need a wider type (which might be slower to work with), you can just calculate (n|1) * ((n+1)/2). Clang does something much more complicated, probably because for it is just a special case of some…
Slightly simpler: c = x ^ y; return popcount(((c >> 1) | 0x8080808080808080) - c) & 0x8080808080808080);
Actually, e is the inverse of the xor, so (e & c1) is guaranteed to be c1, and you still need popcount(c1 & ((e & c2) + c3)).
The name SWAR is sometimes used (https://en.wikipedia.org/wiki/SWAR). Indeed, even 8-bit fields can be added in parallel, using the fact that ^ is like a + that does not produce a carry: uint64_t signmask =…
There is some work on automatically generating data structure implementations from high-level specifications: https://cozy.uwplse.org/
Since the shift count is implicitly modulo 32, you don't even need the subtraction: bool isvowel(char c) { return (1u << (c&31)) & 0x208222; }
I wrote a browser extension that does this (although it will of course occasionally get something wrong): https://github.com/falk-hueffner/metric-cooking
Here's a version that at least for 64 bit might be faster: bool isPerfect(uint64_t x) { int ctz = __builtin_ctzll(x); return ((0x40051056 >> ctz) & 1) && ((x >> ctz) + 1) == (uint64_t(1) << (ctz + 1)); }
Red-black tree presentations are often more complicated than necessary, mostly because of (premature?) optimizations. A simple presentation can be found here:…
That's very unlikely to happen, since finding a counterexample or proving there isn't one is much easier than finding a program candidate, so it'll usually time out in that phase.
I tried using https://github.com/falk-hueffner/sematrope. Best I can get is x - ((x >> 4) ^ 0x33), should be slightly faster. EDIT: unfortunately that works only for upper case letters.
This will not yield a minimal set; in a cycle, it is only necessary to remove at least one word. The problem is thus to delete the minimum number of vertices to remove all cycles. This is the NP-hard Feedback Vertex Set…