-1

I know you can just use an integer and count up and down then convert to a hexadecimal string, but I need to use integers larger than the max value (up to 0xffffffffffffffffffff or 1208925819614629174706175).

What would be the most efficient way to count up to these types of numbers?

phuclv
  • 37,963
  • 15
  • 156
  • 475
G Smith
  • 53
  • 1
  • 9

2 Answers2

1

If you want an 80-bit counter then you can create a structure to store 80 bits then add from the low part to the high part (with carry)

class Counter {
    private long low;      // 64 low bits of the counter
    private short high;    // 16 high bits

    public void inc() {
        low++;
        if (low == 0)  // wrapped around, which means there's a carry
            high++;    // add the carry to the high part
    }

    public String toHex() {
        return String.format("%04X%016X", high & 0xffff, low);
    }
}

If you don't want leading 0's then change the toHex function like this

if (low == 0)
    return Long.toHexString(low);
else
    return Integer.toHexString(high & 0xffff) + String.format("%016X", low);

However, you can't count up to that maximum value in your whole life, because to count only 64-bit values you have to spend ~9223372036 seconds or 292 years, assuming your CPU can count 2 billion values in a second while ignore the loop and all other things needed to be done by the OS. Adding 16 more bits and you'll need more than 19 million years to count up all.

phuclv
  • 37,963
  • 15
  • 156
  • 475
  • Very bad naming conventions. [Java naming conventions](https://stackoverflow.com/documentation/java/2697/oracle-official-code-standard/9031/naming-conventions#t=201706181648276636093) are for class names to start with uppercase letter, and field names to start with lowercase letter. You're doing the exact opposite. – Andreas Jun 18 '17 at 16:48
  • @Andreas I'm not familiar with Java and Java naming convention. Just fixed it – phuclv Jun 18 '17 at 16:58
  • `toHex()` is incorrect. Calling `toHex()` before first call to `inc()` will return `00`, not `0`. Calling `toHex()` right before first carry-over will return `0ffffffffffffffff`. Calling `inc()`, then`toHex()` will then return `10`, which is certainly not correct. – Andreas Jun 18 '17 at 17:09
  • @Andreas I didn't know that `toHexString` doesn't pad the output with leading zeros – phuclv Jun 19 '17 at 03:05
0

The fastest way would be probably keeping a char[] and counting with it. For every operation, you only need to change the last digit in 90% cases. In 9% of cases you need to change two digits, in 0.9% of cases wto, etc.

The conversion to String is just a simple array copy, and so is appending to a StringBuilder.

Note that such an optimization is most probably a non-sense. Go with a BigInteger, save yourself the hassle and the bugs, and report back if it's too slow.

maaartinus
  • 44,714
  • 32
  • 161
  • 320
  • Storing in base 2^64 and you also need to change only the last digit which is roughly 18 digits in decimal. That'll be much slower. Anyway this counter is useless because it can hardly overflow – phuclv Jun 21 '17 at 02:22