Is there a quick bit operation to implement msb_equal: a function to check if two numbers have the same most significant bit?
For example, 0b000100 and 0b000111 both have 4 as their most significant bit value, so they are most msb_equal. In contrast 0b001111 has 8 as the MSB value, and 0b010000 has 16 as it's MSB value, so the pair are not msb_equal.
Similarly, are there fast ways to compute <, and <=?
Examples:
msb_equal(0, 0) => true
msb_equal(2, 3) => true
msb_equal(0, 1) => false
msb_equal(1, 2) => false
msb_equal(3, 4) => false
msb_equal(128, 255) => true
A comment asks why 0 and 1 are not msb_equal. My view on this is that if I write out two numbers in binary, they are msb_equal when the most significant 1 bit in each is the same bit.
Writing out 2 & 3:
2 == b0010
3 == b0011
In this case, the top most 1 is the same in each number
Writing out 1 & 0:
1 == b0001
0 == b0000
Here, the top most 1s are not the same.
It could be said that as 0 has no top most set bit, msb_equal(0,0) is ambiguous. I'm defining it as true: I feel this is helpful and consistent.
Yes, there are fast bit based operations to compute MSB equality and inequalities.
I'll provide implementations using c language syntax for bitwise and logical operators:
| – bitwise OR. || – logical OR.& – bitwise AND. && – logical AND.^ – bitwise XOR.==msb_equal(l, r) -> bool
{
return (l^r) <= (l&r)
}
<This is taken from the Wikipedia page on the Z Order Curve (which is awesome):
msb_less_than(l, r) -> bool
{
(l < r) && (l < l^r)
}
<=msb_less_than_equal(l, r) -> bool
{
(l < r) || (l^r <= l&r)
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments