ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Поиск последовательности в бинарном массиве
20 сообщений из 270, страница 11 из 11
  11  все
Поиск последовательности в бинарном массиве
    #39590506
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr SharahovВ константе $10010000 старшая единица ставит на место биты 0..3, младшая - биты 8..11, т.е. переставили.
Логически я это понимаю. Не могу самостоятельно в случае чего просчитать такую константу.

Вот есть число 00000X0Y
Необходимо получить YX~~~~~~
Соответственно Y нужно поместить на место 28 бита, X нужно поместить на 24 бит.

Соответственно для Y у меня выходит константа $0001 shl 28
А для X я подставляю $0100 shl (24 - 8). И это не правильно.

Расскажи, какой логикой руководствуешься, определяя константу. Туплю :)

Важно не на какое место поставить, а на сколько битов сдвинуть с прежнего места.
И если надо сдвинуть и на A и на B битов, то просто OR-им биты A и B и получаем константу.
...
Рейтинг: 0 / 0
25.01.2018, 00:00
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39590521
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Оки
А как просчитать, не затрут ли биты друг друга

Ну вот пример
Есть число 000А0БВГ
Каждая «буква» это 4 бита.
Допустим, я хочу взять от каждой буквы по 3 бита и занять верхние 12 бит. По изложенному принципу я сформирую константу. Как я могу однозначно определить, глядя на константу, что написанная мной операция работает для любых АБВГ?

И ещё момент. Насколько я понял, принцип предполагает расположение элементов в обратном порядке? Т.е. сохранить порядок элементов не удастся.
...
Рейтинг: 0 / 0
25.01.2018, 01:07
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39590630
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr Sharahov,

Оки
А как просчитать, не затрут ли биты друг друга

Ну вот пример
Есть число 000А0БВГ
Каждая «буква» это 4 бита.
Допустим, я хочу взять от каждой буквы по 3 бита и занять верхние 12 бит. По изложенному принципу я сформирую константу. Как я могу однозначно определить, глядя на константу, что написанная мной операция работает для любых АБВГ?

Тупо считаем, как описано. Берем худший случай - все 1. Проверяем наложение. Если оно есть, начинаем дополнительно изворачиваться при помощи масок, чтобы сделать по частям.


SOFT FOR YOUИ ещё момент. Насколько я понял, принцип предполагает расположение элементов в обратном порядке? Т.е. сохранить порядок элементов не удастся.
Если внимательно посмотришь на произведение, в нем всегда есть все возможные порядки. А порядок расположения и наличие битов в нужном месте определяется коэффициентом (т.е. заданными тобой сдвигами).
...
Рейтинг: 0 / 0
25.01.2018, 09:42
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39590632
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOU,

Вот это может настроить мозг на нужную волну: http://guildalfa.ru/alsha/node/14
...
Рейтинг: 0 / 0
25.01.2018, 09:48
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39591761
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Спасибо тебе за познавательную лекцию

Кстати я так и не разобрался, как расчитывать константу и сдвиг для целочисленного деления.
Причём там целая кипа особенностей:
* если Cardinal делится на Cardinal - там один код
* причём результат может не убраться в нижние 32 бита - тогда приходится делать умножение в Int64 - и смотреть старшие 32 бита
* если Integer делится на Cardinal - то там используется корректировка в зависимости от знака
* если Integer делится на отрицательное - я не знаю, можно ли обойтись без операции neg
* не всегда понятно, удастся ли обойтись imul или нужен mul

Сейчас я обхожусь полным перебором, нахожу подходящие константы. Например, если X в диапазоне 0..9999, то его деление на 100 у меня выглядит так: (X * $147B) shr 19

Но всё это не серьезно. Хочется иметь динамическое решение. Так что если напишешь толковую статью по сему поводу - цены тебе не будет :)
Кстати через FPU тоже вариант, но выполняется дольше, и вопросы по точности. Поэтому если есть возможность решать через целочисленные регистры - я стараюсь делать через них.
...
Рейтинг: 0 / 0
26.01.2018, 15:43
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39591812
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOU,

а это читал? http://guildalfa.ru/alsha/node/34
...
Рейтинг: 0 / 0
26.01.2018, 17:06
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39591829
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
SOFT FOR YOU,

о много нам открытий чудных готовит просвещенья дух

Александру спасибо. Твои алгоритмы всегда были лучшими :)
...
Рейтинг: 0 / 0
26.01.2018, 17:31
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39591954
kep-ko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kep-ko
Гость
SOFT FOR YOUполным перебором, нахожу подходящие константы ...а это уже полный перебор!
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
procedure TForm1.Button1Click(Sender: TObject);
var
  i : Integer;
  n : Cardinal;
  x : TExtended80Rec;
  m : UInt64;
  e : Integer;
begin
  n := StrToIntDef(Edit1.Text, 100);
  x := TExtended80Rec(1/n);
  e := x.Exponent + 1;
  m := x.Mantissa shr 48;
  for i := 0 to 3 do
    Memo1.Lines.Add(Inttostr(n)+'^-1 = $'+IntToHex(m shr i,4)+' *2^'+IntToStr(e+i+48-64));
end;

...
Рейтинг: 0 / 0
26.01.2018, 21:40
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39591961
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr SharahovSOFT FOR YOU,

а это читал? http://guildalfa.ru/alsha/node/34

Видимо оно
Почитаю на досуге :)
...
Рейтинг: 0 / 0
26.01.2018, 21:56
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39591982
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Статья конечно хорошая, но считаю её как минимум не полной. Вот к примеру Си-шный дизасм деления на 10:
Код: sql
1.
2.
3.
4.
5.
u32div10(unsigned int):
  mov edx, -858993459
  mul edx
  mov eax, edx
  shr eax, 3


Конечно, можно сказать, что здесь двойная длинна, которую на чистом Delphi без ущерба производительности реализовать не удастся.
Но во-первых, сейчас активно используют x64 и подобную манипуляцию совершат в два счёта. Во-вторых, при ограниченном диапазоне делимого - вполне можно реализовать деление через обычный imul и сдвиг, что я продемонстрировал на примере ранее.

Немаловажно то, что делимое может и скорее всего будет со знаком. В этом случае логика сильно меняется, и заслуживает детального рассмотрения. Опять таки при ограниченном делимом наверняка можно делать "короткое" умножение.
Код: sql
1.
2.
3.
4.
5.
6.
7.
  mov ecx, eax
  mov edx, 1717986919
  sar ecx, 31
  imul edx
  sar edx, 2
  mov eax, edx
  sub eax, ecx
...
Рейтинг: 0 / 0
26.01.2018, 22:46
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39591987
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr Sharahov,

Статья конечно хорошая, но считаю её как минимум не полной. Вот к примеру Си-шный дизасм деления на 10:
Код: sql
1.
2.
3.
4.
5.
u32div10(unsigned int):
  mov edx, -858993459
  mul edx
  mov eax, edx
  shr eax, 3


Конечно, можно сказать, что здесь двойная длинна, которую на чистом Delphi без ущерба производительности реализовать не удастся.
Но во-первых, сейчас активно используют x64 и подобную манипуляцию совершат в два счёта. Во-вторых, при ограниченном диапазоне делимого - вполне можно реализовать деление через обычный imul и сдвиг, что я продемонстрировал на примере ранее.

Немаловажно то, что делимое может и скорее всего будет со знаком. В этом случае логика сильно меняется, и заслуживает детального рассмотрения. Опять таки при ограниченном делимом наверняка можно делать "короткое" умножение.
Код: sql
1.
2.
3.
4.
5.
6.
7.
  mov ecx, eax
  mov edx, 1717986919
  sar ecx, 31
  imul edx
  sar edx, 2
  mov eax, edx
  sub eax, ecx


Во-первых, эти алгоритмы не вместо, а кроме.
Во-вторых, у меня нет ограничения диапазона - перечитай, если не уловил это.
В-третьих, и как ты тогда на x64 тогда будешь делить 64-битные? Там двойная длина 128 бит.
Знак - это как раз хорошо, ты снова не въехал. Это свободный лишний бит.
...
Рейтинг: 0 / 0
26.01.2018, 22:56
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39592000
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Я не хотел унизить или оскорбить. Я указал на то, что статью имеет смысл доработать, раскрыв вопрос в полной мере.
...
Рейтинг: 0 / 0
26.01.2018, 23:22
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39592001
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr Sharahov,

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

Ну, ты же не понял самой сути.

Предлагается ОРИГИНАЛЬНЫЙ, СОВЕРШЕННО НОВЫЙ, РАНЕЕ НИГДЕ НЕ ОПИСАННЫЙ АЛГОРИТМ.

Так понятнее? Нафига описание нового алгоритма превращать в обзор существующих?
...
Рейтинг: 0 / 0
26.01.2018, 23:28
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39592013
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Я понимаю, что ты хочешь явить миру изобретение. Но практический смысл его только в том случае, если человек не умеет сделать дизасм си-кода (я его кстати делал онлайн), реализовать обратное умножение через FPU, или подобрать константы перебором для своего диапазона чисел. Как минимум в двух случаях из трёх код выполнится быстрее.

Согласен, у тебя универсальный способ, и с ассемблером, тем боле ARM, мучиться не нужно. Но если цель не только попиариться, а ещё и раскрыть тему деления, то без описанных мной выше нюансов - статью считаю не полной.

Алгоритм в литературе раскрыт слабо или практически не раскрыт. У одного чувака псевдокод касался только Cardinal/Cardinal и вроде бы не работал, точно не помню. У второго только Integer/Integer, с сопутствующими ограничениями. Во всяком случае диапазон значений делимого не учитывался нигде, поэтому короткий вариант операции не был рассмотрен нигде.

Может быть ты сталкивался с другой литературой. Но тем и хороши твои статьи, что написаны для людей. С примерами и рассуждениями. По крайней мере на то претендуют.
...
Рейтинг: 0 / 0
26.01.2018, 23:52
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39592021
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUМожет быть ты сталкивался с другой литературой.

Довольно подробно известный алгоритм с двойной шириной описан и у Фога, и Уоррена (+ на сайте Уоррена есть дополнения). Для того чтобы понять идею и, используя шаблоны, написать деление самому без дизасма и перебора вполне достаточно. Останется только прогнать полную проверку написанного, ну, уж без этого никуда.

Описывать то, что всем и так давно известно, в сотый раз совершенно не за чем.
Все равно, чтоб получилось подробнее чем у Уоррена ни сил, ни умения, ни терпения не хватит.
...
Рейтинг: 0 / 0
27.01.2018, 00:11
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39592026
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUЯ понимаю, что ты хочешь явить миру изобретение. Но практический смысл его только в том случае, если человек не умеет сделать дизасм си-кода (я его кстати делал онлайн), реализовать обратное умножение через FPU, или подобрать константы перебором для своего диапазона чисел. Как минимум в двух случаях из трёх код выполнится быстрее.


Добавь сюда ИМХО, и я забуду этот бред.
...
Рейтинг: 0 / 0
27.01.2018, 00:20
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39592032
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

В смысле бред?
Твоё деление на 10 выполняется дольше на 1 сдвиг, вычитание и операцию чтения из памяти, чем в сишном дизасме
Моё (на диапазоне) деление на 100 делается вообще в две операции
...
Рейтинг: 0 / 0
27.01.2018, 00:35
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39592033
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr Sharahov,

В смысле бред?
Твоё деление на 10 выполняется дольше на 1 сдвиг, вычитание и операцию чтения из памяти, чем в сишном дизасме
Моё (на диапазоне) деление на 100 делается вообще в две операции

Бред в том, что ты говоришь
"Мне никогда не понадобится велосипед, я воспользуюсь автомобилем",
как будто у тебя всегда под рукой есть автомобиль.
...
Рейтинг: 0 / 0
27.01.2018, 00:43
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39592036
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Та никто не говорит, что твой алгоритм никогда не понадобится
Собственно и статьи твои обычно описывают то, что ранее кем-то было описано
Я смотрю с практической точки зрения. Ранее ты разжёвывал и более хорошо описанные подходы. Сейчас деление NativeInt/UInt наиболее оптимально подсматривается в си-выхлопе.
...
Рейтинг: 0 / 0
27.01.2018, 01:26
| Ответить | Цитировать | Написать  
Поиск последовательности в бинарном массиве
    #39592114
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOU,

Знаем, плавали: все придумано до нас, "наиболее оптимально" летать самолетами.
...
Рейтинг: 0 / 0
27.01.2018, 11:53
| Ответить | Цитировать | Написать  
20 сообщений из 270, страница 11 из 11
  11  все
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Поиск последовательности в бинарном массиве
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=58&msg=39591954&tid=2041298]:
 0ms
get settings:
 9ms
get forum list:
 21ms
check forum access:
 5ms
check topic access:
 5ms
track hit:
 95ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 74ms
get tp. blocked users:
 2ms
others: 225ms
total:  451ms
созд. / загр.: 451ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]