testing bits in sequence

[Simen kjaeraas]

spir <denis.spir at 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