Comparing the Most Significant Bit of two numbers: ==, <, <=

Question

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.

Answer 1

Yes, there are fast bit based operations to compute MSB equality and inequalities.

Note on syntax

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)
}

Answer 2

If you know which number is the smallest/biggest one, there is a very fast way to check whether the MSBs are equal. The following code is written in C:

bool msb_equal(unsigned small, unsigned big) {
    assert(small <= big);
    return (small ^ big) <= small;
}

This can be useful in cases like when you add numbers to a variable and you want to know when you reached a new power of 2.

Explanation

The trick here is that if the two numbers have the same most significant bit, it will disappear since 1 xor 1 is 0; that makes the xor result smaller than both numbers. If they have different most significant bits, the biggest number's MSB will remain because the smallest number has a 0 in that place and therefore the xor result will be bigger than the smallest number.

When both input numbers are 0, the xor result will be 0 and the function will return true. If you want 0 and 0 to count as having different MSBs then you can replace <= with <.