Forth
http://fforum.winglion.ru/

переставить 2 бита в слове
http://fforum.winglion.ru/viewtopic.php?f=19&t=2543
Страница 1 из 1

Автор:  forther [ Пн мар 22, 2010 21:54 ]
Заголовок сообщения:  переставить 2 бита в слове

А вот какая задачка мне на ум пришла:

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

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

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

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

Автор:  WingLion [ Пн мар 22, 2010 23:11 ]
Заголовок сообщения: 

Хотели "красивое?" нате! :)
Код:

\ решение для 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 - должно получиться АА


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

Автор:  вопрос [ Пн мар 22, 2010 23:27 ]
Заголовок сообщения: 

Да. решение 8)

см. дальше

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

Автор:  forther [ Пн мар 22, 2010 23:28 ]
Заголовок сообщения: 

да, красиво. у меня несколько иначе, но суть та же:
Код:
: swab ( w m -- w')
  2dup and dup 0= if drop exit then
  dup  1- and if drop exit then
  xor ;

Автор:  forther [ Пн мар 22, 2010 23:29 ]
Заголовок сообщения: 

А как усложнить?

Автор:  вопрос [ Пн мар 22, 2010 23:30 ]
Заголовок сообщения: 

forther писал(а):
А как усложнить?

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

Автор:  forther [ Пн мар 22, 2010 23:34 ]
Заголовок сообщения: 

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

Автор:  вопрос [ Пн мар 22, 2010 23:55 ]
Заголовок сообщения: 

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
цвета показывают сдвиг

Автор:  forther [ Вт мар 23, 2010 00:06 ]
Заголовок сообщения: 

WingLion, вы такое усложнение имели ввиду?

Автор:  WingLion [ Вт мар 23, 2010 05:33 ]
Заголовок сообщения: 

forther писал(а):
WingLion, вы такое усложнение имели ввиду?


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

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

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

Автор:  forther [ Вт мар 23, 2010 06:07 ]
Заголовок сообщения: 

а чем плох каскадный вызов swab?

\ data
mask1 swab
mask2 swab
mask3 swab
...

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

Автор:  WingLion [ Вт мар 23, 2010 06:26 ]
Заголовок сообщения: 

Ну, это вопрос из серии "зачем учиться считать в уме, если на калькуляторе все можно посчитать?" ;)

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

Автор:  chess [ Вт мар 23, 2010 09:49 ]
Заголовок сообщения: 

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 ;

Автор:  forther [ Вт мар 23, 2010 10:08 ]
Заголовок сообщения: 

лихо!

Автор:  chess [ Вт мар 23, 2010 16:05 ]
Заголовок сообщения: 

вопрос писал(а):
: 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

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

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/