Узнайте (в C ++), является ли двоичное число префиксом другого

Question

Узнайте (в C ++), является ли двоичное число префиксом другого

Мне нужна функция с таким заголовком:

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

Если a есть, читайте как строку двоичного числа, префикс b, затем установите * c равным остальной части b (то есть, «что b имеет больше, чем a») и верните true. В противном случае верните false. Предположим, что двоичные строки всегда начинаются с «1».

Конечно, это легко сделать, сравнивая побитно (сдвиг b до b == a). Но есть ли решение, которое является более эффективным, без перебора по битам?

Пример: a= 100 (4), b= 1001 (9). Сейчас установлено *c до 1.

4

binary bit-manipulation c++integer-arithmetic

Решение

Другие решения

Я не слишком уверен, но хотел бы что-то вроде следующей работы:

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

(Просто с макушки головы, чтобы не было ошибок.)

0

Источник

Accepted Answer

Вы можете использовать свой любимый «быстрый» метод, чтобы найти самый высокий установленный бит. Давайте назовем функцию 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;
}

сдвиг b поэтому его старший бит соответствует aи сравнить это с a, Если они равны, то a является префиксом b,

Производительность этого алгоритма зависит от производительности msb(), Если он постоянен, то этот алгоритм является постоянным. Если msb() это дорого, то «легкий подход» может быть самым быстрым подходом.

3