如何在不使用任何算术运算的情况下找到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

好.现在来实现这一点.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查找表需要对数字来它们的总和模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;
}