in reply to Most Significant Set Bit
I think your example would be a lot more readable if you expressed the constants in binary or hex.
If each result is approximately equally likely, I think it would be more efficient to do a binary chop: a 64-bit input should take no more than 6 tests. For accuracy you should probably write some code to generate this:
my $m = $z > 0x00000000ffffffff ? $z > 0x0000ffffffffffff ? $z > 0x00ffffffffffffff ? $z > 0x0fffffffffffffff ? $z > 0x3fffffffffffffff ? $z > 0x7fffffffffffffff ? 0x8000000000000000 : 0x40000 +00000000000 : $z > 0x1fffffffffffffff ? 0x2000000000000000 : 0x10000 +00000000000 ... etc.
I don't know much about Bloom filters, but it's possible you could construct one to do it faster. Another possibility would be some XS (or Inline C) - some processors have a single instruction to return this, and C compilers often provide functions that use such instructions where available, and fall back to an alternative implementation otherwise. In this case I think you could do it using __builtin_clz() if using gcc.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Most Significant Set Bit
by coldr3ality (Acolyte) on Mar 25, 2024 at 13:14 UTC |