How to find x mod 15 without using any Arithmetic

问题:

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

回答1:

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;
}

回答2:

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.