math - 如何在不使用任何算术运算的情况下找到 x mod 15？

Question

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

就我而言，我是基于 2 分得到的。
a = a mod 15 = a mod 16为 a<15
让 a = x mod 15然后 a = x - 15k (对于一些非负 k )。

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

即 a mod 16 = ( x mod 16 + k mod 16 ) mod 16
即 a mod 15 = ( x mod 16 + k mod 16 ) mod 16
即 a = ( x mod 16 + k mod 16 ) mod 16
好的。现在来实现这一点。 A mod16操作基本上是& OxF .和 k基本上是 x>>4
所以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])
...
等等

这对我来说就像是在作弊。我希望有一个更优雅的解决方案

Answer 1

这让我想起了基数 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 

现在您仍然需要做一些魔术来使添加的内容消失。但它给出了正确的答案。

更新:

这是一个完整的 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;
}