如何在不使用任何算术运算的情况下找到x mod 15? [英] How to find x mod 15 without using any Arithmetic Operations?

问题描述

假设给我们一个无符号整数.并且不使用任何算术运算符，例如+ - / *或%，我们将找到x mod 15.我们可能会使用二进制位操作.

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.

据我所知，我的得分是2分.

As far as I could go, I got this based on 2 points.

a = a mod 15 = a mod 16表示a<15

让a = x mod 15 然后是a = x - 15k(对于某些非负数k).

Let a = x mod 15 then a = x - 15k (for some non-negative 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

OK. Now to implement this. A mod16 operations is basically & OxF. and k is basically x>>4

所以a = ( x & OxF + (x>>4) & OxF ) & OxF.

归结为加2个4位数字.可以通过位表达式来完成.

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])

... 等等

这似乎在欺骗我.我希望有一个更优雅的解决方案

This seems like cheating to me. I'm hoping for a more elegant solution

推荐答案

这让我想起了以10为底的老技巧，称为铸造9s".这用于检查手工执行的大笔款项的结果. 在这种情况下，123 mod 9 = 1 + 2 + 3 mod 9 = 6.

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.

之所以会这样，是因为9比数字的底数(10)小1. (省略证明；))

This happens because 9 is one less than the base of the digits (10). (Proof omitted ;) )

因此，请考虑以16为底的数字(十六进制).您应该能够做到:

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.

更新:

这里有C ++的完整实现. f查找表将成对的数字放入其总和mod 15(与字节mod 15相同).然后，我们重新打包这些结果，并每轮重新应用一半的数据.

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

这篇关于如何在不使用任何算术运算的情况下找到x mod 15?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！