开发者

Fastest way to convert a number to radix 64 in JavaScript?

In JavaScript you can convert a number to a string representation with a specific radix as follows:

(12345).toString(36) // "9ix"

...and you can convert it back to a regular number like this:

parseInt("9ix", 36) // 12345

36 is the highest radix you can specify. It apparently uses the characters 0-9 and a-z for the digits (36 total).

My question: what's the fastest way to convert a number to a base 64 representation (for example, using A-Z, and - and _ for the extra 28 digits)?


Update: Four people have posted responses saying this question is duplicated, or that I'm looking for Base64. I'm not.

"Base64" is a way of encoding binary data in a simple ASCII character set, to make it safe f开发者_运维知识库or transfer over networks etc. (so that text-only systems won't garble the binary).

That's not what I'm asking about. I'm asking about converting numbers to a radix 64 string representation. (JavaScript's toString(radix) does this automatically for any radix up to 36; I need a custom function to get radix 64.)


Update 2: Here are some input & output examples...

0   → "0"
1   → "1"
9   → "9"
10  → "a"
35  → "z"
61  → "Z"
62  → "-"
63  → "_"
64  → "10"
65  → "11"
128 → "20"
etc.


Here is a sketch for a solution for NUMBERS (not arrays of bytes :)

only for positive numbers, ignores fractional parts, and not really tested -- just a sketch!

Base64 = {

    _Rixits :
//   0       8       16      24      32      40      48      56     63
//   v       v       v       v       v       v       v       v      v
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/",
    // You have the freedom, here, to choose the glyphs you want for 
    // representing your base-64 numbers. The ASCII encoding guys usually
    // choose a set of glyphs beginning with ABCD..., but, looking at
    // your update #2, I deduce that you want glyphs beginning with 
    // 0123..., which is a fine choice and aligns the first ten numbers
    // in base 64 with the first ten numbers in decimal.

    // This cannot handle negative numbers and only works on the 
    //     integer part, discarding the fractional part.
    // Doing better means deciding on whether you're just representing
    // the subset of javascript numbers of twos-complement 32-bit integers 
    // or going with base-64 representations for the bit pattern of the
    // underlying IEEE floating-point number, or representing the mantissae
    // and exponents separately, or some other possibility. For now, bail
    fromNumber : function(number) {
        if (isNaN(Number(number)) || number === null ||
            number === Number.POSITIVE_INFINITY)
            throw "The input is not valid";
        if (number < 0)
            throw "Can't represent negative numbers now";

        var rixit; // like 'digit', only in some non-decimal radix 
        var residual = Math.floor(number);
        var result = '';
        while (true) {
            rixit = residual % 64
            // console.log("rixit : " + rixit);
            // console.log("result before : " + result);
            result = this._Rixits.charAt(rixit) + result;
            // console.log("result after : " + result);
            // console.log("residual before : " + residual);
            residual = Math.floor(residual / 64);
            // console.log("residual after : " + residual);

            if (residual == 0)
                break;
            }
        return result;
    },

    toNumber : function(rixits) {
        var result = 0;
        // console.log("rixits : " + rixits);
        // console.log("rixits.split('') : " + rixits.split(''));
        rixits = rixits.split('');
        for (var e = 0; e < rixits.length; e++) {
            // console.log("_Rixits.indexOf(" + rixits[e] + ") : " + 
                // this._Rixits.indexOf(rixits[e]));
            // console.log("result before : " + result);
            result = (result * 64) + this._Rixits.indexOf(rixits[e]);
            // console.log("result after : " + result);
        }
        return result;
    }
}

UPDATE: Here's some (very lightweight) testing of the above, for running in NodeJs where you have console.log.

function testBase64(x) {
    console.log("My number is " + x);
    var g = Base64.fromNumber(x);
    console.log("My base-64 representation is " + g);
    var h = Base64.toNumber(g);
    console.log("Returning from base-64, I get " + h);
    if (h !== Math.floor(x))
        throw "TEST FAILED";
}

testBase64(0);
try {
    testBase64(-1);
    }
catch (err) {
    console.log("caught >>>>>>  " + err);
    }
try {
    testBase64(undefined);
    }
catch (err) {
    console.log("caught >>>>>>  " + err);
    }
try {
    testBase64(null);
    }
catch (err) {
    console.log("caught >>>>>>  " + err);
    }
try {
    testBase64(Number.NaN);
    }
catch (err) {
    console.log("caught >>>>>>  " + err);
    }
try {
    testBase64(Number.POSITIVE_INFINITY);
    }
catch (err) {
    console.log("caught >>>>>>  " + err);
    }
try {
    testBase64(Number.NEGATIVE_INFINITY);
    }
catch (err) {
    console.log("caught >>>>>>  " + err);
    }

for(i=0; i<100; i++)
    testBase64(Math.random()*1e14);


Here's a version just for 32 bit ints, that is, any number between -2147483648 and 2147483647 (inclusive).

I modified the version in the top answer by Reb Cabin. This should be quite a bit faster because it uses bit operations and lookup tables.

Base64 = (function () {
    var digitsStr = 
    //   0       8       16      24      32      40      48      56     63
    //   v       v       v       v       v       v       v       v      v
        "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+-";
    var digits = digitsStr.split('');
    var digitsMap = {};
    for (var i = 0; i < digits.length; i++) {
        digitsMap[digits[i]] = i;
    }
    return {
        fromInt: function(int32) {
            var result = '';
            while (true) {
                result = digits[int32 & 0x3f] + result;
                int32 >>>= 6;
                if (int32 === 0)
                    break;
            }
            return result;
        },
        toInt: function(digitsStr) {
            var result = 0;
            var digits = digitsStr.split('');
            for (var i = 0; i < digits.length; i++) {
                result = (result << 6) + digitsMap[digits[i]];
            }
            return result;
        }
    };
})();

For example,

Base64.fromInt(-2147483648); // gives "200000"
Base64.toInt("200000"); // gives -2147483648


I think this question is missing a short solution.

const digit="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_";
toB64=x=>x.toString(2).split(/(?=(?:.{6})+(?!.))/g).map(v=>digit[parseInt(v,2)]).join("")
fromB64=x=>x.split("").reduce((s,v)=>s*64+digit.indexOf(v),0)

Works for all integers between 0 and Number.MAX_SAFE_INTEGER.


Extremely fast implementation for all values of javascript safe integers range (from -9007199254740991 to 9007199254740991):

const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';

// binary to string lookup table
const b2s = alphabet.split('');

// string to binary lookup table
// 123 == 'z'.charCodeAt(0) + 1
const s2b = new Array(123);
for (let i = 0; i < alphabet.length; i++) {
  s2b[alphabet.charCodeAt(i)] = i;
}

// number to base64
const ntob = (number) => {
  if (number < 0) return `-${ntob(-number)}`;

  let lo = number >>> 0;
  let hi = (number / 4294967296) >>> 0;

  let right = '';
  while (hi > 0) {
    right = b2s[0x3f & lo] + right;
    lo >>>= 6;
    lo |= (0x3f & hi) << 26;
    hi >>>= 6;
  }

  let left = '';
  do {
    left = b2s[0x3f & lo] + left;
    lo >>>= 6;
  } while (lo > 0);

  return left + right;
};

// base64 to number
const bton = (base64) => {
  let number = 0;
  const sign = base64.charAt(0) === '-' ? 1 : 0;

  for (let i = sign; i < base64.length; i++) {
    number = number * 64 + s2b[base64.charCodeAt(i)];
  }

  return sign ? -number : number;
};

npm: number-to-base64

Perfomance comparison: https://jsperf.com/number-to-base64-encoding


Here's a different take

function base64(value) {
  if (typeof(value) === 'number') {
    return base64.getChars(value, '');
  }

  if (typeof(value) === 'string') {
    if (value === '') { return NaN; }
    return value.split('').reverse().reduce(function(prev, cur, i) {
      return prev + base64.chars.indexOf(cur) * Math.pow(64, i);
    }, 0);
  }
}

base64.chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_";

base64.getChars = function(num, res) {
  var mod = num % 64,
      remaining = Math.floor(num / 64),
      chars = base64.chars.charAt(mod) + res;

  if (remaining <= 0) { return chars; }
  return base64.getChars(remaining, chars);
};


I was looking for a solution to the same problem, but for ActionScript (AS3), and it was evident that many persons confuse Base64 encode with 'numbers in base 64' (radix 64).

The vast majority of sites offer solutions for 'computational cryptography' and not mathematics. As solutions, this are not useful for the conversion that we needed.

Prior to this consultation, and knew the methods toString (radix) and parseInt (radix), I was worked with Hex numbers (radix 16) in both colors, and other features.

However, neither in AS3 or JS there exists a numerical method for transformations to and from radix 64.

Before coming to this site I found:

  1. In various online calculators, radix 64 not starting from scratch, but A.
    Eg: convertix.com & alfredo4570.net
  2. In radix 64 is formed by the following sets of ordered characters: AZ, az, 0-9, + and / (these I have defined a constant: STR64)

To avoid confusion with cryptographic methods, the methods to be used are based on well-known names:

  • toString / to64String
  • parseInt / to64Parse

The code was be wrote in AS3, but is very clear (common with JS).

NOTE: Recommended use with number under: 1 * 1016

At the end, an example and results of operations are included.

const STR64:Array = ('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/').split( '' );

// TRANSFORM NUMBERS BETWEEN radix 10 AND radix 64
/** Methods based on answers shared in:
* @url   http://stackoverflow.com/questions/6213227/fastest-way-to-convert-a-number-to-radix-64-in-javascript
*/

// METHODS 
/** to64String: Method to transform a radix 10 number to radix 64 number (as string)
* @param input   Number for transform to radix 64 (as String)
* @param current String data (don't needed in request)
* @return String Number in radix 64 as String;
*
* @based http://stackoverflow.com/users/383780/monocle
* @based base64( Method for number to string - NOT string part )
*/
function to64String( input:Number, current:String = '' ):String
{
    if ( input < 0 && current.length == 0 ){
        input = input * - 1;
    }
    var modify:Number = input % 64;
    var remain:Number = Math.floor( input / 64 );
    var result:String = STR64[ modify ] + current;
    return ( remain <= 0 ) ? result : to64String( remain, result );
}

/** to64Parse: Method for transform a number in radix 64 (as string) in radix 10 number
* @param input   Number in radix 64 (as String) to transform in radix 10
* @return Number in radix 10
*
* @based http://stackoverflow.com/users/520997/reb-cabin
* @based Base64.toNumber( Method for string to number )
*/
function to64Parse ( input:String ):Number
{
    var result:Number = 0;
    var toProc:Array  = input.split( '' );
    var e:String;
    for ( e in toProc ){
        result = ( result * 64 ) + STR64.indexOf( toProc[ e ] );
    }
    return result;
}

// TEST
var i:int = 0;
var max:Number = 1000000000000;
var min:Number = 0;
for ( i == 0; i < 20; i++ ){
    var num:Number = ( Math.ceil( Math.random() * ( max - min + 1 ) ) + min );
    var s64:String = to64String( num );
    var ret:Number = to64Parse ( s64 );
    trace( i + '\t# ' + num + '\t' + s64 + '\t' + ret + '\t' + ( ret == num ) )
}

// TEST RESULT
/*
0   # 808936734685  LxYYv/d 808936734685    true
1   # 931332556532  NjXvwb0 931332556532    true
2   # 336368837395  E5RJSMT 336368837395    true
3   # 862123347820  Mi6jk9s 862123347820    true
4   # 174279278611  CiT2sAT 174279278611    true
5   # 279361353722  EELO/f6 279361353722    true
6   # 435602995568  GVr9jlw 435602995568    true
7   # 547163526063  H9lfNOv 547163526063    true
8   # 188017380425  CvGtYxJ 188017380425    true
9   # 720098771622  KepO0Km 720098771622    true
10  # 408089106903  F8EAZnX 408089106903    true
11  # 293941423763  ERwRi6T 293941423763    true
12  # 383302396164  Fk+mmkE 383302396164    true
13  # 695998940618  KIMxQXK 695998940618    true
14  # 584515331314  IgX1CTy 584515331314    true
15  # 528965753970  Hso0Nxy 528965753970    true
16  # 5324317143    E9WqHX  5324317143      true
17  # 772389841267  LPWBalz 772389841267    true
18  # 954212692102  N4rgjCG 954212692102    true
19  # 867031893694  MnfIMa+ 867031893694    true
*/


I wrote an npm module for this type of operation, power-radix, that will help you. You can convert any number from any radix to any radix in a user-defined character encoding.

For example:

var base = ['Q', 'W', 'E', 'R', 'T', 'Y', 'I', 'O', 'U'];
new PowerRadix([1, 0], 10).toArray(base); // ['W', 'Q'] 
new PowerRadix('10', 10).toArray(base);   // ['W', 'Q'] 
new PowerRadix(10, 10).toArray(base);     // ['W', 'Q'] 

new PowerRadix([1, 0], 10).toString(base); // "WQ" 
new PowerRadix('10', 10).toString(base);   // "WQ" 
new PowerRadix(10, 10).toString(base);     // "WQ"

The module also supports custom source radix encodings.

new PowerRadix('ba', ['a', 'b']); // base 2 source radix, uses 'a' = 0 & 'b' = 1 character set.
new PowerRadix('ba', ['a', 'b']).toString(10); // returns "2"


The following implementation converts positive, negative and non-integer numbers to an arbitrary base. The conversion back to decimal is easily implemented in a similar fashion:

function toAnyBase(num, base) {
  if (!Number.isInteger(base) || base < 2) throw new RangeError("toAnyBase() base argument must be an integer >= 2");
  if (!Number.isFinite(num)) return num.toString();
  if (num < 0) return "-" + toAnyBase(-num, base);
  
  const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ#_",
        inv_base = 1 / base;
  
  var result = "",
      residual;
  
  // Integer part:
  residual = Math.trunc(num);
  do {
    result = digits.charAt(residual % base) + result;
    residual = Math.trunc(residual * inv_base); 
  } while (residual != 0);
  
  // Fractional part:
  residual = num % 1;
  if (residual != 0) {
    result += ".";
    var max = 1000;
    do {
      residual *= base;
      result += digits.charAt(Math.trunc(residual));
      residual %= 1;
    } while (residual != 0 && --max != 0);
  }

  return result;
}

console.log(toAnyBase(  64, 64)); // "10"
console.log(toAnyBase(-1.5, 64)); // "-1.w"


If you are using NodeJS, you can use the following code:

var base64 = Buffer.from([i>>24,i>>16,i>>8,i]).toString('base64').substr(0,6);


I was after the same solution and I think I've generalized what this person is after with as few lines as possible in basic Javascript. Should work for any positive integer, and endex can be whatever length you want for whatever base you want as long as all the characters are unique.

var endex = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_";
function encode(intcode){
    if(intcode < endex.length){
        return endex[intcode];
    }else{
        return encode(Math.floor(intcode/endex.length)) + endex[intcode%endex.length];
    }
}
function decode(charcode){
    if(charcode.length < 2){
        return endex.indexOf(charcode);
    }else{
        return (decode(charcode.slice(0, -1)) * endex.length) + endex.indexOf(charcode.slice(-1));
    }
}


Well, you could just use any Javascript Base64 library: perhaps this question answers it?

EDIT: Binary data is essentially just a sequence of bytes. If you assume the bytes represent a single number you can represent the sequence of bytes as a base 64 string. Decode them and do some trivial math on the bytes to get a number. Convert the number to a sequence of bytes and encode to get a string. Seems quite reasonable, unless you are somehow invested in the specific characters used in the String.


I know the question is Java Script, but here is a solution in java, you probably can easily convert it.

private String toShortString(BigInteger value, String language) {
    StringBuilder stringBuilder = new StringBuilder();
    BigInteger length = BigInteger.valueOf(language.length());
    while (value.compareTo(BigInteger.ZERO) > 0){
        int index = value.mod(length).intValue();
        stringBuilder.append(language.charAt(index));
        value = value.divide(length);
    }
    return stringBuilder.reverse().toString();
}

Usage

    BigInteger value = BigInteger.valueOf(2).pow(128); 
    System.out.println(value);
    System.out.println(value.toString(16));
    System.out.println(toShortString(value, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()-=_+"));

Output

340282366920938463463374607431768211456
100000000000000000000000000000000
8hS#phQaCO3849pE+^El4

If you convert this to Java Script please edit this question and add it below.


I've made some enhancements in @jahooma and @Reb.Cabin

1- BigInt: The reason is simple, when you are using radix64 the numbers will grow too fast and will overflow javascript primitive int capacity.

2- Better alphabet: I took liberty to change the radix64 alphabet to URL friendly one, also I sorted it lexicographically, this way if you sort alphabetically a list of strings representing radix64 numbers, the result will be the same as if you had converted the radix64 to decimal then sorted then converted back (might sound obvious but the current accepted answer wont work with)

Base64 = (function () {

const alphabet = '-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz';

const base64Values = { '0': 1n, '1': 2n, '2': 3n, '3': 4n, '4': 5n, '5': 6n, '6': 7n, '7': 8n, '8': 9n, '9': 10n, '-': 0n, 'A': 11n, 'B': 12n, 'C': 13n, 'D': 14n, 'E': 15n, 'F': 16n, 'G': 17n, 'H': 18n, 'I': 19n, 'J': 20n, 'K': 21n, 'L': 22n, 'M': 23n, 'N': 24n, 'O': 25n, 'P': 26n, 'Q': 27n, 'R': 28n, 'S': 29n, 'T': 30n, 'U': 31n, 'V': 32n, 'W': 33n, 'X': 34n, 'Y': 35n, 'Z': 36n, '_': 37n, 'a': 38n, 'b': 39n, 'c': 40n, 'd': 41n, 'e': 42n, 'f': 43n, 'g': 44n, 'h': 45n, 'i': 46n, 'j': 47n, 'k': 48n, 'l': 49n, 'm': 50n, 'n': 51n, 'o': 52n, 'p': 53n, 'q': 54n, 'r': 55n, 's': 56n, 't': 57n, 'u': 58n, 'v': 59n, 'w': 60n, 'x': 61n, 'y': 62n, 'z': 63n};

return {

  
    fromInt: function(bigNum) {
        if(typeof bigNum != 'bigint')
          bigNum = BigInt(bigNum);
      

             let len = 1+bigNum.toString().length/2|0;
    const result = Array(len); //to calculate the exact size of the output some  //to calculate the exact size of the output some complex log calcs are needed, I use this to get an approximation
        do {
            result[--len] = alphabet[(bigNum & 0x3fn)];
            bigNum >>= 6n;
        } while (bigNum>0)
        return result.join('');
    },
    toInt: function(input) {
      if(!input)
        return 0;

        var result = 0n;
         
        for (var i = 0n; i < input.length; i++) 
            result = (result << 6n) + base64Values[input[i]];
        

        return result;
    }
};
})();


I translated Ilya Gazman's Java code to JavaScript:

function toShortString(value, language) {
    var string = "";
    var length = language.length;
    while (value > 0) {
        var index = value % length;
        string += language.charAt(index);
        value = value / length;
    }
    return string.split("").reverse().join("").replace(/^0+/g, "");
}

var base64Language = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+/";

console.log(toShortString(138, base64Language)); //> 2a


In a mozilla or webkit browser you can use btoa() and atob() to encode and decode base64.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜