Автор |
Сообщение |
|
|
Заголовок сообщения: |
|
|
|
вопрос писал(а): : 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
пс. Если непересекающихся масок несколько, то создать столько же строк,
их крутить на одинаковое значение раз, а затем получить искомое число.
[quote="вопрос"]: 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 цвета показывают сдвиг[/quote]
Алгоритм - сжать все маскируемые разряды числа в число разрядности равной числу
маскируемых разрядов, затем это число преобразовать в строку - ее содержимое прокрутить,
потом собрать искомое число из исходного числа и числа, полученного из прокрученной строки.
Реализация:
для простоты пусть маска будет определенная 0x90C1
[code]\ обмен двух маскируемых разрядов числа : 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[/code] лог. [code]0001010010000110 1001000011000001
0000010001000111 1000010000000111 1001010000000110 0001010010000110 0000010011000110 0000010001000111 1000010000000111 1001010000000110 0001010010000110 Ok[/code]
пс. Если непересекающихся масок несколько, то создать столько же строк,
их крутить на одинаковое значение раз, а затем получить искомое число.
|
|
|
|
Добавлено: Вт мар 23, 2010 16:05 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
|
|
|
Добавлено: Вт мар 23, 2010 10:08 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
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 ;
[quote="forther"]да, красиво. у меня несколько иначе, но суть та же:Код: : swab ( w m -- w') 2dup and dup 0= if drop exit then dup 1- and if drop exit then xor ;[/quote]
У меня проще было(еще в прошлой задачке):
[code]: SWAPB ( n bitmask -- n') 2DUP AND OVER 1 SWAP WITHIN AND XOR ;[/code]
|
|
|
|
Добавлено: Вт мар 23, 2010 09:49 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Ну, это вопрос из серии "зачем учиться считать в уме, если на калькуляторе все можно посчитать?"
Тут, все-таки раздел решения задач, и усложнение в том и состоит,
как этот каскад вызвать по имеющейся структуре данных на стеке.
А то что оно через перестановку битов решается, ясно сразу,
потому что любая перестановка есть комбинация перестановок пар.
И циклические перестановки - далеко не все из возможных.
Может быть, например, и два цикла перестановок, не задевающих друг друга групп битов.
Ну, это вопрос из серии "зачем учиться считать в уме, если на калькуляторе все можно посчитать?" ;)
Тут, все-таки раздел решения задач, и усложнение в том и состоит,
как этот каскад вызвать по имеющейся структуре данных на стеке.
А то что оно через перестановку битов решается, ясно сразу,
потому что любая перестановка есть комбинация перестановок пар.
И циклические перестановки - далеко не все из возможных.
Может быть, например, и два цикла перестановок, не задевающих друг друга групп битов.
|
|
|
|
Добавлено: Вт мар 23, 2010 06:26 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
а чем плох каскадный вызов swab?
\ data
mask1 swab
mask2 swab
mask3 swab
...
Или по вашему биты разможаться тоже могут?
а чем плох каскадный вызов swab?
\ data
mask1 swab
mask2 swab
mask3 swab
...
Или по вашему биты разможаться тоже могут?
|
|
|
|
Добавлено: Вт мар 23, 2010 06:07 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
forther писал(а): WingLion, вы такое усложнение имели ввиду?
Да, только условие надо точнее задавать. Не просто циклический сдвиг, но и побитно указать, какой бит в какой сдвигается. В одной маске это не получится (т.к. биты в маске формально неразличимы/не по естественному порядку), поэтому на входе надо несколько масок задавать.
NBitsROL ( data, mask1, mask2, maskN -- result ) \ переместить бит по маске1 в бит по маске2, бит по маске2 в бит по маске3 и так далее, а бит по маскеN в бит по маске1.
Начать с N=3 и до N=32 (больше для 32-битного слова смысла нет)
Для N=2 - тривиально - : 2BitsROL OR BWAP ;
[quote="forther"]WingLion, вы такое усложнение имели ввиду?[/quote]
Да, только условие надо точнее задавать. Не просто циклический сдвиг, но и [u]побитно[/u] указать, какой бит в какой сдвигается. В одной маске это не получится (т.к. биты в маске формально неразличимы/не по естественному порядку), поэтому на входе надо несколько масок задавать.
NBitsROL ( data, mask1, mask2, maskN -- result ) \ переместить бит по маске1 в бит по маске2, бит по маске2 в бит по маске3 и так далее, а бит по маскеN в бит по маске1.
Начать с N=3 и до N=32 (больше для 32-битного слова смысла нет)
Для N=2 - тривиально - [b]: 2BitsROL OR BWAP ;[/b]
|
|
|
|
Добавлено: Вт мар 23, 2010 05:33 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
WingLion, вы такое усложнение имели ввиду?
WingLion, вы такое усложнение имели ввиду?
|
|
|
|
Добавлено: Вт мар 23, 2010 00:06 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
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
цвета показывают сдвиг
[quote="forther"]а не могли бы вы развернуть условие? типа что конкретно на входе и что конкретно на выходе. т.е. в общих чертах понятно, о чем вы, но как постановка задачи это не достаточно внятно.[/quote]
: swabn ( w m -- w' )
\ где
\ w - исходное число
\ m - маска
\ переставить биты так, чтобы (а) последний oказался на месте первого
\ (в) каждый из остальных битов - на месте следующего в маске (циклический сдвиг, но не всего регистра, а
\ отмеченных в маске битов)
например, обозначив биты в байте буквами
a b c d e f g h
и имея маску
0 [color=red][b]1[/b][/color][color=darkred] [b]1[/b][/color] 0 0 0 0[color=green][b] 1[/b][/color]
мы должны получить
a [color=green][b]h[/b][/color][color=red][b] b[/b][/color] d e f g [color=darkred] [b]c[/b][/color]
цвета показывают сдвиг
|
|
|
|
Добавлено: Пн мар 22, 2010 23:55 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
а не могли бы вы развернуть условие? типа что конкретно на входе и что конкретно на выходе. т.е. в общих чертах понятно, о чем вы, но как постановка задачи это не достаточно внятно.
а не могли бы вы развернуть условие? типа что конкретно на входе и что конкретно на выходе. т.е. в общих чертах понятно, о чем вы, но как постановка задачи это не достаточно внятно.
|
|
|
|
Добавлено: Пн мар 22, 2010 23:34 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
forther писал(а): А как усложнить?
поменять 3 или более битов по циклу - по кругу, задачка проста за счёт магического свойства числа 2 - количество состояний "истина - ложь"
[quote="forther"]А как усложнить?[/quote]
поменять 3 или более битов по циклу - по кругу, задачка проста за счёт магического свойства числа 2 - количество состояний "истина - ложь"
|
|
|
|
Добавлено: Пн мар 22, 2010 23:30 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
А как усложнить?
А как усложнить?
|
|
|
|
Добавлено: Пн мар 22, 2010 23:29 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
да, красиво. у меня несколько иначе, но суть та же: Код: : swab ( w m -- w') 2dup and dup 0= if drop exit then dup 1- and if drop exit then xor ;
да, красиво. у меня несколько иначе, но суть та же:[code]: swab ( w m -- w') 2dup and dup 0= if drop exit then dup 1- and if drop exit then xor ;[/code]
|
|
|
|
Добавлено: Пн мар 22, 2010 23:28 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Да. решение
см. дальше
исправлено - нет, всё, кажется, правильно, это я так читал
Да. решение 8)
см. дальше
исправлено - нет, всё, кажется, правильно, это я так читал
|
|
|
|
Добавлено: Пн мар 22, 2010 23:27 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Хотели "красивое?" нате!
Код: \ решение для 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 - должно получиться АА
п.с. А задачку надо бы усложнить...
Хотели "красивое?" нате! :)
[code]
\ решение для 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 [/code]
оптимизировать не пытался
результат:
[code] E1 - должно получиться E1 A9 - должно получиться A9 AA - должно получиться АА AA - должно получиться АА [/code]
п.с. А задачку надо бы усложнить...
|
|
|
|
Добавлено: Пн мар 22, 2010 23:11 |
|
|
|
|
|
Заголовок сообщения: |
переставить 2 бита в слове |
|
|
А вот какая задачка мне на ум пришла:
Поменять местами два бита в слове (32 битном). Переставляемые биты задаются маской. Маска это слово, в котором единице равны два бита (которые нужно поменять).
swab ( w m -- w')
например результатом
11111111111111111111111111111110 10000000000000000000000000000001
будет
01111111111111111111111111111111
Я сам решения пока не знаю, но чувствую, что должно быть что нибудь красивое.
PS. Для неправильно заданной маски (с не двумя единичными битами) результат не определен
А вот какая задачка мне на ум пришла:
Поменять местами два бита в слове (32 битном). Переставляемые биты задаются маской. Маска это слово, в котором единице равны два бита (которые нужно поменять).
swab ( w m -- w')
например результатом
11111111111111111111111111111110 10000000000000000000000000000001
будет
01111111111111111111111111111111
Я сам решения пока не знаю, но чувствую, что должно быть что нибудь красивое.
PS. Для неправильно заданной маски (с не двумя единичными битами) результат не определен
|
|
|
|
Добавлено: Пн мар 22, 2010 21:54 |
|
|
|
|