Перестановка битов F # - PullRequest
Новая
       12

Перестановка битов F #

0 голосов
/ 05 ноября 2018

Я пытаюсь сделать небольшую перестановку перестановок в F #.

https://en.wikipedia.org/wiki/Bit-reversal_permutation

Я знаю, как это сделать в Python: 

def bitrev(x, bits):
    y = 0
    for i in range(bits):
        y = (y << 1) | (x & 1)
        x >>= 1
    return y

, который должен вернуть следующий список, если, скажем, биты = 4 для значений в диапазоне 0-15: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

Как я могу сделать это без изменяемых значений?

Ответы [ 2 ]

0 голосов
/ 06 ноября 2018

В случае, если вас интересуют не только отдельные элементы a(m, k), где m < 2^k и k = 0, 1, 2, ..., но и инволюции в виде больших блоков последовательности A030109 в OEIS : Для него легко написать генератор. 

let a030109 =
    seq[0] |> Seq.unfold (fun xs ->
        let ys = Seq.map ((*) 2) xs
        let zs = Seq.map ((+) 1) ys
        Some(xs, Seq.append ys zs) )
    |> Seq.concat

a030109
|> Seq.skip (pown 2 4 - 1)
|> Seq.take (pown 2 4)
|> Seq.toList
// val it : int list = [0; 8; 4; 12; 2; 10; 6; 14; 1; 9; 5; 13; 3; 11; 7; 15]
0 голосов
/ 05 ноября 2018

Вы всегда можете пойти императивным путем и сделать прямой перевод с Python: 

let bitrev x bits =
    let mutable x = x
    let mutable y = 0
    for i in 1..bits do
        y <- (y <<< 1) ||| (x &&& 1)
        x <- x >>> 1
    y

Который вы запускаете так: 

[0..15]
|> List.map (fun n -> bitrev n 4)
|> printfn "%A"

// [0; 8; 4; 12; 2; 10; 6; 14; 1; 9; 5; 13; 3; 11; 7; 15]

Функциональный способ с неизменяемостью будет выглядеть так: 

let bitrev x bits =
    let rec bitrevR x bits y =
        match bits with
        | 0 -> y
        | _ ->
        bitrevR (x >>> 1) (bits - 1)  ((y <<< 1) ||| (x &&& 1))
    bitrevR x bits 0

Внутренние представления для чисел между 0..15 - 4 бита: 

binary  decimal
  0000  =  0
  0001  =  1
  0010  =  2
  0011  =  3
  0100  =  4
  0101  =  5
  0110  =  6
  0111  =  7
  1000  =  8
  1001  =  9
  1010  = 10
  1011  = 11
  1100  = 12
  1101  = 13
  1110  = 14
  1111  = 15

, который перевернулся, выглядит так: 

binary  decimal
0000  =  0   <->   0000 =  0
0001  =  1   <->   1000 =  8
0010  =  2   <->   0100 =  4
0011  =  3   <->   1100 = 12
0100  =  4   <->   0010 =  2
0101  =  5   <->   1010 = 10
0110  =  6   <->   0110 =  6
0111  =  7   <->   1110 = 14
1000  =  8   <->   0001 =  1
1001  =  9   <->   1001 =  9
1010  = 10   <->   0101 =  5
1011  = 11   <->   1101 = 13
1100  = 12   <->   0011 =  3
1101  = 13   <->   1011 = 11
1110  = 14   <->   0111 =  7
1111  = 15   <->   1111 = 15
...