| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > C/C++: Общие вопросы > Задача на си |
| Автор: ixca 20.04.20, 12:36 |
| "Определение в указанном числе позиции последнего вхождения заданной битовой последовательности." Помогите решить задачу. Программа на си. Не понимаю суть задания |
| Автор: Славян 20.04.20, 13:03 |
| Пример: __int64 a = 0000000000001101101010110110b; - двоичное представление числа; Задана "битовая последовательность"="11011"; Вот её вхождение (обозначил жирным) и является последним (думается мне), а то (кое в начале) - первым (красное). |
| Автор: ixca 20.04.20, 13:10 |
| Цитата Славян @ Пример: __int64 a = 0000000000001101101010110110b; - двоичное представление числа; Задана "битовая последовательность"="11011"; Вот её вхождение (обозначил жирным) и является последним (думается мне), а то (кое в начале) - первым (красное). А каким образом это можно реализовать именно в СИ? |
| Автор: Славян 20.04.20, 13:21 |
| Схему бы набросал такую: 1. Считываем=запрашиваем исходное число a. 2. Запрашиваем битовую последовательность в виде строки "1011" и т.п. 3. Ищем её в числе. 4. Если не нашли пишем, что нету и на выход. 5. Иначе (Если нашли) запишем место последнего нахождения. Набросайте хоть азы программы, дабы было понятно, что вы в принципе понимаете как она строится.  |
| Автор: ixca 20.04.20, 13:37 |
| Цитата Славян @ Схему бы набросал такую: 1. Считываем=запрашиваем исходное число a. 2. Запрашиваем битовую последовательность в виде строки "1011" и т.п. 3. Ищем её в числе. 4. Если не нашли пишем, что нету и на выход. 5. Иначе (Если нашли) запишем место последнего нахождения. Набросайте хоть азы программы, дабы было понятно, что вы в принципе понимаете как она строится. После того, как число перевели в двоичный вид, мы в нём ищем битовую последовательность как подстроку внутри строки? |
| Автор: Славян 20.04.20, 13:48 |
| Не, я лишь нарисовал в битах схему. Делал бы всё в машинном представлении. Как-то так: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> 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; // запомним! |
| Автор: JoeUser 20.04.20, 14:25 |
| ixca, нет. Славян все правильно сделал через битовые операции. Но он сделал один "косячок" - первоначально заданное число портится сдвигами. Но его подход в плане производительности - лучший, т.к. минимум операций. А временное значение можно и сохранить. Не суть. А вот для наглядности я все же бы двигал не число, а маску по числу. Накидал тебе код с выводом отладочной информации на каждой итерации. Код специально сделал жЫрным - чисто для понимания. Онлайн исполнение тут. <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> #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; } |
| Автор: Славян 20.04.20, 14:55 |
| Что-то показалось, Джо, что ваш пример схавает и "11111", т.к. там &, кой поглотится маской. Не? Добавлено Ну т.е. "11111"&"11011" = "11011"=mask. |
| Автор: JoeUser 20.04.20, 18:11 |
| Да, ты был прав. Я поправил код. |
| Автор: Славян 20.04.20, 18:56 |
А ещё, Джо, вы ж не стали сохранять место нахождения как я, а сразу стали искать с головы; а потому если у вас сразу в голове найдётся нужное, то (например, при i=0) выдастся на экран -5. Что нелепо. Т.е. надо бы и выдавать, видимо, dig-5-i, а?..  |
| Автор: JoeUser 20.04.20, 20:00 |
| Все , мне двойка!  Но всеж dig-i-1 вроде) |
| Автор: sergioK 21.04.20, 00:46 |
| Цитата Славян @ Не, я лишь нарисовал в битах схему. Делал бы всё в машинном представлении. Как-то так: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> 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. |
| Автор: Славян 21.04.20, 00:57 |
| Цитата sergioK @ Полностью согласен! Но автор темы молчит о способе решения, посему сделали близко к тому как бы сами ваяли... задача для начинающих, и с битами это не очень понятно, проще через стринги (strstr) Добавлено Сомнительно! Если же сразу нашлось (при i=0), то это на 5 бит от головы последнего бита числа произойти могло (dig-5), а не в (dig-1)! Или я чего не догоняю? |
| Автор: JoeUser 21.04.20, 05:07 |
| Допустим длина маски 5 и маска сразу на старших битах подошла, каково смешение маски? 32-0-1 Допустим длина маски 1 и маска сразу на старшем бите подошла, каково смешение маски? 32-0-1 Допустим длина маски 1 и маска нашла только самый младший бит, каково смешение маски? 32-31-1 Вопрос как мы трактуем смещение "позиции последнего вхождения заданной битовой последовательности", я - предложил со старшего бита маски. И все же  https://ideone.com/213hzg и https://ideone.com/yX9ZPg |
| Автор: Славян 21.04.20, 11:52 |
| Цитата JoeUser Не будем вдаваться в холивары, посему обозначу только, что я бы наоборот - с младшего бита маски. Вопрос как мы трактуем смещение "позиции последнего вхождения заданной битовой последовательности", я - предложил со старшего бита маски. |
| Автор: JoeUser 21.04.20, 13:24 |
| Славян, а что по этому: |
| Автор: Славян 21.04.20, 13:50 |
| Первый - мой доделаный пример. Всё норм. 5 нулей не нашли, вернули -1. Добавлено Второй - ваш. Всё норм. Один ноль искали, нашли, вернули 0. Непонятно, в чём вопрос? Добавлено Ищите в моём по маске с одним нулём и тоже его найдёте. Тоже 0 в ответе. |
| Автор: JoeUser 21.04.20, 14:16 |
| Славян,гуд! |