spir <denis.s...@gmail.com> wrote:
Also, My actual need would rather be to move forward. The reason is this
allows important optimisations for common cases. In fact, the codes are
unicode code points: if the 5 first bits are 0 (tested with a mask), I
can jump forward to a sub-tree corresponding to a code < 0x10000 (BMP,
99.999% cases in practice). If the 14 first bits are 0 (ditto), I can
jump to the ASCII case, very common as well.
std.intrinsic's[1] bsr returns the highest non-zero bit. I'd think the
masking'd be as effective when you know which bits you care about.
But this seems more difficult; or rather I have not found a direct way
to extract a 0/1 bit.
I had first used an array of masks
[2^n,2^n-1,...,4,2,1]:
foreach (i ; 0..BIT_SIZE) {
mask = MASKS[i];
bit = !!(code & mask);
node = node.nodes[bit];
}
But as you see masking that way lets a value of 2^i, not 1, in the
'true' case, which needs to be converted, either with "cast(bool)bit" or
"!!bit". And this seems _very_ slow: runs about 3 times slower than
backward traversal.
This seems better implemented like this:
foreach ( i; 0..BIT_SIZE ) {
bit = ( code >> i ) & 1;
node = node.nodes[bit];
}
[1]: http://www.digitalmars.com/d/2.0/phobos/std_intrinsic.html
--
Simen
