11

For unsigned int x, is it possible to calculate x % 255 (or 2^n - 1 in general) using only the following operators (plus no loop, branch or function call)?

!, ~, &, ^, |, +, <<, >>.

3
  • Almost certainly no - the only tricks for this kind of thing tend to be for powers of 2. Essentially you need to implement an integer division algo - I guess you could do something with an unrolled loop but it might still need conditionals and it would be ugly and inefficient.
    – Paul R
    Oct 10, 2011 at 7:28
  • 2
    @Paul R: While it's true that these kind of things are usually restricted to powers-of-two. This is one of the not-so-obvious exceptions.
    – Mysticial
    Oct 10, 2011 at 7:38
  • If this is homework, please tag it as "homework". If it isn't, why the arbitrary restrictions? Oct 12, 2011 at 2:27

3 Answers 3

10

Yes, it's possible. For 255, it can be done as follows:

unsigned int x = 4023156861;

x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);

//  At this point, x will be in the range: 0 <= x < 256.
//  If the answer 0, x could potentially be 255 which is not fully reduced.

//  Here's an ugly way of implementing: if (x == 255) x -= 255;
//  (See comments for a simpler version by Paul R.)
unsigned int t = (x + 1) >> 8;
t = !t + 0xffffffff;
t &= 255;
x += ~t + 1;

// x = 186

This will work if unsigned int is a 32-bit integer.

EDIT: The pattern should be obvious enough to see how this can be generalized to 2^n - 1. You just have to figure out how many iterations are needed. For n = 8 and a 32-bit integer, 4 iterations should be enough.

EDIT 2:

Here's a slightly more optimized version combined with Paul R.'s conditional subtract code:

unsigned int x = 4023156861;

x = (x & 65535) + (x >> 16);     //  Reduce to 17 bits
x = (x & 255) + (x >> 8);        //  Reduce to 9 bits
x = (x & 255) + (x >> 8);        //  Reduce to 8 bits
x = (x + ((x + 1) >> 8)) & 255;  //  Reduce to < 255
4
  • Looks good but seems to fail in some cases, e.g. x = 86817555 ? I ran 1000000 random test cases through the above code and got good = 996132, bad = 3868, so evidently something is not quite right ? (FWIW the cases that fail seem to give 255 when the result should be 0.)
    – Paul R
    Oct 10, 2011 at 8:21
  • @Paul R: Good catch. I missed this corner case. One more step at the end will needed to reduce 255 to 0. Lemme fix.
    – Mysticial
    Oct 10, 2011 at 8:23
  • 1
    Great - that works now - note that you can probably simplify the last part to this: x = (x + ((x + 1) >> 8)) & 255;` - that's only 4 logical/arithmetic operations versus 7.
    – Paul R
    Oct 10, 2011 at 9:31
  • @Paul R: Yeah, I was wondering about that last part since I didn't try very hard to simplify it. I'll edit the answer to point to your simpler version.
    – Mysticial
    Oct 10, 2011 at 9:35
0

Just create an array with all the values (only either need 32 or 64 entries (i.e. 128 or 512 bytes). Then just do a look up.

1
  • Can you expand on this - I can't see how such a small lookup table could work for this ?
    – Paul R
    Oct 10, 2011 at 8:24
-1

Sure. Just get out one of your old computer architecture textbooks and refresh your memory on boolean algebra. A CPU's ALU does it with ANDs and ORs; you can, too.

But why?

An academic exercise? Homework? Curiousity?

1
  • Not really: a CPU does all not only with basic arithmetic operations but also with loops (the OP wants a solution without branches and calls). So I would say no.
    – Matteo
    Oct 10, 2011 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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