Increment char in byte array

Question

I'm prefilling a byte array with:

 private static byte[] idBuffer = ASCIIEncoding.Default.GetBytes("A" + DateTime.Now.ToString("yy") + DateTime.Now.DayOfYear + "0000001");

The "0000001" part in the byte array is my ID part that I would like to increment with ASCII characters 0-1A-S every time I call the "Increment" method.

For example, increment sequence samples would be:

000000S
...
00000S0
00000S1
...
00000SS
...
0000S00
...
0000S99
0000S9A
etc.

I'm having some trouble coming up with the correct algorithm/state machine to increment the characters correctly.

Right now I prefill a char table:

private static byte[] charCodes = new byte[] { 49, 50, 51, 52, 53, 54, 55, 56, 57, 65, 66, 67, 68, 69, 70, 80, 81, 82, 83};

and my crude attempt at the state machine for this but it only gets me to the 2nd position:

if (idBuffer[bufPosition] < 83)
{
    idBuffer[bufPosition] = charCodes[charCodePosition];
    charCodePosition++;
}
else
{
    if (idBuffer[bufPosition - 1] == 48)
    {
        for (int i = bufPosition; i < idBuffer.Length; i++)
            idBuffer[i] = 48;

        idBuffer[bufPosition - 1] = charCodes[charCodePosition2];
        charCodePosition2++;
    }
    else
    {
        charCodePosition2++;
        idBuffer[bufPosition - 1] = charCodes[charCodePosition2];
    }

    charCodePosition = 0;
}

I'm sure there is a much more elegant way to do this that I can't think of - Ideally if someone knows how to do this with unsafe code/pointers, even better!

There are probably hundreds of questions "how to convert number to/from arbitrary base" (i.e. http://stackoverflow.com/questions/923771/quickest-way-to-convert-a-base-10-number-to-any-base-in-net) ... — Alexei Levenkov, Aug 28 '15 at 01:32
I'm not looking to convert, I want to increment the bytes in the array to produce the desired outcome - I looked through search results in your link and couldn't find anything that is applicable — TJF, Aug 28 '15 at 01:45
Sorry, missed the last part - you are looking for more complicated solution. I think you still can find inspiration in questions talking about math operations in base other than 10... If I'd need to do BaseX math I'd convert "digits" values to 0-X range first (with reverse lookup map), perform operation and than transform back... But it would not be complicated enough. — Alexei Levenkov, Aug 28 '15 at 01:52
Try this : var results = Encoding.UTF8.GetChars((new byte[35]).Select((x,i) => (byte)(i + 49)).ToArray()); — jdweng, Aug 28 '15 at 01:52
@jdweng not quite sure how this is relevant to the question? — TJF, Aug 28 '15 at 01:56
This is the correct answer. No state machine. char[] results = Encoding.UTF8.GetChars((new byte[19]).Select((x, i) => (i <= 8) ? (byte)(i + 49) : (i <= 14) ? (byte)(i + 56) : (byte)(i + 65)).ToArray()); Actually i is the state variable. — jdweng, Aug 28 '15 at 02:09
@jdweng: That creates a mapping to the chosen alphabet, but it does not implement the increment which is the point of the question. — Ben Voigt, Aug 28 '15 at 02:34
Increment can easily be implemented by using GetIndexOf() for the current character and then getting next index. — jdweng, Aug 28 '15 at 04:43

score 3 · Accepted Answer · answered Aug 28 '15 at 01:55

3

It's actually pretty simple:

Start with the last element.
Add one.
If you now have '0'+10 (58), adjust it to 'A' (65).
If you have anything other than 'T' (too lazy to look up ASCII code) you are done.
Adjust to '0' (48).
Carry by moving left one element and repeating from step 2 onward.

answered Aug 28 '15 at 01:55

Ben Voigt

277,958
43
419
720

for cooler looking code (my understanding for reason to prefer unsafe) steps 2 - 5 should be performed with lookup table (char -> {incremented char, carry}). – Alexei Levenkov Aug 28 '15 at 01:59
Ben, if I understand your solution correctly, it only increments the next position but doesn't reset the prior positions (e.g. I'd want output to be 000S ... 0010 ... 0011 ... 001S ... 0020 .. etc.) – TJF Aug 28 '15 at 02:01
@AlexeiLevenkov: You don't need "unsafe" to use a lookup table, and a lookup table won't do step 4. Maybe you meant 2,3,5? Anyway, it's unlikely that a lookup table will be faster and it certainly isn't as easy to see that it works. – Ben Voigt Aug 28 '15 at 02:01
@TJF: Step 5 takes care of that. – Ben Voigt Aug 28 '15 at 02:01
@BenVoigt Sorry but I don't follow - I get that 5) sets current position to 0 and then moves left one position. But that doesn't take care of going back to the "right" to start incrementing after you moved up one position (e.g. after 00SSS should follow 01000, 01001 ... 01SSS) – TJF Aug 28 '15 at 02:11
@TJF: You follow this algorithm completely each time you add 1. When you want to add one again, start at step 1 (adjusting the rightmost place) – Ben Voigt Aug 28 '15 at 02:12
@BenVoigt I've posted my suggestion as answer (not really serious suggestion, but data driven code is fascinating sometimes :) ) – Alexei Levenkov Aug 28 '15 at 02:19
@BenVoigt good point about step 4 - but for fixed length number you can go over all digits. – Alexei Levenkov Aug 28 '15 at 02:23
@BenVoigt you're right, got it now, tyvm, this does exactly what I'm looking for! – TJF Aug 28 '15 at 02:27

score 1 · Answer 2 · edited May 23 '17 at 11:58

Based on Ben Voigt answer, the fact you want cool (assuming that the goal of preferring unsafe) code and fixed size of number you can unroll whole code into simple state machine:

{number-to-add, char} -> {incremented char, carry}

Approximate code for 'A'-'C' as 0,1,3. may be slightly simplified if tables merged into one (i.e. combining char and index into single uint value with bit-shifts)

char[2,256] incrementedChar = new char[2,256]{
      {...64 0..., 'A', 'B', 'C', more 0 }, // A+0 = A, 
      {...64 0..., 'B', 'C', 'A', more 0 }};// A+1 = B, .., C+1 = A+carry

int[2,256] carryTable = new int[2,256]{
      {...64 0..., 0, 0, 0, more 0 }, // adding 0 never carry 
      {...64 0..., 0, 0, 1, more 0 }};// carry when adding 1 to `C`

var chars = new[] {'A','A', 'A', 'C'};
int carry = 1; // adding 1 to the last digit
char current;
// unrolled loop from end to start. Adjust indexes if it is not in the beginning.

current = incrementedChar[carry, chars[3]];
carry = carryTable[carry, chars[3]];
chars[3] = current;

current = incrementedChar[carry, chars[2]];
carry = carryTable[carry, chars[2]];
chars[2] = current;

current = incrementedChar[carry, chars[1]];
carry = carryTable[carry, chars[1]];
chars[1] = current;

current = incrementedChar[carry, chars[0]];
carry = carryTable[carry, chars[0]];
chars[0] = current;

The idea isn't bad (and doesn't require `unsafe` code), but the implementation is a total failure. You're adding "1111111" to the number, instead of adding "0000001". (And totally ignored the alphabet in the question, which uses both decimal digits and letters, although that's easy for a lookup table to deal with) — Ben Voigt, Aug 28 '15 at 02:24
@BenVoigt good point - was fixing up table at the same time. Full table would not fit into answer/less readable (but the only tricky part is 9->A - should be doable)... — Alexei Levenkov, Aug 28 '15 at 02:28
Looks like a correct fix, with one problem. You're doing the lookup into `carryTable` using the new value of `current` instead of the incoming value. Note that the carry rule can also be written as "carry when adding one creates '0' (or in your table, 'A')" — Ben Voigt, Aug 28 '15 at 02:29
@BenVoigt hand-unrolling loops turned out to be harder than I though :) — Alexei Levenkov, Aug 28 '15 at 02:32

Increment char in byte array

2 Answers2