Big bitstring operations

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}     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 {


}