Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 16:05

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 15 ] 
Автор Сообщение
 Заголовок сообщения: переставить 2 бита в слове
СообщениеДобавлено: Пн мар 22, 2010 21:54 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
А вот какая задачка мне на ум пришла:

Поменять местами два бита в слове (32 битном). Переставляемые биты задаются маской. Маска это слово, в котором единице равны два бита (которые нужно поменять).
swab ( w m -- w')

например результатом
11111111111111111111111111111110 10000000000000000000000000000001
будет
01111111111111111111111111111111

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

PS. Для неправильно заданной маски (с не двумя единичными битами) результат не определен


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 22, 2010 23:11 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Хотели "красивое?" нате! :)
Код:

\ решение для fork-a

: NOT -1 XOR ; \ проще написать так, чем искать где же библиотека с этим NOT

( word, mask --> word_bit_swaped )
: BSWAP
   DDUP AND 0 = >R  \ если оба бита - нули
   DDUP NOT OR NOT 0 = \ или оба бита - единицы
   R> OR IF DROP \ то переставлять нечего,
        ELSE XOR THEN ; \ иначе перестановка равна инвертированию двух бит

HEX
: test
F0 11 BSWAP . ." - должно получиться E1" CR
AA 03 BSWAP . ." - должно получиться A9" CR
AA 22 BSWAP . ." - должно получиться АА" CR
AA 05 BSWAP . ." - должно получиться АА" CR ;
test


оптимизировать не пытался

результат:

Код:
E1 - должно получиться E1
A9 - должно получиться A9
AA - должно получиться АА
AA - должно получиться АА


п.с. А задачку надо бы усложнить...

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 22, 2010 23:27 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Да. решение 8)

см. дальше

исправлено - нет, всё, кажется, правильно, это я так читал


Последний раз редактировалось вопрос Пн мар 22, 2010 23:28, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 22, 2010 23:28 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
да, красиво. у меня несколько иначе, но суть та же:
Код:
: swab ( w m -- w')
  2dup and dup 0= if drop exit then
  dup  1- and if drop exit then
  xor ;


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 22, 2010 23:29 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
А как усложнить?


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 22, 2010 23:30 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
forther писал(а):
А как усложнить?

поменять 3 или более битов по циклу - по кругу, задачка проста за счёт магического свойства числа 2 - количество состояний "истина - ложь"


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 22, 2010 23:34 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
а не могли бы вы развернуть условие? типа что конкретно на входе и что конкретно на выходе. т.е. в общих чертах понятно, о чем вы, но как постановка задачи это не достаточно внятно.


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн мар 22, 2010 23:55 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
forther писал(а):
а не могли бы вы развернуть условие? типа что конкретно на входе и что конкретно на выходе. т.е. в общих чертах понятно, о чем вы, но как постановка задачи это не достаточно внятно.


: swabn ( w m -- w' )
\ где
\ w - исходное число
\ m - маска
\ переставить биты так, чтобы (а) последний oказался на месте первого
\ (в) каждый из остальных битов - на месте следующего в маске (циклический сдвиг, но не всего регистра, а
\ отмеченных в маске битов)

например, обозначив биты в байте буквами
a b c d e f g h
и имея маску
0 1 1 0 0 0 0 1
мы должны получить
a h b d e f g c
цвета показывают сдвиг


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 23, 2010 00:06 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
WingLion, вы такое усложнение имели ввиду?


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 23, 2010 05:33 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
forther писал(а):
WingLion, вы такое усложнение имели ввиду?


Да, только условие надо точнее задавать. Не просто циклический сдвиг, но и побитно указать, какой бит в какой сдвигается. В одной маске это не получится (т.к. биты в маске формально неразличимы/не по естественному порядку), поэтому на входе надо несколько масок задавать.

NBitsROL ( data, mask1, mask2, maskN -- result ) \ переместить бит по маске1 в бит по маске2, бит по маске2 в бит по маске3 и так далее, а бит по маскеN в бит по маске1.

Начать с N=3 и до N=32 (больше для 32-битного слова смысла нет)
Для N=2 - тривиально - : 2BitsROL OR BWAP ;

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 23, 2010 06:07 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
а чем плох каскадный вызов swab?

\ data
mask1 swab
mask2 swab
mask3 swab
...

Или по вашему биты разможаться тоже могут?


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 23, 2010 06:26 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Ну, это вопрос из серии "зачем учиться считать в уме, если на калькуляторе все можно посчитать?" ;)

Тут, все-таки раздел решения задач, и усложнение в том и состоит,
как этот каскад вызвать по имеющейся структуре данных на стеке.
А то что оно через перестановку битов решается, ясно сразу,
потому что любая перестановка есть комбинация перестановок пар.
И циклические перестановки - далеко не все из возможных.
Может быть, например, и два цикла перестановок, не задевающих друг друга групп битов.

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 23, 2010 09:49 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
forther писал(а):
да, красиво. у меня несколько иначе, но суть та же:Код:
: swab ( w m -- w')
2dup and dup 0= if drop exit then
dup 1- and if drop exit then
xor ;

У меня проще было(еще в прошлой задачке):
Код:
: SWAPB ( n bitmask -- n')
  2DUP AND OVER 1 SWAP WITHIN AND XOR ;

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 23, 2010 10:08 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
лихо!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт мар 23, 2010 16:05 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
вопрос писал(а):
: swabn ( w m -- w' )
\ где
\ w - исходное число
\ m - маска
\ переставить биты так, чтобы (а) последний oказался на месте первого
\ (в) каждый из остальных битов - на месте следующего в маске (циклический сдвиг, но не всего регистра, а
\ отмеченных в маске битов)

например, обозначив биты в байте буквами
a b c d e f g h
и имея маску
0 1 1 0 0 0 0 1
мы должны получить
a h b d e f g c
цвета показывают сдвиг


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

Реализация:
для простоты пусть маска будет определенная 0x90C1

Код:
\ обмен двух маскируемых разрядов числа
: SWAPB ( n bitmask -- n')
  2DUP AND OVER 1 SWAP WITHIN AND XOR ;

\ сжать-разжать маскируемые разряды числа
: QPERF \ n|n' -- n'|n
  0x42 SWAPB 0x84 SWAPB 0x1008 SWAPB 0x8010 SWAPB ;

CREATE BIN" 32 ALLOT

\ преобразовать число N разрядности R в строку вида "1011..00"
: Q>S \ N R -- A U
>R R@ 0
DO DUP 1 AND IF 1 BIN" I + C! THEN 2/ LOOP
DROP BIN" R> ;

\ циклический сдвиг содержимого строки вправо на один байт
: c>>" \ A U -- A U
2DUP 2>R OVER >R 2DUP + 1- C@ >R 1-
OVER 1+ SWAP MOVE R> R> C! 2R> ;

\ преобразовать строку вида "1011..00" в число
: S>Q \ A U -- N
0 -ROT OVER + SWAP DO 2* I C@ IF 1 OR THEN  LOOP ;

\ циклический сдвиг содержимого строки вправо на n байт
: nc>>" ( a u n -- a u) 0 DO c>>" LOOP ;

\ циклический сдвиг вправо только маскированных разрядов числа
: MSK-RSHIFT \ N MSK N1 -- N'
  BIN" 32 ERASE
  >R 2>R 2R@ AND QPERF
  5 Q>S 2R> R> -ROT 2>R nc>>" S>Q QPERF
  2R> INVERT AND XOR ;

\ test
0x2 BASE !

: TST  0x1486 0x10 .0 CR  0x90C1 0x10 .0 CR
  0xA 1 DO 0x1486 0x90C1 I MSK-RSHIFT CR 0x10 .0 LOOP ; STARTLOG TST HEX

лог.
Код:
0001010010000110
1001000011000001

0000010001000111
1000010000000111
1001010000000110
0001010010000110
0000010011000110
0000010001000111
1000010000000111
1001010000000110
0001010010000110
Ok

пс. Если непересекающихся масок несколько, то создать столько же строк,
их крутить на одинаковое значение раз, а затем получить искомое число.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB