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 (and does no sign extension):
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} 1if 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} 111if 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} 1010if 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} 5if 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} 1110if 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} 1001if 0 {
}