Find out (in C ++) if a binary number is a 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 numeric string, the prefix is ​​b, then set * c as the rest of b (that is, "that b has more than") and return true. Otherwise, return false. Suppose binary strings always begin with "1".

Of course - this is easy to do by comparing in half (left shift b to b == a). But is there a solution that is more efficient without repeating 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 bit of dialing . Let me call the msb() function.

 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 is aligned with a and compared with a . If they are equal, then a is the "prefix" b .

This algorithm performance depends on the performance of msb() . If it is constant, then this algorithm is constant. If msb() expensive, then the “simple approach” may be the fastest.

Answer 2

I'm not too sure, but there will be 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; } 

(Above my head, so there may be errors.)