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よりも大きいことを確認し、次に右に1回シフトしてから、xでxorします...そして繰り返す？しかし、私は20回の手術しかありません！

4

3 に答える 3

3

ヒント: 10 のべき乗で剰余を計算する 10 進法では、最後の数桁を残し、残りの桁を null にします。例: 12345 % 100 = 00045 = 45. コンピュータの数値は 2 進数です。したがって、2 進数 (ビット) を null にする必要があります。そのため、さまざまなビット操作演算子 ( &、|、^) を見てください。

于 2012-08-27T19:29:30.693 に答える
2

バイナリは基数 2 であるため、剰余 mod 2^N は、値の右端のビットによって正確に表されます。たとえば、次の 32 ビット整数を考えてみます。

00000000001101001101000110010101

これは 3461525 の 2 の補数値を持ちます。剰余 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 型に対して実行できる正確に 1 つの操作に相当します。それらを理解できますか？私の手順を簡素化する方法がわかりますか? :D

別のヒント:

00000000000000000000000001000000 //  64
11111111111111111111111111000000 // -64
于 2012-08-27T19:34:32.920 に答える
0

除数は常に 2 の累乗なので、簡単です。

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

数値を 5、除数を 2 と入力するとします。

`0000000000000000000000000000101`番号
と
`0000000000000000000000000000001`除数 - 1
=
`0000000000000000000000000000000000001` 残り (期待したもの)

数値を 7、除数を 4 と入力するとします。

`0000000000000000000000000000111`番号
と
`0000000000000000000000000000011`除数 - 1
=
`00000000000000000000000000000000000011` 残り (期待したもの)

これは、除数が 2 の累乗である場合にのみ機能するため (除数 = 1 を除く)、慎重に使用してください。

于 2012-08-31T12:11:24.217 に答える