2

I need help reversing bits in F# as done in this question Reverse bits in number. I'm new to F# and was wondering how we can do this?

let bitreverse x = 
   let mutable b = 0
       while x do 
          b >>>= 1
          b|= x & 1
          x >>>= 1
b

I'm not even sure the syntax is correct here. I am very knew to this language.

Community
  • 1
  • 1
user112901
  • 31
  • 3

2 Answers2

4

The direct translation into F# looks like this:

let bitreverse x = 
    let mutable x = x
    let mutable b = 0
    while x <> 0 do 
        b <- b <<< 1
        b <- b ||| (x &&& 1)
        x <- x >>> 1
    b

This is highly imperative with mutable values and this isn't usually how we'd tend to go about writing code in F#. Notice that re-assignment of a mutable variable is a little different to what you might be used to in an imperative language, you have to use <- which is called the destructive update operator.

Thankfully, it's pretty straightforward to translate this into a recursive function that uses immutable values which should be a little more idiomatic

let bitreverse2 x =
    let rec bitRerverseHelper b x =
        match x with
        |0 -> b // if 0, the recursion stops here and we return the result: b
        |_ -> bitRerverseHelper ((b <<< 1) ||| (x &&& 1)) (x >>> 1) // otherwise recurse
    bitRerverseHelper 0 x
TheInnerLight
  • 12,034
  • 1
  • 29
  • 52
  • Just curious, is there a shorter way to reverse bits than this? – user112901 May 20 '16 at 22:49
  • @user112901 Kind of, you could use `if` instead of pattern matching to put the logic on one line, e.g. `let rec bitRerverseHelper b x = if x = 0 then b else bitRerverseHelper ((b <<< 1) ||| (x &&& 1)) (x >>> 1)`. I find the pattern matching easier to read though. – TheInnerLight May 20 '16 at 22:59
  • I meant like is there another completely different way to reverse bits in F#? Like builtin functions, or any other logic that may be simpler/shorter than this logic? – user112901 May 20 '16 at 23:17
  • @user112901 Not built-in, no. This answer has a pretty thorough overview of some possible approaches, albeit described in C: http://stackoverflow.com/a/746203/5438433 so you could certainly go shorter for a data type smaller than `int.` – TheInnerLight May 20 '16 at 23:33
3
  1. F# doesn't support compound assignment, so you can't do something like b |= x & 1, you need to expand it to b <- b ||| (x &&& 1).
  2. The argument x isn't mutable, so you need to create a local binding and mutate that. It looks weird, but you can just write let mutable x = x as the first line of your function to shadow the existing binding with a mutable one.
  3. x is an int, not a bool, so you can't use it as the condition for your while loop. Use x <> 0 instead.
  4. Indentation matters in F#, so make sure that while and your final b both line up with the first let.

Fixing those issues will make your code work, but idiomatic F# would probably forgo the while loop and mutation and use a recursive inner function with an accumulator instead.

kvb
  • 54,864
  • 2
  • 91
  • 133