Back to Questions
2.3k
views6
comments
Decimal to binary conversion
f#

Just thought I share my solution for exercise #6 found here which asked for a simple application to convert a decimal number to binary.
I used the first algorithm suggested here.

I'm hoping for suggestions and helpful critic as I am still learning.
Of course I realize that a real app would add some checks on the user input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

open System


module Program =


    [<EntryPoint>]
    let main(args: string[]) =

        // 6. Read integer from console and print its binary representation as list of binary digits [0; 1; 0 ..]
        let binaryOf d =
    
            let largestPowerOfTwoFor x =
                let rec findLargestPowerOfTwoFor x current =
                    if(Math.Pow(2.0, (float) current + 1.0) >= (float) x)
                    then current
                    else findLargestPowerOfTwoFor x (current + 1)
                
                findLargestPowerOfTwoFor x 0    
            
            let rec findBinaryOf num p =
                if (p < 0) 
                then []
                else
                    let powerOfTwo = Math.Pow(2.0, (float) p)
                    
                    if(powerOfTwo <= num)
                    then 
                       1 :: findBinaryOf (num - powerOfTwo) (p - 1)
                    else
                       0 :: findBinaryOf num (p - 1)
            
            findBinaryOf ((float) d) (largestPowerOfTwoFor d)
        
        
        let theInteger = 
            printf "Please enter an integer: "  
            Console.ReadLine().Trim() 
            |> Convert.ToInt32

        let _ = printfn "The binary presentation of %d is: %A" theInteger <| binaryOf theInteger
                
        let _ = Console.ReadKey()

        0
.

this sounds like an unfold to me

let f n = Seq.unfold (fun n -> if n = 0 then None else Some (n%2,n/2)) n |> Seq.toList |> List.rev

I only cater for positive number though

By on 1/11/2010 1:57 PM ()

Why work when you can cheat? :p

1
2
3
4

let convertToBinaryList (n:int) = 
    System.Convert.ToString(n,2)
    |> Seq.map (fun c -> int c - int '0')
    |> Seq.toList
By on 1/12/2010 4:42 AM ()

Here's another approach, taking advantage that the language exposes int to bit manipulation. To get the rightmost bit, do a bitwise and with 1 (n &&& 1). Then shift all the bits over by 1 (n >>> 1) and repeat:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 

module Test

open System

let getBinDigits n =
    let rec f n acc = 
        if n = 0 then acc 
                 else f (n >>> 1) ((n &&& 1) :: acc)
    f n []        

printf "Enter number: "
let i = Console.ReadLine() |> int
printfn "%A" (getBinDigits i)

Another way to do the same thing but without relying on direct bit manipulation is to think of it this way: Given an integer n, how can you tell the rightmost binary digit? Right rightmost digit, the one's column, will determine if the integer is odd. So we know the rightmost binary digit simply if it's odd or even. To find the next digit, first do integer division by two, then see if the result odd or even. Keep repeating until you hit zero.

Both algorithms are usually the same -- shifting by 1 bit is the same as integer division by 2, and bitwise and for 1 is the same as n mod 2. One benefit of this approach is that in F# is the bigint type doesn't support bitwise operations (as far as I know), but using division and mod does:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 

module Test

open System
open System.Numerics

let getBigBinDigits n =
    let rec f n acc = 
        if n = 0I then acc
                  else f (n / 2I) ((int (n % 2I)) :: acc)
    f n []        

printf "Enter number: "
let i = Console.ReadLine() |> bigint.Parse
printfn "%A" (getBigBinDigits i)
By on 1/11/2010 1:48 PM ()

Great, thanks for the answers.
I suppose all solutions (except for the 'cheating' way) are pretty much identical, just perform the division and obtaining of the remainder in different ways, but stick to the same underlying algorithm.

Since I would like to have a comparison, is there a way to post a solution using the other algorithm (the one that I referred to, which first finds the largest power ... )?
I would like to improve the elegance/brevity of my code.
Some critique on it would also be appreciated.

By on 1/12/2010 9:27 AM ()

Both algorithm are the same, you still need to work from bit 0.

Michael and kvb have shown two nice implementations using recursion.

I was lately learning foldr and unfold(following the call of Eric Meijer in his recent C9 video promoting using higher order function if possible) and try the following:

1
2
3
4
5
6
7
8

let f n = 
  let step _ g (x::xs) = if x > n then xs else g (x+x::x::xs)
  let m = List.foldBack step [1..128] (fun x -> x) [2;1] 
  let OneOrZero (r,l) = 
    match l with 
     | [] -> None 
     | x::xs -> if r < x then Some(0,(r,xs)) else Some(1,(r-x,xs))
  Seq.unfold OneOrZero (n,m) |> Seq.toList

again it only handles positive number and 32 bit integer. changing [2;1] to [2L;1L] would make it take 64 bit integer. I would love to know how to make n becomes 'a where 'a supports the basic +/- and comparison.

By on 1/12/2010 6:18 PM ()

First of all, as coded your algorithm has a problem: it doesn't give the right answer for any power of two because it gets the wrong highest power.

If you want to stick with something in the vein of your original algorithm, here's how I would do it:

1
2
3
4
5
6
7
8
9
10
11
12

let binaryOf d =
  let rec largestPower p =
    let p' = 2*p
    if (p'-1 >= d) then p
    else largestPower p'
  let rec binaryFor n p =
    if p = 0 then []
    elif p <= n then
      1 :: (binaryFor (n-p) (p/2))
    else
      0 :: (binaryFor n (p/2))
  binaryFor d (largestPower 1)

Note that this never converts ints to floats, and that all exponentiation is done by recursively multiplying (or dividing, in the case of binaryFor) by 2. The only subtlety here is that you need to check p'-1 >= d instead of the seemingly equivalent p'>d, since for arguments greater than (Int32.MaxValue/2) p' will overflow to Int32.MinValue. If you want something a bit more faithful to your original implementation, you could use the built-in pown function for integer exponentiation, but again you'll need to be careful since pown 2 32 overflows.

By on 1/12/2010 11:03 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper