Hi all,

A very popular interview question is to try implement all arithemtic operations for integers without using all the usual suspects. After thinking for a while I concluded that I only really need inc/dec in order to implement everything else. And the good news is that one can easily implement inc/dec using bit-shifts like so:

(ns interview.arithmetic
  (:refer-clojure :exclude [- * / + inc dec even? odd?]))


(defn even? [x]
 (== 0 (bit-and x 1)))

(defn odd? [x]
 (== 1 (bit-and x 1)))

(defn- halve-int [x]
 (bit-shift-right x 1))

(defn- double-int [x]
 (bit-shift-left x 1))

(defn inc [x]
  (cond
    (even? x) (bit-xor x 1)
    (== -1 x) 0
  :else
     (-> x
        halve-int
        inc
        double-int)))

(defn dec [x]
  (if (odd? x) (bit-xor x 1)
  (-> x
     bit-not
     inc
     bit-not)))

At this point, having this I can implement all arithmetic operations on integers by combining 'iterate' + take/take-while. For example here is +:

(defn +
([] 0)
([x] x)
([x y]
(let [iter (if (neg? y) dec inc)]
  (->> x
     (iterate iter)
     (take (inc (Math/abs y)))
     last)))
([x y & more]
  (reduce + x (cons y more))))

The same pattern applies for [- * /]. My question is, can anyone see a better way of doing this? It seems pretty elegant to me but I'd like to see what other people think...

many thanks :)

Jim

ps: division is indeed a bit trickier than the rest due to positive/negative signs. Not really hard though...

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Reply via email to