如何在不使用任何算术运算的情况下求 x mod 15？

假设我们得到一个无符号整数。并且不使用任何算术运算符，即+ - / * or %，我们要找到x mod 15。我们可以使用二进制位操作。

据我所知，我是根据两点得出这个结论的。

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

Let a = x mod 15 then a = x - 15k（对于一些非负数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

好的。现在来实施这个。 Amod16操作基本上是& OxF. and k基本上是x>>4

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

归根结底就是将 2 个 4 位数字相加。这可以通过位表达式来完成。

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

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

... 等等

这对我来说似乎是在欺骗。我希望有一个更优雅的解决方案

这让我想起了 10 进制的一个老把戏，叫做“抛弃 9”。这用于检查手工执行的大额计算的结果。 在这种情况下123 mod 9 = 1 + 2 + 3 mod 9 = 6.

发生这种情况是因为 9 比数字基数 (10) 少 1。 （省略证明；））

因此考虑以 16 为基数（十六进制）的数字。你应该能够做到：

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

现在您仍然需要施展一些魔法才能使添加的内容消失。但它给出了正确的答案。

UPDATE:

这是 C++ 的完整实现。这f查找表将数字对求和 mod 15。（与字节 mod 15 相同）。然后，我们重新打包这些结果，并在每轮中重新应用一半的数据。

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