На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
  
> Задача на си
    "Определение в указанном числе позиции последнего вхождения заданной битовой
    последовательности."
    Помогите решить задачу. Программа на си. Не понимаю суть задания
      Пример: __int64 a = 0000000000001101101010110110b; - двоичное представление числа;
      Задана "битовая последовательность"="11011";
      Вот её вхождение (обозначил жирным) и является последним (думается мне), а то (кое в начале) - первым (красное).
        Цитата Славян @
        Пример: __int64 a = 0000000000001101101010110110b; - двоичное представление числа;
        Задана "битовая последовательность"="11011";
        Вот её вхождение (обозначил жирным) и является последним (думается мне), а то (кое в начале) - первым (красное).

        А каким образом это можно реализовать именно в СИ?
          Схему бы набросал такую:
          1. Считываем=запрашиваем исходное число a.
          2. Запрашиваем битовую последовательность в виде строки "1011" и т.п.
          3. Ищем её в числе.
          4. Если не нашли пишем, что нету и на выход.
          5. Иначе (Если нашли) запишем место последнего нахождения.

          Набросайте хоть азы программы, дабы было понятно, что вы в принципе понимаете как она строится. :blush:
            Цитата Славян @
            Схему бы набросал такую:
            1. Считываем=запрашиваем исходное число a.
            2. Запрашиваем битовую последовательность в виде строки "1011" и т.п.
            3. Ищем её в числе.
            4. Если не нашли пишем, что нету и на выход.
            5. Иначе (Если нашли) запишем место последнего нахождения.

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

            После того, как число перевели в двоичный вид, мы в нём ищем битовую последовательность как подстроку внутри строки?
              Не, я лишь нарисовал в битах схему. Делал бы всё в машинном представлении. Как-то так:
              ExpandedWrap disabled
                long long a=55990; // то, число из примера
                long long isk=27; // заданная последовательность
                long long mask=1|2|4|8|16; // маска, 5 бит
                int coxp = -1; // не найдено пока ничего
                for( int t=0; t<64; t++, a>>=1) // идём по числу 'a'
                  if( !((a^isk)&mask) ) // в точности попали !
                    coxp = t; // запомним!
                Цитата ixca @
                мы в нём ищем битовую последовательность как подстроку внутри строки?

                ixca, нет. Славян все правильно сделал через битовые операции. Но он сделал один "косячок" - первоначально заданное число портится сдвигами. Но его подход в плане производительности - лучший, т.к. минимум операций. А временное значение можно и сохранить. Не суть. А вот для наглядности я все же бы двигал не число, а маску по числу. Накидал тебе код с выводом отладочной информации на каждой итерации. Код специально сделал жЫрным - чисто для понимания.

                Онлайн исполнение тут.

                ExpandedWrap disabled
                  #include <stdio.h>
                  #include <limits.h>
                  #include <stdlib.h>
                   
                  #define false 0
                  #define true 1
                  typedef int bool;
                   
                  void debug(unsigned x) {
                    for(int i=sizeof(x)<<3; i; i--) putchar('0'+((x>>(i-1))&1));
                  }
                   
                  int main(void) {
                    unsigned value  = 0b0000000000001101101010110110;
                    unsigned mask = 0b11011;
                    unsigned imask = 0b11111;
                    unsigned dig = sizeof(unsigned)*CHAR_BIT;
                    unsigned i,tmp;
                    bool found = false;
                    for(i=0; i<dig-5+1; i++) {
                      printf("i = %d\n",i);
                      printf("value        : ");
                      debug(value);
                      printf("\n");
                      printf("value & imask: ");
                      debug(value & (imask << (dig-5-i)));
                      printf("\n");
                      printf("         mask: ");
                      debug(mask << (dig-5-i));
                      printf("\n ---\n");
                      if ((value & (imask << (dig-5-i))) == (mask << (dig-5-i))) {
                        found = true;
                        break;
                      }
                    }
                    if (found) {
                      printf("нашли: %d", dig-i-1);
                    } else {
                      printf("не нашли!!");
                    }
                    return 0;
                  }
                  Что-то показалось, Джо, что ваш пример схавает и "11111", т.к. там &, кой поглотится маской. Не?

                  Добавлено
                  Ну т.е. "11111"&"11011" = "11011"=mask.
                    Цитата Славян @
                    Ну т.е. "11111"&"11011" = "11011"=mask.

                    Да, ты был прав. Я поправил код.
                      А ещё, Джо, вы ж не стали сохранять место нахождения как я, а сразу стали искать с головы; а потому если у вас сразу в голове найдётся нужное, то (например, при i=0) выдастся на экран -5. Что нелепо. Т.е. надо бы и выдавать, видимо, dig-5-i, а?.. :rolleyes:
                        Цитата Славян @
                        Т.е. надо бы и выдавать, видимо, dig-5-i, а?

                        Все , мне двойка! :lol: Но всеж dig-i-1 вроде)
                          Цитата Славян @
                          Не, я лишь нарисовал в битах схему. Делал бы всё в машинном представлении. Как-то так:
                          ExpandedWrap disabled
                            long long a=55990; // то, число из примера
                            long long isk=27; // заданная последовательность
                            long long mask=1|2|4|8|16; // маска, 5 бит
                            int coxp = -1; // не найдено пока ничего
                            for( int t=0; t<64; t++, a>>=1) // идём по числу 'a'
                              if( !((a^isk)&mask) ) // в точности попали !
                                coxp = t; // запомним!

                          Мне почему то кажется что задача для начинающих, и с битами это не очень понятно, проще через стринги (strstr)
                          или если на плюсах через string.find.
                            Цитата sergioK @
                            задача для начинающих, и с битами это не очень понятно, проще через стринги (strstr)
                            Полностью согласен! Но автор темы молчит о способе решения, посему сделали близко к тому как бы сами ваяли... :blush:

                            Добавлено
                            Цитата JoeUser @
                            Но всеж dig-i-1 вроде)
                            Сомнительно! Если же сразу нашлось (при i=0), то это на 5 бит от головы последнего бита числа произойти могло (dig-5), а не в (dig-1)! Или я чего не догоняю?
                              Цитата Славян @
                              Или я чего не догоняю?

                              Допустим длина маски 5 и маска сразу на старших битах подошла, каково смешение маски? 32-0-1
                              Допустим длина маски 1 и маска сразу на старшем бите подошла, каково смешение маски? 32-0-1
                              Допустим длина маски 1 и маска нашла только самый младший бит, каково смешение маски? 32-31-1
                              Вопрос как мы трактуем смещение "позиции последнего вхождения заданной битовой последовательности", я - предложил со старшего бита маски.

                              И все же :-? https://ideone.com/213hzg и https://ideone.com/yX9ZPg
                                Цитата JoeUser
                                Вопрос как мы трактуем смещение "позиции последнего вхождения заданной битовой последовательности", я - предложил со старшего бита маски.
                                Не будем вдаваться в холивары, посему обозначу только, что я бы наоборот - с младшего бита маски.
                                  Славян, а что по этому:
                                  Цитата JoeUser @
                                    Первый - мой доделаный пример. Всё норм. 5 нулей не нашли, вернули -1.

                                    Добавлено
                                    Второй - ваш. Всё норм. Один ноль искали, нашли, вернули 0.

                                    Непонятно, в чём вопрос?

                                    Добавлено
                                    Ищите в моём по маске с одним нулём и тоже его найдёте. Тоже 0 в ответе.
                                      Славян,гуд!
                                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                      0 пользователей:


                                      Рейтинг@Mail.ru
                                      [ Script execution time: 0,0532 ]   [ 17 queries used ]   [ Generated: 28.03.24, 21:24 GMT ]