在C语言中,是否可以使用按位运算符来生成x%10(模10)?

50few1ms  于 2023-05-16  发布在  其他
关注(0)|答案(4)|浏览(201)

我一直试图在SO和其他网站上搜索这个具体的答案,但到目前为止还没有得到任何明确的答案。
是否可以使用位运算符找到x % 10的整数的最后一位?
在我的代码中,我有类似rand() % 10的东西,我想知道是否有什么可以让它成为一个按位操作,在更少的行可能。
我知道如果你有一个十六进制数,你可以通过以下方式做到这一点:
0xABCDE & 0xF == E
0xABCD & 0xF == D
and so on...
然而,这将导致大于10的范围。由于我使用的是随机数生成器,我希望所有这些操作都在from 0 to 9.范围内,这可能吗?

ruarlubt

ruarlubt1#

在C中可以用位运算符来生成x%10吗?
不,不合理。
众所周知,如果N是2的幂,则可以通过使用位掩码来有效地计算x%N。(例如,x%16x & 0x0F,至少只要x是无符号的。)事实上,这是众所周知的,几乎任何C编译器都知道如何做到这一点。
考虑到2的幂模的吸引人的效率和经济性,我们很想为其他除数寻找类似的技巧。不幸的是,数学不工作了。正如这个问题的其他答案所示,虽然从技术上讲,您可以使用按位运算符的精心组合来计算x%10,但并不清楚这个练习是否有任何价值。参见Fast division/mod by 10x
最后,如果你想计算x%10,用C语言表达它的最佳方式是完全不神奇但显而易见的:

x % 10

如果有比实际除法更好的方法来实现它,请让编译器为您进行优化。代码仍然很明显,因为每个人都知道x % 10的意思。
(And事实上,尽管我刚才说我不认为有合理的“按位快捷方式”来计算x % 10,但事实证明,gcc至少倾向于将该特定表达式编译为一个神秘的、可能更有效的乘法、加法和移位序列,而根本不需要任何DIV指令。
如果计算x%10被证明是程序中的一个瓶颈,那么应该问,为什么要计算x%10这么多,有更好的替代方案吗?
你提到你有“类似rand() % 10的东西”,好像你正在生成单个的、随机的十进制数字。如果这是你需要做的基本事情,可能没有更好的方法了。不过,你浪费了很多rand()试图给予你的熵。您可能需要考虑一个特殊用途的随机数生成器。或者,如果您要将单个随机数字组合成更大的数字,则可能需要考虑更直接地生成这些更大的数字。
当然,x%10经常出现的另一个地方是将数字转换为十进制表示时。例如,我曾经写过一个任意精度的算术库,它在内部以二进制工作,当它必须将其中一个大数转换为十进制并将其打印出来时,它可能会花费大量的时间。调整库以在内部使用 decimal 表示,可以让它更有效地以十进制打印内容。(当然,它会使某些其他操作的效率明显降低。
如果您要将数字转换为十进制作为序列化格式的一部分,并且如果不要求序列化格式易于阅读,则可以考虑以十六进制而不是十进制序列化整数,因为在这种情况下,转换将涉及一系列x%16而不是x%10的计算。

pxyaymoc

pxyaymoc2#

这个算吗没有循环,没有条件,只有&>>和数组索引。对于64位支持,请将函数的长度增加一倍。

int mod10(unsigned int n) {
    const int tab[2][10] = {
        { 0, 2, 4, 6, 8, 0, 2, 4, 6, 8 },
        { 1, 3, 5, 7, 9, 1, 3, 5, 7, 9 },
    };
    
    return tab[n & 1][
      tab[(n >> 1) & 1][
      tab[(n >> 2) & 1][
      tab[(n >> 3) & 1][
      tab[(n >> 4) & 1][
      tab[(n >> 5) & 1][
      tab[(n >> 6) & 1][
      tab[(n >> 7) & 1][
      tab[(n >> 8) & 1][
      tab[(n >> 9) & 1][
      tab[(n >> 10) & 1][
      tab[(n >> 11) & 1][
      tab[(n >> 12) & 1][
      tab[(n >> 13) & 1][
      tab[(n >> 14) & 1][
      tab[(n >> 15) & 1][
      tab[(n >> 16) & 1][
      tab[(n >> 17) & 1][
      tab[(n >> 18) & 1][
      tab[(n >> 19) & 1][
      tab[(n >> 20) & 1][
      tab[(n >> 21) & 1][
      tab[(n >> 22) & 1][
      tab[(n >> 23) & 1][
      tab[(n >> 24) & 1][
      tab[(n >> 25) & 1][
      tab[(n >> 26) & 1][
      tab[(n >> 27) & 1][
      tab[(n >> 28) & 1][
      tab[(n >> 29) & 1][
      tab[(n >> 30) & 1][
      (n >> 31) & 1]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]];
}

请注意,绝对没有理由使用这段代码,但它确实有效,并且值得理解它。
其工作原理是tab[a][b]等于(2*b + a) % 10。另一种看待它的方式是,我们在DFA中执行32个步骤,从状态0开始,每个状态都有两个箭头:箭头0指向(2*n)%10,箭头1指向(2*n+1)%10。最后的状态就是结果。

mxg2im7a

mxg2im7a3#

我想出了这个可行的方法,但可能有一种更优雅的方法来实现它。使用查找表似乎有点像作弊,但我不知道如何摆脱最后几个倍数的10没有分支和循环等。不管怎么说,可能有人会感兴趣。
一个64位的版本也可以用类似的方法构造,但是我选择了一个64位的函数,它调用32位的函数,所有的输入值都经过了检查。

uint32_t uint32mod10(uint32_t n) {
/*
n = sum_{i=0 to 7} (2^4i)n_i
n % 10 = (n_0 + 6(sum_{i=1 to 7} n_i)) % 10

n = sum_{i=0 to 9} (2^i)b_i
n % 10 = (b_0 + 2(b_1 + b_5 + b_9) + 4(b_2 + b_6) + 8(b_3 + b_7) + 6(b_4 + b_8)) 
*/
  uint8_t lut[44] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    0, 1, 2, 3};
  uint32_t m = ((n >> 4) & 0xf) + ((n >> 8) & 0xf) + ((n >> 12) & 0xf) + ((n >> 16) & 0xf)
    + ((n >> 20) & 0xf) + ((n >> 24) & 0xf) + ((n >> 28) & 0xf); // max 7*15 = 105
  n = (n & 0xf) + (m << 2) + (m << 1); // max 15 + 630 = 645
  m = ((n & 0x10) >> 3) + ((n & 0x100) >> 7);
  n = (n & 0xf) + ((n & 0xe0) >> 4) + (m << 1) + m
    + ((n & 0x200) >> 8); // max 15 + 14 + 12 + 2 = 43
  return lut[n];
}

uint32_t uint64mod10(uint64_t n) {
  /*
n = n_0 + n_1*2^24 + n_2*2^48
n % 10 = (n_0 + 6(n_1 + n_2)) % 10 
  */
  uint64_t m = (n >> 48) + ((n >> 24) & 0xffffff);
  return uint32mod10((uint32_t)((n & 0xffffff) + (m << 2) + (m << 1)));
}

编辑:
一些可能很容易在微控制器上编码的东西,实际上可以扩展为用于32位无符号整数的二进制到十进制转换,如下所示。

static inline uint32_t uint32divby5(uint32_t n) {  
  uint32_t a, m = (n >> 2) - (n >> 4);
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  a = m + (m << 2);
  if (a > n) return m - 1;
  return m;
}

uint32_t uint32mod10b(uint32_t n) {
  uint32_t m = uint32divby5(n >> 1);
  return n - (m << 3) - (m << 1);
}

编辑2:
如果64位算术是可用的另一种选择,

static inline uint32_t fastdiv16(uint16_t denom, uint32_t lp30, uint64_t m, uint32_t num)  {
  //result = num/denom
  //uint64_t m = (((uint64_t)1 << 63) / denom);
  //uint32_t lp30 = 30 + lzcnt(m);
  //m = m >> (63 - lp30);
  uint64_t q = (num  * m) >> lp30;
  uint64_t test = q*denom;
  return (uint32_t)(q + 1 - (test + denom > num));
}

uint32_t uint32mod10c(uint32_t n) {
  uint32_t m = fastdiv16(10, 34, 1717986918, n);
  return n - (m << 3) - (m << 1);
}
zengzsys

zengzsys4#

对于0-99范围内的数字,您可以用途:

x - (10*((x*103)>>10)

它不是严格意义上的位运算,而且它是否比余数运算快还值得怀疑。

相关问题