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 ] |
Заголовок сообщения: | |
Да. решение см. дальше исправлено - нет, всё, кажется, правильно, это я так читал |
Автор: | 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/ |