You can use your favorite "fast" method to find the highest set bit. Let's call the function msb()
.
bool is_prefix (int a, int b, int *c) {
if (a == 0 || b == 0 || c == 0) return false;
int d = msb(b) - msb(a);
if (d < 0) return false;
if ((b >> d) == a) {
*c = b ^ (a << d);
return true;
}
return false;
}
Shift b
so its high order bit aligns with a
, and compare that with a
. If they are equal, then a
is a "prefix" of b
.
This algorithm's performance depends on the performance of msb()
. If it is constant, then this algorithm is constant. If msb()
is expensive, then the "easy approach" may be the fastest approach.