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, Jul 12 '11 at 06:41
Do you need a solution specifically for `mod 15` or an universal solution for any modulus? — bezmax, Jul 12 '11 at 06: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, Jul 12 '11 at 06:53
@Zsub: Unsure that SO is the place for programming questions?! What is this site coming to… it seems that eventually one will only be able to ask questions like "how to get rounded corners in CSS", and no programming questions will be allowed. :p — ShreevatsaR, Jul 12 '11 at 13:28
@ShreevatsaR Heh, you are right of course :) I was just thinking maybe on those he'd get a somehow better answer. — Zsub, Jul 12 '11 at 14:46
related: [Divisiblity of 5 without using % and / operator](https://stackoverflow.com/q/17113660/995714), [Check if a number is divisible by 3](https://stackoverflow.com/q/3421609/995714), [Is there any way to write "mod 31" without modulus/division operators?](https://stackoverflow.com/q/26047196/995714), [Fast divisibility tests (by 2,3,4,5,.., 16)?](https://stackoverflow.com/q/6896533/995714) — phuclv, Mar 24 '19 at 00:41

score 9 · Accepted Answer · edited May 26 '14 at 16:49

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, Jul 12 '11 at 10:06
@ShreevatsaR - indeed the algorithm then looks hacky, but can be reduced to not very many operations. So I've added an implementation of it... — Michael Anderson, Jul 12 '11 at 11:41
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. — Trev, Jan 31 '21 at 00:40

score 2 · Answer 2 · edited Jun 20 '20 at 09:12

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 — ShreevatsaR, Jul 12 '11 at 15:02

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

2 Answers2

Linked