4

我完全被困在如何做这个家庭作业问题上，并寻找一两个提示让我继续前进。我仅限于 20 次操作（=不计入这 20 次）。

我应该填写一个看起来像这样的函数：

    /* Supposed to do x%(2^n).
       For example: for x = 15 and n = 2, the result would be 3.

       Additionally, if positive overflow occurs, the result should be the
       maximum positive number, and if negative overflow occurs, the result
       should be the most negative number.
     */
    int remainder_power_of_2(int x, int n){

      int twoToN = 1 << n;

      /* Magic...? How can I do this without looping? We are assuming it is a
         32 bit machine, and we can't use constants bigger than 8 bits
         (0xFF is valid for example).
         However, I can make a 32 bit number by ORing together a bunch of stuff.
         Valid operations are: << >> + ~ ! | & ^
       */

      return theAnswer;
    }

我在想也许我可以twoToN向左移动......直到我以某种方式检查（没有if / else）它比x大，然后向右移动一次......然后用x异或它......和重复？但我只有20个手术！

4

3 回答 3

3

提示：在十进制系统中，以 10 的幂为模，您只需保留最后几位数字并将其他数字设为空即可。例如 12345 % 100 = 00045 = 45。好吧，在计算机中数字是二进制的。所以你必须清空二进制数字（位）。因此，请查看各种位操作运算符 ( &, |, ^) 来执行此操作。

于 2012-08-27T19:29:30.693 回答
2

由于二进制是基数 2，余数 mod 2^N 由值的最右边位精确表示。例如，考虑以下 32 位整数：

00000000001101001101000110010101

这具有 3461525 的二进制补码值。余数 mod 2 恰好是最后一位 (1)。余数 mod 4 (2^2) 正好是最后 2 位 (01)。余数 mod 8 (2^3) 正好是最后 3 位 (101)。通常，余数 mod 2^N 正好是最后 N 位。

简而言之，您需要能够获取您的输入数字，并以某种方式对其进行屏蔽以仅获取最后几位。

提示：假设您使用的是 mod 64。二进制中 64 的值是：

00000000000000000000000001000000

您感兴趣的模数是最后 6 位。我将为您提供一系列可以将该数字转换为掩码的操作（但我不会告诉您它们是什么，您可以自己弄清楚它们：D）

00000000000000000000000001000000 // starting value
11111111111111111111111110111111 // ???
11111111111111111111111111000000 // ???
00000000000000000000000000111111 // the mask you need

这些步骤中的每一个都等同于可以在 int 类型上执行的一个操作。你能弄清楚它们吗？你能看到如何简化我的步骤吗？:D

另一个提示：

00000000000000000000000001000000 //  64
11111111111111111111111111000000 // -64
于 2012-08-27T19:34:32.920 回答
0

因为你的除数总是二的幂，所以很容易。

uint32_t remainder(uint32_t number, uint32_t power)
{
    power = 1 << power;
    return (number & (power - 1));
}

假设您输入数字为 5，除数为 2

`000000000000000000000000000000101`数字
和
`00000000000000000000000000000001` 除数 - 1
=
`000000000000000000000000000000001` 余数（我们所期望的）

假设您输入数字为 7，除数为 4

`00000000000000000000000000000111`号码
和
`00000000000000000000000000000011` 除数 - 1
=
`00000000000000000000000000000011` 余数（我们所期望的）

这只适用于除数是 2 的幂（除数 = 1 除外），因此请谨慎使用。

于 2012-08-31T12:11:24.217 回答