How to find x mod 15 without using any Arithmetic Operations?

Question

We are given a unsigned integer, suppose. And without using any arithmetic operators ie + - / * or %, we are to find x mod 15. We may use binary bit manipulations.

As far as I could go, I got this based on 2 points.

a = a mod 15 = a mod 16 for a<15

Let a = x mod 15 then a = x - 15k (for some non-negative k).

ie a = x - 16k + k...

ie a mod 16 = ( x mod 16 + k mod 16 ) mod 16

ie a mod 15 = ( x mod 16 + k mod 16 ) mod 16

ie a = ( x mod 16 + k mod 16 ) mod 16

OK. Now to implement this. A mod16 operations is basically & OxF. and k is basically x>>4

So a = ( x & OxF + (x>>4) & OxF ) & OxF.

It boils down to adding 2 4-bit numbers. Which can be done by bit expressions.

sum[0] = a[0] ^ b[0]

sum[1] = a[1] ^ b[1] ^ (a[0] & b[0])

... and so on

This seems like cheating to me. I'm hoping for a more elegant solution

I see nothing wrong with this, no arithmetic operators are used and instead you just use bitwise operators, its probably what they want. — Jesus Ramos
– Jesus Ramos, Commented Jul 12, 2011 at 6:41
Do you need a solution specifically for mod 15 or an universal solution for any modulus? — bezmax
– bezmax, Commented Jul 12, 2011 at 6:45
Maybe post this om math.SE or codegolf.SE for a more elegant solution? I am unsure SO is the place for this. — Zsub
– Zsub, Commented Jul 12, 2011 at 6:53

phuclv · Accepted Answer · 2014-05-26 16:49:59Z

This reminds me of an old trick from base 10 called "casting out the 9s". This was used for checking the result of large sums performed by hand. In this case 123 mod 9 = 1 + 2 + 3 mod 9 = 6.

This happens because 9 is one less than the base of the digits (10). (Proof omitted ;) )

So considering the number in base 16 (Hex). you should be able to do:

0xABCE123 mod 0xF = (0xA + 0xB + 0xC + 0xD + 0xE + 0x1 + 0x2 + 0x3 ) mod 0xF = 0x42 mod 0xF = 0x6

Now you'll still need to do some magic to make the additions disappear. But it gives the right answer.

UPDATE:

Heres a complete implementation in C++. The f lookup table takes pairs of digits to their sum mod 15. (which is the same as the byte mod 15). We then repack these results and reapply on half as much data each round.

#include <iostream> uint8_t f[256]={ 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,0, 1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,1, 2,3,4,5,6,7,8,9,10,11,12,13,14,0,1,2, 3,4,5,6,7,8,9,10,11,12,13,14,0,1,2,3, 4,5,6,7,8,9,10,11,12,13,14,0,1,2,3,4, 5,6,7,8,9,10,11,12,13,14,0,1,2,3,4,5, 6,7,8,9,10,11,12,13,14,0,1,2,3,4,5,6, 7,8,9,10,11,12,13,14,0,1,2,3,4,5,6,7, 8,9,10,11,12,13,14,0,1,2,3,4,5,6,7,8, 9,10,11,12,13,14,0,1,2,3,4,5,6,7,8,9, 10,11,12,13,14,0,1,2,3,4,5,6,7,8,9,10, 11,12,13,14,0,1,2,3,4,5,6,7,8,9,10,11, 12,13,14,0,1,2,3,4,5,6,7,8,9,10,11,12, 13,14,0,1,2,3,4,5,6,7,8,9,10,11,12,13, 14,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14, 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,0}; uint64_t mod15( uint64_t in_v ) { uint8_t * in = (uint8_t*)&in_v; // 12 34 56 78 12 34 56 78 => aa bb cc dd in[0] = f[in[0]] | (f[in[1]]<<4); in[1] = f[in[2]] | (f[in[3]]<<4); in[2] = f[in[4]] | (f[in[5]]<<4); in[3] = f[in[6]] | (f[in[7]]<<4); // aa bb cc dd => AA BB in[0] = f[in[0]] | (f[in[1]]<<4); in[1] = f[in[2]] | (f[in[3]]<<4); // AA BB => DD in[0] = f[in[0]] | (f[in[1]]<<4); // DD => D return f[in[0]]; } int main() { uint64_t x = 12313231; std::cout<< mod15(x)<<" "<< (x%15)<<std::endl; }

To get rid of the additions, you can use a 16x16 lookup table. :-)
@ShreevatsaR - indeed the algorithm then looks hacky, but can be reduced to not very many operations. So I've added an implementation of it...
I independently discovered this when I was ten and am still proud of it, 25 years later. Unfortunately it's been a bit of a dry spell since then.

Community · Accepted Answer · 2020-06-20 09:12:55Z

Your logic is somewhere flawed but I can't put a finger on it. Think about it yourself, your final formula operates on first 8 bits and ignores the rest. That could only be valid if the part you throw away (9+ bits) are always the multiplication of 15. However, in reality (in binary numbers) 9+ bits are always multiplications of 16 but not 15. For example try putting 1 0000 0000 and 11 0000 0000 in your formula. Your formula will give 0 as a result for both cases, while in reality the answer is 1 and 3.

In essense I'm almost sure that your task can not be solved without loops. And if you are allowed to use loops - then it's nothing easier than to implement bitwiseAdd function and do whatever you like with it.

Added:

Found your problem. Here it is:

... a = x - 15k (for some non-negative k).

... and k is basically x>>4

It equals x>>4 only by pure coincidence for some numbers. Take any big example, for instance x=11110000. By your calculation k = 15, while in reality it is k=16: 16*15 = 11110000.

Specifically, k is x>>4 if and only if floor(x/15)=floor(x/16), which happens if and only if, writing x=15k+r where 0≤r<15, we have 16k≤x<16(k+1). This in turn means that k≤r<k+16. So the largest x for which this is true is x=224 (corresponding to k=r=14), and there are only 120 such x. Examples of x for which it's not true are 15, 30, 31, 45, 46, 47, 60, 61, 62, 63, etc.

Collectives™ on Stack Overflow

How to find x mod 15 without using any Arithmetic Operations?

2 Answers 2

4 Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Linked

Related