Выясните (в C++), если двоичное число префиксом другого

Question

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

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

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

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

Пример: a = 100 (4), b = 1001 (9). Теперь установите *c на 1.

Answer 1

Вы можете использовать ваш любимый "fast" method to find the highest set bit. Назовем функцию 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() стоит дорого, то «простой подход» может быть самым быстрым подходом.

Answer 2

Я не слишком уверен, но что-то вроде следующей работы: (. Только от верхней части головы, так что может быть ошибки)

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