if 0 {[Richard Suchenwirth] 2005-02-06 - The delightful exchanges on
[Googol magnitude] led [Lars H] to code, in [Binary representation
of numbers]:}
 proc dec2bin {num} {
    while {[regexp {[0-9]} $num]} {
       set num\
         [string map {o0 0 o1 1 o2 2 o3 3 o4 4 i0 5 i1 6 i2 7 i3 8 i4 9 0 ""}\
           [string map {0 0o 1 0i 2 1o 3 1i 4 2o 5 2i 6 3o 7 3i 8 4o 9 4i} $num]]
    }
    string map {i 1 o 0} $num
 }

 proc bin2dec {num} {
    set num h[string map {1 i 0 o} $num]
    while {[regexp {[io]} $num]} {
       set num\
         [string map {0o 0 0i 1 1o 2 1i 3 2o 4 2i 5 3o 6 3i 7 4o 8 4i 9 ho h hi h1}\
           [string map {0 o0 1 o1 2 o2 3 o3 4 o4 5 i0 6 i1 7 i2 8 i3 9 i4} $num]]
    }
    string range $num 1 end
 }
if 0 {These functions convert between decimal strings (unbounded by
arithmetic bit-width of integers, be they 32 or 64) and similarly unbounded
bit strings. (Virtual memory might present an ultimate bound...)
All numbers are non-negative integers, i.e. 0 or positive.

Now, what can we do with such bit strings, without being limited by bit
width? One obvious idea is to perform bitwise operations (& and, | or, ^ xor)
on two bit strings. For this, we need
to normalize both to equal length, by padding the shorter one with
zeroes. Then we can iterate over pairs of corresponding bits and apply the
operator (as that comes from an argument, the [expr] must be unbraced):}
 proc binop {a op b} {
    set la [string length $a]
    set lb [string length $b]
    if {$la>$lb} {
        set b [string repeat 0 [expr {$la-$lb}]]$b
    } elseif {$la<$lb} {
        set a [string repeat 0 [expr {$lb-$la}]]$a
    }
    set res ""
    foreach i [split $a ""] j [split $b ""] {
        append res [expr $i $op $j]
    }
    regsub ^0+ $res "" res     ;# suppress leading zeroes
    expr {$res eq ""? 0: $res} ;# but not with 0
 }
#-- Testing (using short strings, but Googols are fine too):
 proc test {cmd expected} {
    catch $cmd res
    if {$res ne $expected} {puts "$cmd->$res, expected $expected"}
 }
 test {binop    1 & 1000} 0
 test {binop   11 & 10}   10
 test {binop    1 | 1000} 1001
 test {binop 1111 ^ 101}  1010

#-- The single unary operator, bitwise NOT (~), gets specific code:
 proc bin! a {
    regsub ^0+ [string map {0 1 1 0} $a] "" res
    expr {$res eq ""? 0: $res} ;# but not with 0
 }

 test {bin! 1011}  100
 test {bin! 11111} 0
 test {bin! 0}     1

if 0 {Other bitstring operations involve shifting - left shift(<<)
corresponds to multiplication with powers of 2:}
 proc bin<< {bits n} {
    append bits [string repeat 0 $n]
 }
 test {bin<< 111 3} 111000
 test {bin<< 111 0} 111
if 0 {Right shift (>>) corresponds to integer division, remainder
discarded, by powers of 2. Note that this is "logical" shifting,
not arithmetical, where the sign bit would be propagated, but we don't
have one:}
 proc bin>> {bits n} {
    string range $bits 0 end-$n
 }
 test {bin>> 1010 2} 10
 test {bin>> 1010 0} 1010

if 0 {
Counting how many 1-bits are in a bit string is useful at times, and
that's easily done with [regexp]:}
 interp alias {} bitcount {} regexp -all 1

 test {bitcount 10110} 3
 test {bitcount 0} 0
 test {bitcount 11111} 5
 
if 0 {Now, just for the fun of it, addition (certainly not the most
efficient way to do it...) We need length normalization
again, but iterate from right to left:}
 proc bin+ {a b} {
    set la [string length $a]
    set lb [string length $b]
    if {$la>$lb} {
        set b [string repeat 0 [expr {$la-$lb}]]$b
    } elseif {$la<$lb} {
        set a [string repeat 0 [expr {$lb-$la}]]$a
        set la $lb
    }
    set res ""
    set carry 0
    for {set i [incr la -1]} {$i>=0} {incr i -1} {
        set sum [expr {$carry+[string index $a $i]+[string index $b $i]}]
        set res [expr {$sum%2}]$res ;# prepend latest bit
        set carry [expr {$sum/2}]
    }
    regsub ^0+ $carry$res "" res     ;# suppress leading zeroes
    expr {$res eq ""? 0: $res} ;# but not with 0
 }
 test {bin+ 11 100}  111
 test {bin+ 1  1}    10
 test {bin+ 111 111} 1110

if 0 {Given addition, multiplication is especially easy on base-2
numbers:}
 proc bin* {a b} {
    set res 0
    foreach bit [split $b ""] {
        if $bit {set res [bin+ $res $a]}
        append res 0 ;# shift <<1, i.e. double
    }
    string range $res 0 end-1 ;#-- undo the last <<1 shift
 }
 test {bin* 100  11} 1100
 test {bin* 1010 10} 10100
 test {bin* 11   11} 1001
 
if 0 {
----
[Category Mathematics] | [Arts and crafts of Tcl-Tk programming]
}