Skip to content

Instantly share code, notes, and snippets.

@miner miner/fourbit.clj

Created Jun 18, 2012
What would you like to do?
Miner's four-bit adder for Rosetta Code
(ns miner.fourbit)
;; a bit is represented as a boolean (true/false)
;; a word is a big-endian vector of bits [true false true true] = 11
;; maybe little endian is more convenient???
(defn bvec
{:pre [(<= 0 num 0xFFFFFFFF)]}
(vec (drop-while false? (map #(bit-test num %) (range 31 -1 -1)))))
([num lowbits]
(mapv #(bit-test num %) (range (dec lowbits) -1 -1))))
(defn bit4 [num]
(bvec num 4))
(defn bvec->num [bvs]
(reduce (fn [tot bd] (+ (if bd 1 0) (* 2 tot))) 0 bvs))
;; bits are represented by booleans (true or false)
;; bit vectors are big-endian (msb first)
;; multiple values are returned as vectors
(defn or-gate [a b]
(or a b))
(defn and-gate [a b]
(and a b))
(defn not-gate [a]
(not a))
(defn xor-gate [a b]
(or-gate (and-gate (not-gate a) b) (and-gate a (not-gate b))))
(defn half-adder [a b]
"result is [carry sum]"
(let [carry (and-gate a b)
sum (xor-gate a b)]
[carry sum]))
(defn full-adder [a b c0]
"result is [carry sum]"
(let [[ca sa] (half-adder c0 a)
[cb sb] (half-adder sa b)]
[(or-gate ca cb) sb]))
;; big endian bit-vectors, results have one more bit (carry) than args
(defn recursive-nbit-adder
([va vb] (recursive-nbit-adder va vb () false))
([va vb ls cin]
{:pre [(= (count va) (count vb))]}
(if (seq va)
(let [[c s] (full-adder (peek va) (peek vb) cin)]
(recur (pop va) (pop vb) (conj ls s) c))
(vec (conj ls cin)))))
;; about same speed using reduce
(defn nbit-adder [va vb]
"va and vb should be big endian bit-vectors of the same size. The result is a bit vector having one more bit (carry) than args."
{:pre [(= (count va) (count vb))]}
(let [[c sumlist] (reduce (fn [[carry lsum] [a b]]
(let [[c s] (full-adder a b carry)]
[c (conj lsum s)]))
[false ()]
(map vector (rseq va) (rseq vb)))]
(vec (conj sumlist c))))
(defn four-bit-adder [a4 a3 a2 a1 b4 b3 b2 b1]
"Returns [carry s4 s3 s2 s1]"
(nbit-adder [a4 a3 a2 a1] [b4 b3 b2 b1]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.