Wednesday, 18 January 2012

Value of a binary number

The test today is to write the code that will take a binary number expressed as a string of 0 and 1 characters and convert this to the integer value.

My first thought is to apply the old method where you step by character through the string, starting with an accumulator value initially zero.  Then, for each character, if the character is 1 you double the accumulator and add one, and if the character is 0 you just double your accumulator. When there are no more characters left the accumulator is the result.  So the function is:

(defn convert-binary [s]
  (loop [acc 0, s s]
    (if (seq s)
        (if (= \1 (first s))
            (recur (+ 1 (* 2 acc)) (rest s))
            (recur (* 2 acc) (rest s)))

However here we are writing a loop - - surely there is a quick way to bolt together the existing list processing function to do the work?

Well, we want to know the values of the digits, from the lowest upwards.  These of course are the powers of 2, which we can get by iterating adding a number to itself, starting from 1:-

user=>(take 10 (iterate #(+ % %) 1))
(1 2 4 8 16 32 64 128 256 512)

Alongside these we want the digits of the binary string in the order of least to greatest, which is just a matter of using function reverse.

user=>(reverse "1010")
(\0 \1 \0 \1)

Now we can use map to apply a function to these pairs: specifically, if the digit is 0 then return 0, but if the digit is 1 return the power-of-2 value of the digit from the other list.  This gives us a list of numbers corresponding to the absolute values of the digits.  Now we add these up by using reduce +.  Wrap this up as an anonymous function of a binary string b and we get this:-

(fn [b]
  (reduce +
    (map (fn [d v] (if (= \0 d) 0 v))
         (reverse b)
         (iterate #(+ % %) 1))))

No, there is going to be a much simpler way.

No comments:

Post a Comment