Methods for converting between the decimal and binary representation of positive integers

- Big bitstring operations
- Converting an integer to a base 2 string
- to.binary
- Math on binary strings
- To little endian

Converting the decimal representation of a number to binary, eg, 6 -> 110

proc int2bits {i} { #returns a string, e.g. int2bits 10 => 1010 set res {} if {$i < 0} { set sign - set i [expr {abs($i)}] } else { set sign {} } while {$i>0} { set res [expr {$i%2}]$res set i [expr {$i/2}] } if {$res == {}} {set res 0} return $sign$res }

In the following example, which requires Tcl 8.6 or later, %lb or %b could be used, but $int would then be truncated if necessary. Also, in the case of %lb or %b, if $int is too large, the result could be nonsensical, as a truncated version of the machine representation of a negative integer would be returned.

package require Tcl 8.6 proc int2bits {int} { return [format %llb $int] }

The following example includes a "width" option to set the width of the resulting string

proc int2bits {i {width {}}} { #returns the binary representation of $i # width determines the length of the returned string (left truncated or added left 0) # use of width allows concatenation of bits sub-fields set res {} if {$i<0} { set sign - set i [expr {abs($i)}] } else { set sign {} } while {$i>0} { set res [expr {$i%2}]$res set i [expr {$i/2}] } if {$res == {}} {set res 0} if {$width != {}} { append d [string repeat 0 $width] $res set res [string range $d [string length $res] end] } return $sign$res }

Another alternative is to use [[binary]

proc int2bits {i} { #returns the binary representation of $i e.g. int2bits 10 => 1010 #this did not work properly where $i > [expr {2**32-1}] #binary scan [binary format I1 $i] B* x if {$i == 0} { return 0 } elseif {$i > 0} { set sign {} } else { set sign - set i [expr {abs($i)}] } while {$i>0} { set mod [expr {$i % 256}] set i [expr {$i/256}] lappend mods $mod } binary scan [binary format c* [lreverse $mods[set mods {}]]] B* x return $sign[string trimleft $x 0] }

To convert the binary representation of a number to decimal, e.g. 110 -> 6:

proc bits2int {bits} { if {$bits<0} { set sign - set bits [expr {abs($bits)}] } else { set sign {} } return $sign[expr 0b$bits] }

proc bits2int {bits} { #returns integer equivalent of $bits set res 0 if {$bits < 0} { set sign - set bits [expr {abs($bits)}] } else { set sign {} } foreach i [split $bits {}] { set res [expr {$res*2+$i}] } return $sign$res }

[[binary] could also be used:

proc bits2int {bits} { #returns decimal representation of the binary representation $bits if {$bits == 0} { return 0 } elseif {[string index $bits 0] eq "-"} { set sign - set bits [string range $bits 1 end] } else { set sign {} } set mod [expr {[string length $bits]%8}] if {$mod} { set mod [expr {8-$mod}] } set bits [string repeat 0 $mod]$bits set len [string length $bits] set bits [binary format B* $bits] if {$len<=8} { binary scan $bits cu res } elseif {$len <=16} { binary scan $bits Su res } elseif {$len <=32} { if {$len <= 24} { set bits [binary format B* 0]$bits } binary scan $bits Iu res } else { set res 0 set blen [expr {$len/8}] set pos -1 while {$blen} { incr blen -1 binary scan $bits x[incr pos]cu next set res [expr {$res + $next*(2**($blen*8))} ] } } return $sign$res }

authors: RS, Joseph Collard, PYK

'Nother variation: use [[format] to convert to octal (or hexadecimal, for

that matter), and "string map ..." to transform octal digits to bit patterns.

proc int2bits x { string map { 0 {0 0 0} 1 {0 0 1} 2 {0 1 0} 3 {0 1 1} 4 {1 0 0} 5 {1 0 1} 6 {1 1 0} 7 {1 1 1} } [split [format %o $x] ""] } ;#RS - note however that the bit sequence is multiples of 3 long: % int2bits 9 0 0 1 0 0 1 % int2bits 255 0 1 1 1 1 1 1 1 1

Lars H: A simple variation on that, without leading zeros and about 30% faster, since it avoids the split:

proc int2bits x { string map { +0 0 +1 1 +2 {1 0} +3 {1 1} +4 {1 0 0} +5 {1 0 1} +6 {1 1 0} +7 {1 1 1} 0 { 0 0 0} 1 { 0 0 1} 2 { 0 1 0} 3 { 0 1 1} 4 { 1 0 0} 5 { 1 0 1} 6 { 1 1 0} 7 { 1 1 1} } [format +%o $x] }

Helmut Giese in c.l.t:

proc val2Bin val { set binRep [binary format c $val] binary scan $binRep B* binStr return $binStr } # some tests puts [val2Bin 10] puts [val2Bin 129] puts [val2Bin 0x7F]

Arjen Markus The following fragment converts a hexadecimal representation to a floating-point number:

# Convert between float and hex # set hex "f3080000" set bin [binary format h8 $hex] binary scan $bin f float puts "$float"

On a big-endian machine the result is "1.0" (on a little-endian machine it is bizarre: 4.6006..e-041, but that is simply because the bytes are reversed.)

For extracting "unsigned" floating-point values from very long (>32 bits) integers in hex, MS has this recommendation on c.l.t.:

proc conv {largeHex} { set res 0.0 foreach hexDigit [split $largeHex {}] { set new 0x$hexDigit set res [expr {16.0*$res + $new}] } return $res }

Arjen Markus: Suppose you have a sequence of bytes that are read from a file. Two of these, say at position 6 and 7 (counting from 0), make up an integer number. Then:

set two_bytes [string range $str 6 7] binary scan "\0\0$two_bytes" I intvalue

will turn these two bytes into an integer (consisting of 4 bytes, hence the two leading nulls), if the original data are in big-endian order.

If they are in little-endian order, use:

set two_bytes [string range $str 6 7] binary scan "${two_bytes}\0\0" i intvalue

(Note: trailing nulls and a different format)

Eric Amundsen: Here's a solution that seems to work fine for 64-bit 2's complement integer math.

proc bin2int {binString} { set result 0 for {set j 0} {$j < [string length $binString]} {incr j} { set bit [string range $binString $j $j] set result [expr $result << 1] set result [expr $result | $bit] } return $result } set binaryString 11001 puts [bin2int $binaryString]

KBK: contributed this version in the Tcl chatroom on 2002-11-18:

proc fromBinary { digitString } { set r 0 foreach d [split $digitString {}] { incr r $r incr r $d } return $r }

TV 2003-04-24: The above is along the lines which one could use in a reusable low level implementation. The complement in similar manner could be:

set a 16; set r {}; while {$a != 0} {set h [expr $a/2]; if {[expr $h+$h] != $a} {set r "1$r"} {set r "0$r"} ; set a $h } puts $r

The result should be split to get a list from the string, and the domain is limited by the ceiling for expr based addition and division.

Addition and division by two can be fast for low level implementation, and the method can probably easily be used with an infinite math package (I've seen one but didn't try it out yet).

Lars H 2005-02-05:

The following two converters came out of a "challenge" at Googol magnitude. Since they are simply doing things to strings, they are not limited by [[expr] precision!

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 } proc int2bits {n} {split [dec2bin $n] ""} proc bits2int {n} {bin2dec [join $n ""]}

The idea of dec2bin is to alternate between a normal decimal notation and an a bi-quinary [L1 ] or "abacistic" notation where there are separate positions for fives (**i** = a five, **o** = no five). It is easy to generate the abacistic notation for half of a number in decimal notation -- just half every digit in place, e.g. 7 -> 3i -- and also easy to convert from abacistic to decimal notation, e.g. i3 -> 8. (Note that this doesn't combine **i**s and **o**s into the same decimal position as they were split off from.) **i**s and **o**s that don't have a digit to their right to recombine with constitute the bits that have been shifted out from the decimal number. bin2dec does the same thing backwards, with an extra **h** in the leftmost position to discard unnecessary zeroes.

% dec2bin 987654 11110001001000000110 % bin2dec 11110001001000000111 987655 % bin2dec 1[string repeat 0 64] 18446744073709551616

ET: This last example shows the problem with binary digits: They're impossible to read after just a few digits. While I never liked the language ADA, it did have an idea that I wish had caught on, the optional use of an underscore character in large numerical constants, to make the numbers readable. (And trival for a compiler or interpreter to scan/parse).

So, 1_234_567 is a number that is as readable as 1,234,567 and is much better than 1234567. I have a handy little converter, (which I stole from somewhere on this wiki and modifed):

proc {commas} {var {num 3} {char ","}} { set len [string length $var] set first [expr $len - $num] set x "" while { $len > 0} { # grab left num chars set lef [string range $var $first end] if {[string length $x] > 0} { set x "${lef}$char${x}" } else { set x ${lef} } # grab everything except left num chars set var [string range $var 0 [expr $first -1]] set len [string length $var] set first [expr $len - $num] } return $x }

Here are some examples of its use:

dec2bin 987654 11110001001000000110 % commas [dec2bin 987654] 4 _ 1111_0001_0010_0000_0110 % commas [dec2bin 987654] 4 { } 1111 0001 0010 0000 0110 % commas [dec2bin 987654] 1 { } 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 %commas 123456789 ;# naturally, it defaults for use with large decimal integers 123,456,789 % commas 123456789 3 _ ;# and here's how I wish numbers could be entered, in tcl and in C etc. 123_456_789 % puts "0x[commas [format %08X 123456789] 4 _]" ;# and for hex numbers as well 0x075B_CD15

Larry: Very interesting page! Is there aywhere on the page code that simply converts numbers into binary?

For example we have CW000-aa000 and we'd like the program to first search the CW string then convert into binary numbers at position 3-4-5 and 9-10-11.

Chad: Why is it that after

binary scan [binary format f 393.84] f n

the value of n is 393.839996338?

AM 2011-01-14: This is a classic problem: the decimal number 393.84 can not be represented exactly in the binary format that most contemporal computers use. The value you see is the closest binary value. Compare this to the difficulty of representing 1/3 in decimal numbers.

LV: Are there any languages which provide an add-on module or mode of operation where **real** variables are represented in a programmatic form designed not to lose percision? I was thinking that perhaps APL or LISP was one such language.

Perhaps someone has - or could - create a package for Tcl that would permit one to do math in that fashion for people who don't care about the lost computer cycles but do care about the precision.

CliC: Racket , a Scheme dialect, has "rational" types, so that e.g., 1/3 may be used in calculations with no loss of precision. I'm not a heavy user of it, though. I just downloaded it to check out the authors' "modern answer to SICP" programming tutorial.

GrahamDyke 2011-02-08 04:15:57:

Int2Bits And Bits2Int, Another Version:

proc Int2Bin { Int { Digits {} } } { set Res "" set Dig "" while {$Int > 0} { set Res [expr $Int % 2]$Res set Int [expr $Int / 2] } if { $Res == "" } { set Res 0 } if { $Digits != {} && [set Len [string length $Res]] < $Digits } { for {set Count 0} {$Count < [expr $Digits - $Len]} {incr Count} { set Res 0$Res } } return $Res }

Looking through the various examples for the Bits2Int solution I have noticed what appears to be a global flaw in the thinking. Every example assumes that the least significant bit in the binary string is on the left hand side. This is incorrect, the least significant bit in any binary number is always on the right hand side. This completely messes up the calculation. I was just wondering if any of these authors had actualy tested their code?

Here is a solution that works, assuming the binary string has the least significant bit on the right hand side. The string must first be reversed for the foreach to pick up the least significant bit first and so on.

proc Bin2Int { Bits } { set Res 0 set Base 1 set Inx [expr [string length $Bits] - 1] set New_Bits [split $Bits {}] foreach Bit $New_Bits { append Bits_1 [string index $Bits $Inx] incr Inx -1 } set Bits_2 [split $Bits_1 {}] foreach Bit $Bits_2 { set Res [expr $Res + ($Base * $Bit)] set Base [expr $Base * 2] } return $Res }

dcd 2011-02-11: It seems apropos to point to a page on converting Tcl integers to little-endian representations in various bases. To little endian