Нахождение сигнатуры 0

Примитивное решение в терминах SUS (Single Unix Specification):

int diff = 32 - 26;
int32_t   signature = 0x01fffffe;
int32_t   mask = 0x03ffffff;
int32_t   test_value = 0x4ffffff5;
int32_t    v;
int bit = -1;
for ( i = 0; i < diff; ++i ) {
   v = (test_value >> i) & mask;
   if ( !(v ^ signature) ) {
      bit = i;
      break;
    }
}
return (0 <= bit); /* наличие или просто - return bit;*/

Не тестировано. Худший случай — 6 итераций.

Не тестировано. Худший случай — 6 итераций.

приведённое решение даёт ответ только для поиска сигнатуры целиком, в то время, как первоначальное условие такое:

задача найти ее наличие, или ее начало

Genie
приведённое решение даёт ответ только для поиска сигнатуры целиком, в то время, как первоначальное условие такое:

Не совсем так по моему (мб я и ошибаюсь), решение находит полную сигнатуру и возвращает номер бита с которого она начинается или просто bool (см комментарий окло return). Если же задающий вопрос хотел найти и частичное вхождение, то вопрос не правильно сформулирован (опять же по-моему).

Кстати, в этом случае, с минимальными изменениями кода (1 строка) и увеличением количества итераций (2-ая строка) задача решается в лоб перебором. На таком размере данных и сигнатуры изобретать что-то более комплексное просто вредно для поизводительности.

Т.к. изменение тривиально, то оставим это в качестве упражнения.

Спасибо

Тривильное решение сейчас и работает, примерно в таком виде ))

А насчет изобретать, мысли все же бродят уж больно сигнатурка хитрая,

а количество операций все же хочется сократить.

Все равно большое спаибо за ответ.

pzh
Тривильное решение сейчас и работает, примерно в таком виде ))

А насчет изобретать, мысли все же бродят уж больно сигнатурка хитрая,

а количество операций все же хочется сократить.

Все равно большое спаибо за ответ.

Если сигнатура не меняется, то тогда сделайте loop unroll. Это наиболее быстрый путь если судить по исходному вопросу.

pzh
Имеется 26 битная уникальная сигнатура вида 0111….1110( в средине только единички),

задача найти ее наличие, или ее начало в произвольном четырех байтном отрезке за минимальное количество операций.

Идеи есть ?

Буду благодарен даже за намеки на идеи.

Полное вхождение — см. sas. Частичное, т.е. отрезок имеет вид

xx..xx011…11

(извините, если недопонял) примерно так:

X:           xx...xx011...11
X + 1:       xx...xx100...00
X ^ (X + 1): 00...00111...11
(X ^ (X + 1)) >> 1 == искомое начало.

идеи понял, премного благодарен )