从左到右迭代任何数字的位

Question

我正在尝试在 c.

中实现模幂运算（从左到右平方和乘法）算法

为了从左到右迭代这些位，我可以使用此 link 中解释的掩码在此示例中，使用的掩码是 0x80，它只能用于最大为 8 bits.

的数字

为了让它适用于任意数量的位，我需要动态分配掩码，但这让它有点复杂。

是否有任何其他解决方案可以完成。

提前致谢！

------------编辑---------------------

    long long base = 23;
    long long exponent = 297;
    long long mod = 327;

    long long result = 1;

    unsigned int mask;

    for (mask = 0x80; mask != 0; mask >>= 1) {

         result = (result * result) % mod;  // Square

         if (exponent & mask) {
            result = (base * result) % mod; // Mul
         }
    }

如本例所示，如果我使用掩码 0x80 将不起作用，但如果我使用 0x100 则它可以正常工作。在运行时间选择掩码值似乎是一项开销。

Answer 1

如果要遍历所有位，首先必须知道类型中有多少位。

这是一件出奇复杂的事情：

sizeof给你字节数，但是一个字节可以超过8位。
limits.h 让你 CHAR_BIT 知道一个字节中的位数，但即使你将它乘以 sizeof 你的类型，结果仍然可能是错误的，因为无符号类型允许包含不属于数字表示形式的 填充位 ，而 sizeof returns 存储大小 以字节为单位，其中包括这些 填充位 .

好在this answer有一个巧妙的宏，可以根据各自类型的最大值计算出实际值位的个数：

#define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
                  + (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

无符号类型的最大值非常容易获得：只需将 -1 转换为您的无符号类型即可。

所以，总而言之，您的代码可能如下所示，包括上面的宏：

#define UNSIGNED_BITS IMAX_BITS((unsigned)-1)

// [...]

unsigned int mask;
for (mask = 1 << (UNSIGNED_BITS-1); mask != 0; mask >>= 1) {
    // [...]
}

请注意，应用这个复杂的宏完全没有运行时缺点，它是一个编译时常量。

Answer 2

您的算法似乎不必要地复杂：可以以不依赖于整数类型或其最大值的方式从最低有效位到最高有效位测试指数中的位。这是一个简单的实现，不需要任何大小整数的任何特殊情况：

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
    unsigned long long base     = (argc > 1) ? strtoull(argv[1], NULL, 0) : 23;
    unsigned long long exponent = (argc > 2) ? strtoull(argv[2], NULL, 0) : 297;
    unsigned long long mod      = (argc > 3) ? strtoull(argv[3], NULL, 0) : 327;
    unsigned long long y = exponent;
    unsigned long long x = base;
    unsigned long long result = 1;

    for (;;) {
        if (y & 1) {
            result = result * x % mod;
        }
        if ((y >>= 1) == 0)
            break;
        x = x * x % mod;
    }
    printf("expmod(%llu, %llu, %llu) = %llu\n", base, exponent, mod, result);
    return 0;
}

没有任何命令行参数，它会产生：expmod(23, 297, 327) = 185。您可以通过将基数、指数和模数作为命令行参数传递来尝试其他数字。

编辑：

如果必须从最高有效位到最低有效位扫描 exponent 中的位，则 mask 应定义为与 exponent 相同的类型，如果类型为未签名：

 unsigned long long exponent = 297;
 unsigned long long mask = 0;
 mask = ~mask - (~mask >> 1);

如果类型是有符号的，为了完全的可移植性，您必须使用 <limits.h> 中的最大值定义。但是请注意，使用无符号类型会更有效。

 long long exponent = 297;
 long long mask = LLONG_MAX - (LLONG_MAX >> 1);

循环将浪费时间运行通过所有最重要的 0 位，因此可以首先使用更简单的循环来跳过这些位：

 while (mask > exponent) {
     mask >>= 1;
 }

从左到右迭代任何数字的位

Iterate bits from left to right for any number

c

rsa

traversal

exponentiation