Created
June 18, 2012 16:31
-
-
Save miner/2949264 to your computer and use it in GitHub Desktop.
Miner's four-bit adder for Rosetta Code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; http://rosettacode.org/wiki/Four_bit_adder | |
(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 | |
([num] | |
{: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