Our great sponsors
-
-
RISC-V does have a proposed extension Zbb that includes the cpop and cpopw instructions. It doesn't seem to have much recent activity, though.
https://github.com/riscv/riscv-bitmanip/blob/main/bitmanip/i...
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
advent-of-code-2022
🎄 My Advent of Code solutions in Rust. http://adventofcode.com/2022 (by timvisee)
I did something similar and counted from the end, to make much bigger jumps!
https://github.com/timvisee/advent-of-code-2022/blob/master/...
Maybe a bit less neat in the binary sense, but definitely very fast.
-
Note that for enumerable domains of less than 64, using a long plus bit ops has been a standard Set implementation for quite a while. For example, Java's EnumSet uses a long if the enum has less than 64 values:
https://github.com/frohoff/jdk8u-jdk/blob/master/src/share/c...
Where add() uses `|= bitmask`, remove() uses `&= ~bitmask`, and size() uses a count of the 1's in the long.
Adding XOR as an efficient toggle would be interesting, but unnecessary to keep this O(n), if I understand correctly. It's just toggling the value, so (albeit with an extra branch), you could implement it as:
if (!set.contains(val)) {
-
https://github.com/erikcorry/advent-of-code-2022/blob/main/d...
Then a friend solved it with regular expressions, but I found a sicker regex. After all, that's what regexes are about.
https://mobile.twitter.com/erikcorry/status/1600524753596456...
-
You are right. The algorithm you described is very similar to this XOR one. However, I did some benchmarks[0] and non-XOR version was 40% slower to XOR version when compiled with target-cpu=native. Unfortunately, without `target-cpu=native` the xor version was 40% slower and plain old arrays won!
[0]: https://github.com/mpawelski/adventofcode2022_day06/blob/mas...