Non-decimal radices/Convert

Non-decimal radices/Convert
You are encouraged to solve this task according to the task description, using any language you may know.

Number base conversion is when you express a stored integer in an integer base, such as in octal (base 8) or binary (base 2). It also is involved when you take a string representing a number in a given base and convert it to the stored integer form. Normally, a stored integer is in binary, but that's typically invisible to the user, who normally enters or sees stored integers as decimal.

Write a function (or identify the built-in function) which is passed a non-negative integer to convert, and another integer representing the base. It should return a string containing the digits of the resulting number, without leading zeros except for the number 0 itself. For the digits beyond 9, one should use the lowercase English alphabet, where the digit a = 9+1, b = a+1, etc. The decimal number 26 expressed in base 16 would be 1a, for example.

Write a second function which is passed a string and an integer base, and it returns an integer representing that string interpreted in that base.

The programs may be limited by the word size or other such constraint of a given language. There is no need to do error checking for negatives, bases less than 2, or inappropriate digits.

Ada

Ada provides built-in capability to convert between all bases from 2 through 16. This task requires conversion for bases up to 36. The following program demonstrates such a conversion using an iterative solution. <ada>with Ada.Text_Io; use Ada.Text_Io; with Ada.Strings.Fixed; With Ada.Strings.Unbounded;

procedure Number_Base_Conversion is

  Max_Base : constant := 36;
  subtype Base_Type is Integer range 2..Max_Base;
  Num_Digits : constant String := "0123456789abcdefghijklmnopqrstuvwxyz";
  Invalid_Digit : exception;
  
  function To_Decimal(Value : String; Base : Base_Type) return Integer is
     use Ada.Strings.Fixed;
     Result : Integer := 0;
     Decimal_Value : Integer;
     Radix_Offset : Natural := 0;
  begin
     for I in reverse Value'range loop
        Decimal_Value := Index(Num_Digits, Value(I..I)) - 1;
        if Decimal_Value < 0 then
           raise Invalid_Digit;
        end if; 
        Result := Result + (Base**Radix_Offset * Decimal_Value);
        Radix_Offset := Radix_Offset + 1;
     end loop;
     return Result;
  end To_Decimal;
  
  function To_Base(Value : Natural; Base : Base_Type) return String is
     use Ada.Strings.Unbounded;
     Result : Unbounded_String := Null_Unbounded_String;
     Temp : Natural := Value;
     Base_Digit : String(1..1);
  begin
     if Temp = 0 then
        return "0";
     end if;
     while Temp > 0 loop
        Base_Digit(1) := Num_Digits((Temp mod Base) + 1);
        if Result = Null_Unbounded_String then
           Append(Result, Base_Digit);
        else
           Insert(Source => Result,
              Before => 1,
              New_Item => Base_Digit);
        end if;
        Temp := Temp / Base;
     end loop;
     return To_String(Result);
  end To_Base;
  

begin

  Put_Line("26 converted to base 16 is " & To_Base(26, 16));
  Put_line("1a (base 16) is decimal" & Integer'image(To_Decimal("1a", 16)));

end Number_Base_Conversion;</ada>

C++

<cpp>#include <limits>

1. include <string>
2. include <cassert>

std::string const digits = "0123456789abcdefghijklmnopqrstuvwxyz";

std::string to_base(unsigned long num, int base) {

 int const max_size = std::numeric_limits<char>::digits  * sizeof(unsigned long);
 char s[max_size + 1];
 char* pos = s + max_size;
 *pos = '\0';
 if (num == 0)
 {
   *--pos = '0';
 }
 else
 {
   while (num > 0)
   {
     *--pos = digits[num % base];
     num /= base;
   }
 }
 return pos;

}

unsigned long from_base(std::string const& num_str, int base) {

 unsigned long result = 0;
 for (std::string::size_type pos = 0; pos < num_str.length(); ++pos)
   result = result * base + digits.find(num_str[pos]);
 return result;

}</cpp>

Common Lisp

<lisp>(setq *print-base* 16) (write-to-string 26) ; returns the string 1A (setq *read-base* 16) (read-from-string "1a") ; returns the integer 26</lisp>

D

D standard library string module included functions to convert number to string at a radix. <d>module std.string; char[] toString(long value, uint radix); char[] toString(ulong value, uint radix);</d> Implementation. <d>module radixstring ; import std.stdio ; import std.ctype ;

const string Digits = "0123456789abcdefghijklmnopqrstuvwxyz" ;

int dtoi(char dc, int radix) {

 static int[char] digit ;
 char d = tolower(dc) ;
 if (digit.length == 0) // not init yet
   foreach(i,c ; Digits)
     digit[c] = i ;
 if (radix > 1 & radix <= digit.length)
   if (d in digit)
     if (digit[d] < radix) 
       return digit[d] ;
 return int.min ; // a negative for error ;

}

ulong AtoI(string str, int radix = 10, int* consumed = null) {

 ulong result = 0; 
 int sp = 0 ;
 for(; sp < str.length ; sp++) {
   int d = dtoi(str[sp], radix) ;
   if (d >= 0)  // valid digit char
     result = radix*result + d ;     
   else
     break ;
 }     
 if(sp != str.length)      // some char in str not converted
   sp = -sp ;
 if (!(consumed is null))  // signal error if not positive ;
   *consumed = sp ;
 return result ;

}

string ItoA(ulong num, int radix = 10) {

 string result = null ;  

// if (radix < 2 || radix > Digits.length) throw Error

 while (num > 0) {
   int d = num % radix ;
   result = Digits[d]~ result ;
   num = (num - d) / radix ;
 } 
 return result == null ? "0" : result ;

}

void main(string[] args) {

 string numstr = "1ABcdxyz???" ;
 int ate ;
 writef("%s (%d) = %d",numstr, 16, AtoI(numstr, 16, &ate)) ;
 if(ate <= 0) writefln("\tcheck: %s<%s>",numstr[0..-ate], numstr[-ate..$]) ; 
 else writefln() ;
 writefln(ItoA(60272032366,36)," ",ItoA(591458,36)) ;  

}</d>

Forth

Forth has a global user variable, BASE, which determines the radix used for parsing, interpretation, and printing of integers. This can handle bases from 2-36, but there are two words to switch to the most popular bases, DECIMAL and HEX.

42 dup
2 base !
.   \ 101010
hex
.   \ 2A
decimal

Many variants of Forth support literals in some bases, such as hex, using a prefix

$ff .   \ 255

Fortran

Works with: Fortran version 90 and later

MODULE Conversion
  IMPLICIT NONE
  CHARACTER(36) :: alphanum = "0123456789abcdefghijklmnopqrstuvwxyz"
 
  CONTAINS

  FUNCTION ToDecimal(base, instr)
    INTEGER :: ToDecimal
    INTEGER :: length, i, n, base
    CHARACTER(*) :: instr

    ToDecimal = 0
    length = LEN(instr)
    DO i = 1, length
      n = INDEX(alphanum, instr(i:i)) - 1
      n = n * base**(length-i)
      Todecimal = ToDecimal + n
    END DO
  END FUNCTION ToDecimal

  FUNCTION ToBase(base, number)
    CHARACTER(31) :: ToBase
    INTEGER :: base, number, i, rem

    ToBase = "                               "
    DO i = 31, 1, -1
      IF(number < base) THEN
        ToBase(i:i) = alphanum(number+1:number+1)
        EXIT
      END IF
      rem = MOD(number, base)
      ToBase(i:i) = alphanum(rem+1:rem+1)
      number = number / base
    END DO
    ToBase = ADJUSTL(ToBase)
  END FUNCTION ToBase

END MODULE Conversion

PROGRAM Base_Convert
  USE Conversion

  WRITE (*,*) ToDecimal(16, "1a")
  WRITE (*,*) ToBase(16, 26)     

END PROGRAM

Haskell

It's actually more useful to represent digits internally as numbers instead of characters, because then one can define operations that work directly on this representation.

So conversion to and from digits represented as 0-9 and a-z is done in an additional step.

import Data.List
import Data.Char

toBase :: Int -> Int -> [Int]
toBase b v = toBase' [] v where
  toBase' a 0 = a
  toBase' a v = toBase' (r:a) q where (q,r) = v `divMod` b

fromBase :: Int -> [Int] -> Int
fromBase b ds = foldl' (\n k -> n * b + k) 0 ds

toAlphaDigits :: [Int] -> String
toAlphaDigits = map convert where
  convert n | n < 10    = chr (n + ord '0')
            | otherwise = chr (n + ord 'a' - 10)

fromAlphaDigits :: String -> [Int]
fromAlphaDigits = map convert where
 convert c | isDigit c = ord c - ord '0'
           | isUpper c = ord c - ord 'A' + 10
           | isLower c = ord c - ord 'a' + 10

Example:

*Main> toAlphaDigits $ toBase 16 $ 42
"2a"
*Main> fromBase 16 $ fromAlphaDigits $ "2a"
42

J

J supports direct specification of numbers by base, as in these examples:

   2b100 8b100 10b100 16b100 36b100 36bzy
4 64 100 256 1296 1294

Programs for conversion of numeric values to literals, and of literals to numbers:

numerals=: '0123456789abcdefghijklmnopqrstuvwxyz'
baseNtoL=: numerals {~ [ #.^:_1 ]
baseLtoN=: (#~ #) #. numerals i. ]

Examples of use:

   2 baseNtoL 100 101
1100100
1100101
   16 baseNtoL 26
1a
   36 baseLtoN 'zy'
1294

These may be combined so the conversion performed is derived from the type of argument received.

   base=: baseNtoL :: baseLtoN
   
   16 base 'aa'
170
   16 base 170
aa 

See also primary verbs Base and Antibase.

Java

for long's: <java>public static long backToTen(String num, int oldBase){

  return Long.parseLong(num, oldBase); //takes both uppercase and lowercase letters

}

public static String tenToBase(long num, int newBase){

  return Long.toString(num, newBase);//add .toUpperCase() for capital letters

}</java>

for BigInteger's: <java>public static BigInteger backToTenBig(String num, int oldBase){

  return new BigInteger(num, oldBase); //takes both uppercase and lowercase letters

}

public static String tenBigToBase(BigInteger num, int newBase){

  return num.toString(newBase);//add .toUpperCase() for capital letters

}</java>

JavaScript

<javascript>k = 26 s = k.toString(16) //gives 1a i = parseInt('1a',16) //gives 26 //optional special case for hex: i = +('0x'+s) //hexadecimal base 16, if s='1a' then i=26.</javascript>

OCaml

<ocaml>let int_of_basen n str =

 match n with
 | 16 -> int_of_string("0x" ^ str)
 |  2 -> int_of_string("0b" ^ str)
 |  8 -> int_of_string("0o" ^ str)
 | _ -> failwith "unhandled"

let basen_of_int n d =

 match n with
 | 16 -> Printf.sprintf "%x" d
 |  8 -> Printf.sprintf "%o" d
 | _ -> failwith "unhandled"</ocaml>

# basen_of_int 16 26 ;;
- : string = "1a"

# int_of_basen 16 "1a" ;;
- : int = 26

Perl

Perl has some built-in capabilites for various conversions between decimal, hexadecimal, octal, and binary, but not other bases. <perl>sub digitize

1. Converts an integer to a single digit.

{my $i = shift;
 return $i < 10
   ? $i
   : ('a' .. 'z')[$i - 10];}

sub undigitize

1. Converts a digit to an integer.

{my $i = shift;
 return $i =~ /\d/
   ? $i
   : 10 + ord($i) - ord('a');}

sub to_base

{my ($int, $radix) = @_;
 my $numeral = digitize($int % $radix);
 $numeral .= digitize($int % $radix)
     while $int = int($int / $radix);
 return scalar reverse $numeral;}

sub from_base

{my ($numeral, $radix) = @_;
 $numeral = reverse $numeral;
 my $int = 0;
 for (my $n = 0 ; $numeral ; ++$n)
    {$int += $radix**$n * undigitize substr($numeral, 0, 1, );}
 return $int;}</perl>

PHP

PHP has a base_convert() function that directly converts between strings of one base and strings of another base: <php>base_convert("26", 10, 16); // returns "1a"</php>

If you want to convert a string to an integer, the intval() function optionally takes a base argument when given a string: <php>intval("1a", 16); // returns 26</php>

To go the other way around, I guess you can use base_convert() again; I am unaware of a better way: <php>base_convert(26, 10, 16); // returns "1a"</php>

In addition, there are specialized functions for converting certain bases: <php>// converts int to binary string decbin(26); // returns "11010" // converts int to octal string decoct(26); // returns "32" // converts int to hex string dechex(26); // returns "1a" // converts binary string to int bindec("11010"); // returns 26 // converts octal string to int octdec("32"); // returns 26 // converts hex string to int hexdec("1a"); // returns 26</php>

Pop11

Pop11 can input and output routines can use any base up to 36 (depending on value 'pop_pr_radix' variable). 'radix_apply' runs i/o routine temporarly setting 'pop_pr_radix' to given value. 'sprintf' procedure instead of printing returns string. So, to convert number to given value we just compose built-in procedures:

define number_to_base(n, base);
    radix_apply(n, '%p', sprintf, base);
enddefine;

In input base optionally preceeds the number, for example 8:15 is 13. So, to convert string in given base we need to prepend base prefix and read number from string:

define string_in_base_to_number(s, base);
    incharitem(stringin(base >< ':' >< s))();
enddefine;

Python

<python>def baseN(num,b):

  return ((num == 0) and  "0" ) or ( baseN(num // b, b).lstrip("0") + "0123456789abcdefghijklmnopqrstuvwxyz"[num % b])

k = 26 s = baseN(k,16) # returns the string 1a i = int('1a',16) # returns the integer 26</python>

Ruby

s = 26.to_s(16) # returns the string 1a i = '1a'.to_i(16) # returns the integer 26