number base conversion

 

Overview

This article covers the algorithm for and methods, and the math for, converting numbers and strings from/to one number base to another number base.

This kind of function I use all the time in my software so that users have a choice of the kind of input they would like to feed into my programs. I like to build in flexibility for my input, while leaving the absolutely simplest possible so as not to make the software hard to use. This is the type of function I use in 80%-90% of my programs and even some DHTML web pages for input handling: I want users to have the flexibility of being able to put any type of input format they would like.

here is a question I answered about converting decimal fractions to binary used to drive meto distraction in college. now it's normal for me and I think about bitset fixed point arithmetic C++ classes.

number base conversion - base to base

you can do this with a calculator if you have one. if you don't use TTCALC.

we are going to convert an unsigned binary number (base 2) 11100101011 to a new number base which we are going to invent. it could just as easily be hexadecimal (base 16) but I want you to not be stuck in a rut with canned ideas.

the new numbering system uses the numbering system of hexadecimal with the additional characters all the way through Z, for a total of 26 letters + 10 digits which is 36 characters, so the number base to convert TO is 36. The number base to convert FROM is binary, or 2.

The character set could just as well all be letters for that matter or even be punctuation, or symbols, the choice of the character set for representation of digits is entirely up to me, the inventor.

So our allowable digits character set is going to be 0123456789abcdefghijklmnopqrstuvwxyz

Get a decent scientific calculator which can do number BASEs like an HP 33s if you are cheap, very functional and useful and lasts a long time on coin cells or Li-Ion built-in rechargeable batteries. I have listed some very nice calculators. the HP 48IIg and 50g is an excellent calculator, but there's a lot of things about it that drive me up the wall,and a lot of things I like, and it uses up AAA and CR2032 batteries fairly quickly with college use so buy them in bulk. Casio graphing calculators have always been nice feature-wise and easy to use for programmers, and so have HP 33s and HP 35s.

You can skip the following steps if the conversion can be done directly on your calculator, but you should still learn how to do this the hard way, since you will need to learn how to code this. This is the type of function I use 80%-90% of my programs and even some DHTML web pages for input handling: I want users to have the flexibility of being able to put any type of input format they would like.

  1. convert to base 10, or whatever base is native, using your calculator, or your program.
  2. after the number is fully converted to a native base, convert the number to the target base.

I just posted a feature request into ttcalc to handle bit shifts and rotates, it's a necessary part of programming work. until then, use ttcalc to multiply the from_digit positions of the by their appropriate base power.

The Math

p=zero-based digit position right to left (base power index)
d[p]=digit at position p
b=base from
n=number of digits in number to convert from

number = p = 0 n - 1 d p × b p = ( d 0 × b 0 ) + ( d 1 × b 1 ) + ( d 2 × b 2 ) + ... + ( d n - 1 × b n - 1 )

You can ignore the zeros if you want to save calculator time.

for the example, let's look at the digit positions.

11100101011
-----------
10000000000
09876543210

everything to the left that we don't see are zero digits, so we can ignore those.

we have 1's in position 0, 1, 3, 5, 8, 9, 10. using our equation above and pluggin in the appropriate stuff, we get number = p = 0 11 - 1 d p × 2 p = ( 1 × 2 0 ) + ( 1 × 2 1 ) + ( 0 × 2 2 ) + ( 1 × 2 3 ) + ( 0 × 2 4 ) + ( 1 × 2 5 ) + ( 0 × 2 6 ) + ( 0 × 2 7 ) + ( 1 × 2 8 ) + ( 1 × 2 9 ) + ( 1 × 2 10 ) = 1835

You should memorize the powers of 2 and at least some of 16. you will use them a lot.

You should be able to write your own algorithm and think it out for yourself.

Usually it means working the number from left to right digit-wise, but according to its base power index (what I call p), it's exactly the opposite direction (base power index 0 is on the right and counts leftward).

To get the decimal answer (or native base) in the calculator converted back to binary (or any base), use the following algorithm:

decimals

thing iofthe digitpositionss like a number line going in both directions,where the digit to the left of the desimal point is 0.

base 2 weightings are only different from base 10 weightings in that just to the left of the decimal point is 2^0 and to the right is 2^-1, to the right of that is 2^-2, to the right of that is 2^-3 and so on.

0
Σ digitValue*base^digitpos
digitpos=-5

the digitvalue would be in the range 0..1 (the range of 0..base-1)

take 0.8515625 base 10-->base2 for instance.
work from left to right (larger values to smaller).
0. < 2^0 (1) so put 0 to left of decimal point.
.5 >= 2^-1 (0.5) so subtract 0.5 from 0.8515625 which gives 0.3515625 and put a 1 past 1st answer decimal point, 0.1
.04321 < 2^-2 (0.25) so subtract 0.25 from 0.3515625 which gives 0.1015625 and put a 1 past 1st answer decimal point, 0.11
.04321 < 2^-3 (0.125) so put a 0 past 3rd answer decimal point, 0.110
.04321 < 2^-4 (0.0625) so subtract 0.0625 from 0.1015625 which gives 0.0390625 and put a 1 past 1st answer decimal point, 0.1101
.04321 >= 2^-5 (0.03125) so subtract 0.03125 from 0.0390625 which gives 0.0078125 and put a 1 past 5th answer decimal point, 0.11011
.04321 < 2^-6 (0.015625) so put a 0 past 6th answer decimal point, 0.110110
.04321 >= 2^-7 (0.0078125) so subtract 0.0078125 from 0.0078125 which gives 0.0 and put a 1 past 7th answer decimal point, 0.1101101

some may be be irrational, a repeating decimal, or something else you will have to cut off, but a few like this one will be representable. the ones that won't will not end with 0.0 so early.

best case is you end up with a 0 for "gives".

Number base conversion integer to string algorithm:

variables:
base_to=base you are converting to
last_to_digit_pos=last zero-based digit_to position, right-to-left
last_from_digit_pos=last zero-based digit_from position, right-to-left
digit_from_pos=current from_digit position
digit_to_pos=current digit_to position
number_from=initially, number to start with
result=number_to

power algorithm:
function power(base, n) 
    result = 1
    for i = 1 to n
        result = result * base
    next
    return result
end function

algorithm #1:
COMMENT: this algorithm skips directly to the correct digit.  
COMMENT: it *can* be used for for making strings, but not recommended, see latter lines.
function integer_to_base_string(base_to, number_from, byreference result)
    base_charset = "0123456789abcdefghijklmnopqrstuvwxyz"
    result = 0
    number_from = 0
    if (0 == number_from) then
        result_string = "0"
        return success
    end if
    
    while number_from != 0 do
    
        COMMENT: powbase = find the next smallest/lesser power of base_to 
        COMMENT: that is closest to number_from
        COMMENT: figure out what position that power of (base-to-convert-to) is
        COMMENT: for powbase
        
        for digit_to_pos = 0 to last_from_digit_pos
            powbase = power(base_to, digit_to_pos)
            if (powbase > number_from) then
                digit_to_pos = digit_to_pos - 1
                powbase = power(base_to, digit_to_pos)
                exit this for loop
            else if (powbase == number_from) then
                exit this for loop
            end if
        next

        COMMENT:  write a digit_to down in that position as part of the answer.
        
        digit_to = ToInteger(number_from / base_to)
        if (digit_to > base_to) then
            return failure
        end if
        number_from = number_from - (digit_to * powbase)
        put digit_to in its correct place in result at position digit_to_pos
    end while
end function


algorithm #2:
COMMENT: we will assume zero-based indexes into strings
function integer_to_base_string(base_to, number_from, byreference result_string)
    base_charset = "0123456789abcdefghijklmnopqrstuvwxyz"
    COMMENT: for Javascript, maximum usable integer digits is 17 (2^53).
    COMMENT: you will need a lot more powerful power function for this, one that does floating point.
    last_to_digit_pos = Math.floor(Math.pow(power(2,53),1/36.0))
    result_string = ""
    if (0 == number_from) then
        result_string = "0"
        return success
    end if
    
    is_leading_zero_digits = true
    for digit_to_pos = last_to_digit_pos to 0 step -1
        powbase = power(base_to, digit_to_pos)
        digit_to = ToInteger(number_from / powbase)
        if (digit_to > base_to) then
            COMMENT: number_from too large for conversion, return failure
            return failure
        endif
        number_from = number_from - (digit_to * powbase);
        if (is_leading_zero_digits and 0 != digit_to) then
            is_leading_zero_digits = false
        end if
        if (not is_leading_zero_digits) then
        	COMMENT: if your strings are 1-based, then simply add 1 to digit_to
            result_string = result_string + base_charset.charAt(digit_to)
        endif
    next
    return success
end function

Number base conversion string to integer algorithm:

variables:
base_to=base you are converting to
last_to_digit_pos=last zero-based digit_to position, right-to-left
last_from_digit_pos=last zero-based digit_from position, right-to-left
digit_from_pos=current from_digit position
digit_to_pos=current digit_to position
number_from=initially, number to start with
string_from=the number to convert from in base base_to in the form of a string
number_to=

power algorithm:
function power(base, n) 
    result = 1
    for i = 1 to n
        result = result * base
    next
    return result
end function

COMMENT: we will assume zero-based indexes into strings
function StringPos(string_to_search, char_to_find)
    is_found = false
    for index = 0 to string_to_search.length() - 1
        if (char_to_find == string_to_search.charAt()) then
            is_found = true
            exit this for loop
        end if
    next
    if (is_found) then
        return index
    else
        COMMENT: return failure
        return -1
    end if
end function


algorithm #1:
COMMENT: we will assume zero-based indexes into strings
function base_string_to_integer(base_from, string_from, byreference number_to)
    base_charset = "0123456789abcdefghijklmnopqrstuvwxyz"
    string_from_length = string_from.length()
    last_from_digit_pos = string_from_length - 1
    MAX_from_digit_pos = Math.floor(Math.log(Math.pow(2,53))/Math.log(base_from))
    number_to = 0
    if (last_from_digit_pos > MAX_from_digit_pos) {
        return failure
    }
    for digit_from_pos = 0 to last_from_digit_pos
        COMMENT: the .toLowerCase is entirely optional.  If your character set string is case sensitive, 
        COMMENT: then use the string as it is without that function.
        digit_from = base_charset.indexOf(string_from.charAt(last_from_digit_pos - digit_from_pos).toLowerCase());
        if (-1 == digit_from) {
            return failure
        }
        powbase = power(base_from, digit_from_pos)
        number_to = number_to + (digit_from * powbase)
    next
    return success
end function

or you can simply in the display section put ttcalc's input and output base to whatever canned base you want, and then just type in the numbers. but I am sure this is not what your instructor is wanting you to do. I think he wants you to learn how to convert the numbers yourself. the reason why is sometimes in programming, you need to write number-string conversion routines and this requires the process I am outlining - breaking it down into powers of the base you want it in.

so you had better learn how to do this by hand now, or you will be up a creek when it comes time to do this in the real world over and over again programmatically and not with a calculator. sometimes you just need to build up your own library of routines, and this is one of them.

 

Number of digits

Number of base N (64, 36, 16, 10, 8, 2) digits that this program is compatible with in Javascript because of floating point arithmetic and its 17 usable mantissa digits (without corruption).

Math.floor(Math.log(Math.pow(2,53))/Math.log(64))= (digits, upper and lower case, @ and _)
Math.floor(Math.log(Math.pow(2,53))/Math.log(62))= (digits, upper and lower case)
Math.floor(Math.log(Math.pow(2,53))/Math.log(36))= (digits, upper or lower case)
Math.floor(Math.log(Math.pow(2,53))/Math.log(16))= (hexadecimal, digits upper or lower case a-f)
Math.floor(Math.log(Math.pow(2,53))/Math.log(10))= (digits)
Math.floor(Math.log(Math.pow(2,53))/Math.log(8))= (digits 0-7)
Math.floor(Math.log(Math.pow(2,53))/Math.log(2))= (digits 0-1)

physical calculators
HP 50g graphing calculator, available from hp.com $129.99
2300+ built-in functions. SD card slot. RPN, algebraic, and textbook data entry. FAT filesystem. 2.5MB RAM. 131x80 pixel display, RS232 and USB connectivity, external hardware (such as interfaces for data logging) available. made for scientists. it takes some months to learn how to use the thing, and it doesn't come with a physical manual - those are on the disc and there are 2 at 1000 pages each. the physical manual is just a getting started guide to help you put in the batteries, etc and do some very basic stuff. but once you have mastered some of the functions and base conversions, you can do some powerful things you can't with other calculators. you can think of the big graphing display also as multi-line text, in which you can put large entries. it also has an equation editor and has CAS (Computer Algebra System) and can solve equartions, simplify, factor, like I said, there are 2300+ functions :-). it also does unit conversions like meters to inches really well (I wonder if you can do that in hexadecimal (probably)...! most everything is basically a specifically formatted piece of text. functions are one of those, they look like a math function or C function, they have arguments separated by commas. programmable, but the manual in that area is terrible and doesn't give working examples. the calculator I got forgets its contents when you change the batteries. does financial. does fraction-real conversion and approximation. made for real work use, also happens to be useful in the classroom to solve problems IF you have the learning curve down. DO NOT buy this when you start college. buy this a year before you start college.
HP 35s Scientific Calculator, available from hp.com $59.99
decent little scientific calculator! made for real work use, also happens to be useful in the classroom to solve problems.
All HP Calculators, available from hp.com $$-$$$
made for real work use, also happens to be useful in the classroom to solve problems.
TI-Nspire™ CX CAS (Computer Algebra System) Handheld, available from ti.com $$-$$$
easy to use, made for classroom use.
All TI Calculators, available from ti.com $$-$$$
easy to use, made for classroom use.
Casio PRISM FX-CG10 Graphing Calculator, available from casio.com $129.99
programmable. does recursion. does financial. handles fractions (but I would like to see if it handles fraction-real conversion/approximation and how well it does that, casios didn't used to). has clip and paste, graph solve. I liked my casio when I had it. I always wished I had more, so I got an HP 50g. for classroom and 90% real work use.
All Casio Calculators, available from casio.com $$-$$$
for classroom and 90% real work use.
software calculators
PARI/GP Computer Algebra System (CAS), available from pari.math.u-bordeaux.fr free
includes PARI/gp and TTCalc, Eigenmath, and others.
TTCalc calculator, available from sf.net free
terrific general/programmer's calculator. you have to look in the help to find the rest of the functions. and you can define your own functions.
I have a collection of some symbolic math calculators here in the navigation.