переставить 2 бита в слове

forther

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

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

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

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

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

WingLion

Хотели "красивое?" нате!

Код:

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

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

вопрос

Да. решение

см. дальше

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

forther

да, красиво. у меня несколько иначе, но суть та же:

Код:

: swab ( w m -- w')
  2dup and dup 0= if drop exit then 
  dup  1- and if drop exit then
  xor ;

forther

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

вопрос

forther писал(а):

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

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

forther

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

вопрос

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

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

WingLion

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

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

\ data
mask1 swab
mask2 swab
mask3 swab
...

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

WingLion

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

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

chess

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

лихо!

chess

вопрос писал(а):

: 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

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

переставить 2 бита в слове

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