1

I recently had to do a codility test. The question itself was reasonably easy. take a string of numbers and +, * loop through it, if the character is a number, add it to a stack, if its an operation pop two items off the stack, perform the operation and put the result back on the stack.

The tricky small print however, specifed that the stack store values as 12 bit unsigned ints.

This gave me a lot of trouble I tried bitwise shifting back and forth but got negative numbers and eventualy I had to just do % 4096 before I ran out of time.

Also I realised that really I might have to create a special 12bit add and multiply operators, or would I be ok just converting a 16bit result?

Have I missed a trick?

What is the best way to emulate 12 bit uint math in c#?

5

A simple operation like

  PushToStack(uint32 value)
  {
     _stack.Add(value % 4096);
  }

should be sufficient, as long as you use this function exclusively for pushing values to your stack.

Note that (a+b)%n == (a%n + b%n)%n and (a*b)%n == ((a%n) * (b%n))%n for a and b >=0 and n>0.

Furthermore, when you add or multiply two values from the stack, the input values are already 12 bit, so the output has at maximum 24 bit, so you can do this using unsigned or signed 32bit arithmetics without getting an overflow. Thus there will be never any negative value occur, and any kind of bit shifting is unnecessary. And as soon as the result is pushed to the stack again, it becomes 12 bits again.

  • as long as you only use positive ints + and *, could you just convert once at the end? – Ewan May 30 '15 at 13:24
  • @Ewan: do you mean by "once at the end" something different than what I wrote above? – Doc Brown May 30 '15 at 17:11
  • It looks like your equivilances mean that you could do (((a+b)*c)+d....etc) %n so you could add to the stack as uint32 and convert the result of the calc to uint12 and get the same result as converting to uint12 after each step – Ewan May 30 '15 at 18:40
  • @Ewan: for an arbitrary n, this would be only safe as long as you do not get any intermediate overflow. But if n is a power of 2 as in your case, this will indeed work, since (a%(2^32))%(2^m) == a%(2^m) for m<=32. Note that in your question you only required one multiplication or one addition before the result is pushed back on the stack, the case you constructed in your comment is a different question. – Doc Brown May 30 '15 at 19:32
  • ahh well I ask because on reviewing my code after the test I found I missed the conversion on the plus case. So I am interested in the maths because it will effect the number of cases in which my code fails. It seems from what you are saying as long as the final operation is a multiply my code will return the correct result! – Ewan May 30 '15 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.