Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[107.23.157.16] |
|
Сообщ.
#1
,
|
|
|
"Определение в указанном числе позиции последнего вхождения заданной битовой
последовательности." Помогите решить задачу. Программа на си. Не понимаю суть задания |
Сообщ.
#2
,
|
|
|
Пример: __int64 a = 0000000000001101101010110110b; - двоичное представление числа;
Задана "битовая последовательность"="11011"; Вот её вхождение (обозначил жирным) и является последним (думается мне), а то (кое в начале) - первым (красное). |
Сообщ.
#3
,
|
|
|
Цитата Славян @ Пример: __int64 a = 0000000000001101101010110110b; - двоичное представление числа; Задана "битовая последовательность"="11011"; Вот её вхождение (обозначил жирным) и является последним (думается мне), а то (кое в начале) - первым (красное). А каким образом это можно реализовать именно в СИ? |
Сообщ.
#4
,
|
|
|
Схему бы набросал такую:
1. Считываем=запрашиваем исходное число a. 2. Запрашиваем битовую последовательность в виде строки "1011" и т.п. 3. Ищем её в числе. 4. Если не нашли пишем, что нету и на выход. 5. Иначе (Если нашли) запишем место последнего нахождения. Набросайте хоть азы программы, дабы было понятно, что вы в принципе понимаете как она строится. |
Сообщ.
#5
,
|
|
|
Цитата Славян @ Схему бы набросал такую: 1. Считываем=запрашиваем исходное число a. 2. Запрашиваем битовую последовательность в виде строки "1011" и т.п. 3. Ищем её в числе. 4. Если не нашли пишем, что нету и на выход. 5. Иначе (Если нашли) запишем место последнего нахождения. Набросайте хоть азы программы, дабы было понятно, что вы в принципе понимаете как она строится. После того, как число перевели в двоичный вид, мы в нём ищем битовую последовательность как подстроку внутри строки? |
Сообщ.
#6
,
|
|
|
Не, я лишь нарисовал в битах схему. Делал бы всё в машинном представлении. Как-то так:
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; // запомним! |
Сообщ.
#7
,
|
|
|
Цитата ixca @ мы в нём ищем битовую последовательность как подстроку внутри строки? ixca, нет. Славян все правильно сделал через битовые операции. Но он сделал один "косячок" - первоначально заданное число портится сдвигами. Но его подход в плане производительности - лучший, т.к. минимум операций. А временное значение можно и сохранить. Не суть. А вот для наглядности я все же бы двигал не число, а маску по числу. Накидал тебе код с выводом отладочной информации на каждой итерации. Код специально сделал жЫрным - чисто для понимания. Онлайн исполнение тут. #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; } |
Сообщ.
#8
,
|
|
|
Что-то показалось, Джо, что ваш пример схавает и "11111", т.к. там &, кой поглотится маской. Не?
Добавлено Ну т.е. "11111"&"11011" = "11011"=mask. |
Сообщ.
#9
,
|
|
|
Цитата Славян @ Ну т.е. "11111"&"11011" = "11011"=mask. Да, ты был прав. Я поправил код. |
Сообщ.
#10
,
|
|
|
А ещё, Джо, вы ж не стали сохранять место нахождения как я, а сразу стали искать с головы; а потому если у вас сразу в голове найдётся нужное, то (например, при i=0) выдастся на экран -5. Что нелепо. Т.е. надо бы и выдавать, видимо, dig-5-i, а?..
|
Сообщ.
#11
,
|
|
|
Цитата Славян @ Т.е. надо бы и выдавать, видимо, dig-5-i, а? Все , мне двойка! Но всеж dig-i-1 вроде) |
Сообщ.
#12
,
|
|
|
Цитата Славян @ Не, я лишь нарисовал в битах схему. Делал бы всё в машинном представлении. Как-то так: 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. |
Сообщ.
#13
,
|
|
|
Цитата sergioK @ Полностью согласен! Но автор темы молчит о способе решения, посему сделали близко к тому как бы сами ваяли... задача для начинающих, и с битами это не очень понятно, проще через стринги (strstr) Добавлено Цитата JoeUser @ Сомнительно! Если же сразу нашлось (при i=0), то это на 5 бит от головы последнего бита числа произойти могло (dig-5), а не в (dig-1)! Или я чего не догоняю? Но всеж dig-i-1 вроде) |
Сообщ.
#14
,
|
|
|
Цитата Славян @ Или я чего не догоняю? Допустим длина маски 5 и маска сразу на старших битах подошла, каково смешение маски? 32-0-1 Допустим длина маски 1 и маска сразу на старшем бите подошла, каково смешение маски? 32-0-1 Допустим длина маски 1 и маска нашла только самый младший бит, каково смешение маски? 32-31-1 Вопрос как мы трактуем смещение "позиции последнего вхождения заданной битовой последовательности", я - предложил со старшего бита маски. И все же https://ideone.com/213hzg и https://ideone.com/yX9ZPg |
Сообщ.
#15
,
|
|
|
Цитата JoeUser Не будем вдаваться в холивары, посему обозначу только, что я бы наоборот - с младшего бита маски. Вопрос как мы трактуем смещение "позиции последнего вхождения заданной битовой последовательности", я - предложил со старшего бита маски. |
Сообщ.
#16
,
|
|
|
Славян, а что по этому:
|
Сообщ.
#17
,
|
|
|
Первый - мой доделаный пример. Всё норм. 5 нулей не нашли, вернули -1.
Добавлено Второй - ваш. Всё норм. Один ноль искали, нашли, вернули 0. Непонятно, в чём вопрос? Добавлено Ищите в моём по маске с одним нулём и тоже его найдёте. Тоже 0 в ответе. |
Сообщ.
#18
,
|
|
|
Славян,гуд!
|