Find out (in C++) if binary number is prefix of another

Question

I need a function with a header like this:

bool is_prefix(int a, int b, int* c) {
    // ...
}

If a is, read as a binary number string, a prefix of b, then set *c to be the rest of b (i.e. "what b has more than a") and return true. Otherwise, return false. Assume that binary strings always start with "1".

Of course - it is easy to do by comparing bit by bit (leftshift b until b==a). But is there a solution which is more efficient, without iterating over the bits?

Example: a=100 (4), b=1001 (9). Now set *c to 1.

Answer 1

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.

Answer 2

I'm not too sure, but would something like the following work:

bool
is_prefix( unsigned a, unsigned b, unsigned* c )
{
    unsigned mask = -1;
    while ( mask != 0 && a != (b & mask) ) {
        a <<= 1;
        mask <<= 1;
    }
    c = b & ~mask;
    return mask != 0;
}

(Just off the top of my head, so there could be errors.)