nixp.ru v3.0

22 января 2017,
воскресенье,
21:22:36 MSK

Аутсорсинг Linux с компанией «Флант»
pzh написал 2 февраля 2005 года в 12:06 (368 просмотров) Ведет себя неопределенно; открыл 2 темы в форуме, оставил 6 комментариев на сайте.

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

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

Идеи есть ?

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

sas

Примитивное решение в терминах 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 итераций.

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

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

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

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

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

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

Спасибо

pzh

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

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

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

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

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

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

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

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

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

vnp
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 == искомое начало.
pzh

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

ecobeingecobeing.ru
Экология и вегетарианство на благо всем живым существам Планеты.