logo CoolAJ86

Convert Decimal Strings to Hex with JS BigInts

Published 2018-12-12

With the introduction of native BigInts (also known as Big Nums or Arbirtrary-Precision Numbers), in JavaScript, it's now easy to convert from arbitrarily-large ints to hex (which is the gateway drug to typed arrays).

However, there are some caveats, particulary with negative numbers.

But first, let's tackle some of the more simple problems.

TL;DR:

For the impatient, this is what we'll be building up to:

function bnToHex(bn) {
  bn = BigInt(bn);

  var pos = true;
  if (bn < 0) {
    pos = false;
    bn = bitnot(bn);
  }

  var hex = bn.toString(16);
  if (hex.length % 2) { hex = '0' + hex; }

  if (pos && (0x80 & parseInt(hex.slice(0, 2), 16))) {
    hex = '00' + hex;
  }

  return hex;
}

function bitnot(bn) {
  bn = -bn;
  var bin = (bn).toString(2)
  var prefix = '';
  while (bin.length % 8) { bin = '0' + bin; }
  if ('1' === bin[0] && -1 !== bin.slice(1).indexOf('1')) {
    prefix = '11111111';
  }
  bin = bin.split('').map(function (i) {
    return '0' === i ? '1' : '0';
  }).join('');
  return BigInt('0b' + prefix + bin) + BigInt(1);
}

Convert BigInt Decimal to Hex

There are two ways to go about this:

  • Use the BigInt wrapper (which, much like Number, doesn't use new)
  • Use the literal BigInt syntax (postfixing a number with n)

Either way, you'll have to correct for the same types of problems that Number.prototype.toString(base) has always had.

For this demonstration I've selected a not-so-random random number:

// Literal syntax
1339673755198158349044581307228491520n.toString(16);

// BigInt wrapper
BigInt('1339673755198158349044581307228491520').toString(16);

// Same WRONG result
// '102030405060708090a0b0c0d0e0f00' WRONG!!!

Despite the fact that BigInt(str) requires prefixed strings (namely as 0x, 0o, 0b) in order to parse them correctly, it doesn't output the prefix (which is inconsistent, but okay).

What's not okay, however, is that it doesn't correctly pad the hex string to be parsable (and, more importantly, concatenateable).

That first problem (padding) is an easy fix:

function bnToHex(bn) {
  var base = 16;
  var hex = BigInt(bn).toString(base);
  if (hex.length % 2) {
    hex = '0' + hex;
  }
  return hex;
}

(the bn in bnToHex stands for "Big Number", after the "bnjs" tradition)

bnToHex('1339673755198158349044581307228491520');
// '0102030405060708090a0b0c0d0e0f00' Correct!!

Note the leading 0 that keeps the string length divisible by 2. That's a proper hex string.

Now, we could add the 0x prefix for pretty-printing if we wanted, but I find that hex is easier to work in than other formats (binary strings, TypedArrays, etc) and so I wouldn't - at least not at this stage.

Negative BigInt to Hex

This next problem really isn't any different than with normal Number-type numbers, but since we can use Arrays and TypedArrays for normal numbers there are other reasonable workarounds.

For this example we'll need two specially-paired complementary Integers:

  • The positive number 170892133397465074381480318756786823280n
  • The negative number -169390233523473389081894288674981388176n

(note that the negative number is one off from the positive number)

First we'll look at the output of the bnToHex function we just created:

bnToHex('170892133397465074381480318756786823280');
// '8090a0b0c0d0e0f00010203040506070' Looks true...

bnToHex('-169390233523473389081894288674981388176');
// '0-7f6f5f4f3f2f1f0fffefdfcfbfaf9f90' very, _very_ WRONG!

There are a lot of problems here, the least of which is the leading 0. A much bigger one is that that BigInt's toString() assigns a decimal - to denote negative rather than encoding it into the hex.

As you may know, in binary formats (hex, base64, and binary - of course) negative numbers are repsentented by having the first bit (the "high order bit") set to 1 (0x80 | i in hex).

Since there's no -0 (well, technically there is... but that's another topic entirely), the bits are also toggled in what's known as "two's compliment" (otherwise known as "bitwise not") which, unfortunately, isn't correctly implemented in JavaScript for BigInts (and takes some trickery even to make work with regular Numbers), so we have to implement it and update our bnToHex accordingly:

function bnToHex(bn) {
  bn = BigInt(bn);

  // I've noticed that for some operations BigInts can
  // only be compared to other BigInts (even small ones).
  // However, <, >, and == allow mix and match
  if (bn < 0) {
    bn = bitnot(bn);
  }

  var base = 16;
  var hex = bn.toString(base);
  if (hex.length % 2) {
    hex = '0' + hex;
  }
  return hex;
}

function bitnot(bn) {
  // JavaScript's bitwise not doesn't work on negative BigInts (bn = ~bn; // WRONG!)
  // so we manually implement our own two's compliment (flip bits, add one)
  bn = -bn;
  var bin = (bn).toString(2)
  var prefix = '';
  while (bin.length % 8) {
    bin = '0' + bin;
  }
  if ('1' === bin[0] && -1 !== bin.slice(1).indexOf('1')) {
    prefix = '11111111';
  }
  bin = bin.split('').map(function (i) {
    return '0' === i ? '1' : '0';
  }).join('');
  return BigInt('0b' + prefix + bin) + BigInt(1);
}

Let's try again:

bnToHex('170892133397465074381480318756786823280');
// '8090a0b0c0d0e0f00010203040506070' Good.

bnToHex('-169390233523473389081894288674981388176');
// '8090a0b0c0d0e0f00010203040506070' Good... Er... what!?

As you may notice, we get exactly the same result. We lose the ability to distinguish between positive and negative numbers!

Obviously, however, there is a way to store negative BigInts, otherwise the JavaScript engine wouldn't be able to distinguish between them either.

Positive vs Negative BigInt

In the long-standing tradition of BigInts, as it were, the historical way to solve this problem is to pad a positive number with 0 if (and only if) it's ambiguous (meaning that the high-order bit is set).

All we need to do is keep track of the original sign and then pad appropriately:

function bnToHex(bn) {
  var pos = true;
  bn = BigInt(bn);

  // I've noticed that for some operations BigInts can
  // only be compared to other BigInts (even small ones).
  // However, <, >, and == allow mix and match
  if (bn < 0) {
    pos = false;
    bn = bitnot(bn);
  }

  var base = 16;
  var hex = bn.toString(base);
  if (hex.length % 2) {
    hex = '0' + hex;
  }

  // Check the high byte _after_ proper hex padding
  var highbyte = parseInt(hex.slice(0, 2), 16);
  var highbit = (0x80 & highbyte);

  if (pos && highbit) {
    // A 32-byte positive integer _may_ be
    // represented in memory as 33 bytes if needed
    hex = '00' + hex;
  }

  return hex;
}

function bitnot(bn) {
  // JavaScript's bitwise not doesn't work on negative BigInts (bn = ~bn; // WRONG!)
  // so we manually implement our own two's compliment (flip bits, add one)
  bn = -bn;
  var bin = (bn).toString(2)
  var prefix = '';
  while (bin.length % 8) {
    bin = '0' + bin;
  }
  if ('1' === bin[0] && -1 !== bin.slice(1).indexOf('1')) {
    prefix = '11111111';
  }
  bin = bin.split('').map(function (i) {
    return '0' === i ? '1' : '0';
  }).join('');
  return BigInt('0b' + prefix + bin) + BigInt(1);
}

And one last round of checks...

We'll use our special pair again:

bnToHex('170892133397465074381480318756786823280');
// '008090a0b0c0d0e0f00010203040506070' Perfect!

bnToHex('-169390233523473389081894288674981388176');
// '8090a0b0c0d0e0f00010203040506070'

We could also go a lot simpler and try smaller numbers:

//
// Positives
//
bnToHex(0)    // '00'
bnToHex(1)    // '01'
bnToHex(127)  // '7f'
bnToHex(128)  // '0080'
bnToHex(129)  // '0081'

//
// Negatives
//
bnToHex(-129) // 'ff7f'
bnToHex(-128) // '80'
bnToHex(-127) // '81'
bnToHex(-1)   // 'ff'

Problems ~both~ all Ways

The same problems exist going from Hex to Decimal (and with regular Number-type numbers).

If you found this useful, and you're interested in solving related problems, take a look at these as well:

References:


By AJ ONeal

If you loved this and want more like it, sign up!


Did I make your day?
Buy me a coffeeBuy me a coffee  

(you can learn about the bigger picture I'm working towards on my patreon page )