Non-decimal radices/Convert: Difference between revisions
Line 65: | Line 65: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
===Built in=== |
|||
{{works with|ALGOL 68|Standard - no extensions to language used}} |
|||
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}} |
|||
The ''formatted transput'' in '''ALGOL 68''' uses the '''format''' type ('''mode'''). |
|||
This '''format''' type has many similarities with modern ''regular expressions'' |
|||
and can be used to convert '''string''' patterns to and from many of the |
|||
built in types ('''mode'''s) in ALGOL 68. Here is an example converting |
|||
a numbers base. |
|||
<lang algol>INT base = 16, from dec = 26; |
|||
BITS to bits; |
|||
FORMAT hex repr = $n(base)r2d$; |
|||
FILE f; STRING str; |
|||
associate(f, str); |
|||
putf(f, (hex repr, BIN from dec)); |
|||
print(("Hex: ",str, new line)); |
|||
reset(f); |
|||
getf(f, (hex repr, to bits)); |
|||
print(("Int: ",ABS to bits, new line))</lang> |
|||
Output: |
|||
<pre> |
|||
Hex: 1a |
|||
Int: +26 |
|||
</pre> |
|||
Note that the only conversions "officially" available are for the bases 2r, 4r, 8r |
|||
and 16r. But [[ALGOL 68G]] allows formatting for all numbers in the range 2r to 16r. |
|||
===Implement=== |
|||
Handles signed and unsigned numbers from all bases. |
|||
{{trans|python}} |
{{trans|python}} |
||
Line 119: | Line 153: | ||
+256 => 100 => +256 |
+256 => 100 => +256 |
||
</pre> |
</pre> |
||
===Libraries=== |
|||
As of February 2009 no open source libraries to do this task have been located. |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
<lang cpp>#include <limits> |
<lang cpp>#include <limits> |
Revision as of 01:37, 16 February 2009
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. <lang 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;</lang>
ALGOL 68
Built in
The formatted transput in ALGOL 68 uses the format type (mode). This format type has many similarities with modern regular expressions and can be used to convert string patterns to and from many of the built in types (modes) in ALGOL 68. Here is an example converting a numbers base.
<lang algol>INT base = 16, from dec = 26; BITS to bits;
FORMAT hex repr = $n(base)r2d$;
FILE f; STRING str;
associate(f, str); putf(f, (hex repr, BIN from dec)); print(("Hex: ",str, new line));
reset(f); getf(f, (hex repr, to bits)); print(("Int: ",ABS to bits, new line))</lang> Output:
Hex: 1a Int: +26
Note that the only conversions "officially" available are for the bases 2r, 4r, 8r and 16r. But ALGOL 68G allows formatting for all numbers in the range 2r to 16r.
Implement
Handles signed and unsigned numbers from all bases.
<lang algol> STRING numeric alpha = "0123456789abcdefghijklmnopqrstuvwxyz";
PROC raise value error = ([]STRING args)VOID: (
put(stand error, "Value error"); STRING sep := ": "; FOR index TO UPB args - 1 DO put(stand error, (sep, args[index])); sep:=", " OD; new line(stand error); stop
);
PROC base n = (INT num, base)STRING: (
PROC base n = (INT num, base)STRING: ( num = 0 | "" | base n(num OVER base, base) + numeric alpha[@0][num MOD base]); ( num = 0 | "0" |: num > 0 | base n(num, base) | "-" + base n(-num, base) )
);
PROC unsigned int = (STRING repr, INT base)INT:
IF UPB repr < LWB repr THEN 0 ELSE INT pos; IF NOT char in string(repr[UPB repr], pos, numeric alpha) THEN raise value error("CHAR """+repr[UPB repr]+""" not valid") FI; unsigned int(repr[:UPB repr-1], base) * base + pos - 1 FI
PROC int = (STRING repr, INT base)INT:
( repr[LWB repr]="-" | -unsigned int(repr[LWB repr + 1:], base) | unsigned int(repr, base) );
[]INT test = (-256, -255, -26, -25, 0, 25, 26, 255, 256); FOR index TO UPB test DO
INT k = test[index]; STRING s = base n(k,16); # returns the string 1a # INT i = int(s,16); # returns the integer 26 # print((k," => ", s, " => ", i, new line))
OD</lang> Output:
-256 => -100 => -256 -255 => -ff => -255 -26 => -1a => -26 -25 => -19 => -25 +0 => 0 => +0 +25 => 19 => +25 +26 => 1a => +26 +255 => ff => +255 +256 => 100 => +256
Libraries
As of February 2009 no open source libraries to do this task have been located.
C++
<lang cpp>#include <limits>
- include <string>
- 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;
}</lang>
Common Lisp
<lang lisp>(let ((*print-base* 16)
*read-base* 16)) (write-to-string 26) ; returns the string "1A" (read-from-string "1a") ; returns the integer 26
(write-to-string 26 :base 16) ; also "1A"</lang>
D
D standard library string module included functions to convert number to string at a radix. <lang d>module std.string; char[] toString(long value, uint radix); char[] toString(ulong value, uint radix);</lang> Implementation. <lang 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)) ;
}</lang>
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
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: <lang 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
}</lang>
for BigInteger's: <lang 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
}</lang>
JavaScript
<lang 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.</lang>
OCaml
<lang 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"</lang>
# basen_of_int 16 26 ;; - : string = "1a" # int_of_basen 16 "1a" ;; - : int = 26
A real base conversion example:
<lang ocaml>let to_base b v =
let rec to_base' a v = if v = 0 then a else to_base' (v mod b :: a) (v / b) in to_base' [] v
let from_base b ds =
List.fold_left (fun n k -> n * b + k) 0 ds
let to_alpha_digit n =
if n < 10 then char_of_int (n + int_of_char '0') else char_of_int (n + int_of_char 'a' - 10)
let to_alpha_digits ds =
let buf = Buffer.create (List.length ds) in List.iter (fun i -> Buffer.add_char buf (to_alpha_digit i)) ds; Buffer.contents buf
let from_alpha_digit c = match c with
'0'..'9' -> int_of_char c - int_of_char '0' | 'A'..'Z' -> int_of_char c - int_of_char 'A' + 10 | 'a'..'z' -> int_of_char c - int_of_char 'a' + 10
let from_alpha_digits s =
let result = ref [] in String.iter (fun c -> result := from_alpha_digit c :: !result) s; List.rev !result</lang>
Example:
# to_alpha_digits (to_base 16 42);; - : string = "2a" # from_base 16 (from_alpha_digits "2a");; - : int = 42
Perl
Perl has some built-in capabilites for various conversions between decimal, hexadecimal, octal, and binary, but not other bases. <lang perl>sub digitize
- Converts an integer to a single digit.
{my $i = shift; return $i < 10 ? $i : ('a' .. 'z')[$i - 10];}
sub undigitize
- 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;}</lang>
PHP
PHP has a base_convert() function that directly converts between strings of one base and strings of another base: <lang php>base_convert("26", 10, 16); // returns "1a"</lang>
If you want to convert a string to an integer, the intval() function optionally takes a base argument when given a string: <lang php>intval("1a", 16); // returns 26</lang>
To go the other way around, I guess you can use base_convert() again; I am unaware of a better way: <lang php>base_convert(26, 10, 16); // returns "1a"</lang>
In addition, there are specialized functions for converting certain bases: <lang 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</lang>
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
<lang 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</lang>
Ruby
<lang ruby>s = 26.to_s(16) # returns the string 1a i = '1a'.to_i(16) # returns the integer 26</lang>