Bitwise Operations and Sets

Posted on January 1, 2013
Tags: algorithms

1 Basics

Set Encoding Binary Python
\(\emptyset\) \(0\) \(00000\) 0
\(\{0\}\) \(2^0=1\) \(00001\) 0
\(\{1\}\) \(2^1=2\) \(00010\) 0
\(\{2\}\) \(2^2=4\) \(00100\) 0
\(\{3\}\) \(2^3=8\) \(01000\) 0
\(\{4\}\) \(2^4=16\) \(10000\) 0
\(\{0,1,2,3\}\) \(2^4 - 1=15\) \(01111\) 0
\(\{3,4\}\) \(2^3 + 2^4=24\) \(11000\) 0

\(Set \rightarrow Encoding\)
\(\{n\} \mapsto 2^n\)
\(\{0,1,2,..n-1\} \mapsto 2^n-1\)

Why do we take n from \(\{n\}\) and Encode it by turning it into the exponent instead of simply converting to another base?

2 bitwise shift

2.1 shift right

5 >> 3

\[ floor(\frac{5}{2^3})\]

2.2 shift left

5 << 2

\[ 5 \times 2^3 \]

3 Sets


#eval (bit1 3) + (bit0 4)

inductive Bit := 
  | one : Bit
  | zero : Bit 
  deriving Repr

-- class Addbit (T : Type) where 
--   add : T -> T -> T 

open Bit



instance: Add Bit where 
  add : Bit -> Bit -> Bit :=
  λ x y => match (x, y) with 
    | (one, one) => one 
    | (one, zero) => one
    | (zero, one) => one
    | (zero, zero) => zero
  
#eval one + one

instance: AndOp Bit where 
  and : Bit -> Bit -> Bit :=
  λ x y => match (x, y) with 
    | (one, one) => one 
    | (one, zero) => zero
    | (zero, one) => zero
    | (zero, zero) => zero   

#eval one &&& one
#eval (. &&& one) <$> [zero,one]
-- #eval [(λ x => x &&& one),(λ x => x &&& one)] <*> [zero,one]

-- #eval [(λ x y => x + y),(λ x y => x * y)] <*> [1,2] <*> [3,4] 

instance: Applicative List where
  pure x := [x]
  seq f x :=
    match f with 
     | [] => [] 
     | f::fs => f <$> x ⟨⟩ 

#eval [(. + 1)] <*> [3,6]