testing bits in sequence

[spir]

Hello,

I need to test in sequence the bits of an unsigned int (see below more precision), and move in a tree accordingly. Since there are 2 possible branches at every step, they are encoded in a [2] array, indexed by bit. I am looking for the fastest way to get that bit.

To run backwards (MSB <-- LSB), one can simply mask and shift right, like:
	uint MASK = 1;
	auto node = root;
	auto code = something;
	foreach (_ ; 0..BIT_SIZE) {
	    bit = code & MASK;
	    node = node.nodes[bit];
	    code >>= 1;
	}
But this looks like slow (to my surprise). I don't know what the limiting instruction is.

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.
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.

Note: I cannot use a plain array, because there is a small proportion of actual values in the whole range (sparse array of ~ 1 per-thousand 'busy' locations). I'm looking for a possible alternative to using AAs (costly because of division). Backward traversal currently runs sensibly slower that using an AA, but with optimisation for common cases there could be a huge gain in practice.
The data structure I'm trying to implement is concretely a kind "bit-trie" (dunno whether that exists already).

Any advice welcome. Thank you,

Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com