4

「C-リファレンスマニュアル（第5版）」という本を読んで、私はこのコードに出くわしました（SETの各整数はビット位置で表されます）。

typedef unsigned int SET;

#define emptyset ((SET) 0)

#define first_set_of_n_elements(n) (SET)((1<<(n))-1)

/* next_set_of_n_elements(s): Given a set of n elements,
   produce a new set of n elements. If you start with the
   result of first_set_of_n_elements(k)/ and then at each
   step apply next_set_of_n_elements to the previous result,
   and keep going until a set is obtained containing m as a
   member, you will have obtained a set representing all
   possible ways of choosing k things from m things. */
SET next_set_of_n_elements(SET x) {
    /* This code exploits many unusual properties of unsigned arithmetic. As an illustration:
      if x == 001011001111000, then
      smallest       == 000000000001000
      ripple         == 001011010000000
      new_smallest   == 000000010000000
      ones           == 000000000000111
      returned value == 001011010000111
    The overall idea is that you find the rightmost
    contiguous group of 1-bits. Of that group, you slide the
    leftmost 1-bit to the left one place, and slide all the
    others back to the extreme right.
    (This code was adapted from HAKMEM.) */

    SET smallest, ripple, new_smallest, ones;
    if (x == emptyset) return x;
    smallest     = (x & -x);
    ripple       = x + smallest;
    new_smallest = (ripple & -ripple);
    ones         = ((new_smallest / smallest) >> 1) -1;
    return (ripple | ones);
}

私は「1」の計算に迷いました、そしてそれは計算における重要性です。計算は数学的には理解できますが、なぜこれが機能するのか、どのように機能するのかは理解できません。

関連する注記として、この本の著者は、first_set_of_n_elementsの計算は「符号なし減算の特性を利用する」と主張しています。（2 ^ n）-1はどのように「エクスプロイト」ですか？

4

5 に答える 5

2

まず第一に、このコードはかなりあいまいであり、熟考するのに時間を費やす価値のあるもののようには見えません。それは役に立たない知識を生み出すだけです。

「エクスプロイト」とは、コードがさまざまな算術ルールの実装定義の動作に依存していることです。

001 011001111000は15ビットの数値です。著者が16ではなく15ビットの数値を使用する理由はわかりません。5版を過ぎてもタイプミスが残っているようです。

2の補数システムでその2進数の前にマイナス記号を付けると（ここでは2の補数の説明）、になります1110 1001 1000 1000。コンパイラは数値の10進表現（5752）を保持し、それを負の等価物（-5752）に変換するためです。（ただし、実際のデータ型はそのまま残りunsigned intますので、印刷しようとするとガベージ番号59784になります。）

    0001 0110 0111 1000  
AND 1110 1001 1000 1000
  = 0000 0000 0000 1000

C標準は2の補数を強制しないため、その本のコードは移植性がありません。

于 2013-01-31T10:08:08.300 に答える
2

最小の計算は、intの最初の非0ビットを取得します。それはどのように機能しますか？
nをintのビット長とします。数値xの反対（ビットb n-1 ... b 0 ）は、 xを-xに合計すると、 2nが得られるように計算されます。整数はnビット長しかないため、結果のビットは破棄され、0が得られます。
ここで、b'n - 1 ... b'0を-xのバイナリ表現とします。x +（-x ）は2nに等しくなければならない
ので、 xの最初のビット1 （たとえば、位置i）に出会うと、関連する-xビットも1に設定され、数値を加算すると、キャリーが得られます。2 n
を取得するには、このキャリーは、intのビットシーケンスが終了するまですべてのビットを伝搬する必要があります。したがって、 i < j < nの各位置jでの-xのビットは、以下のプロパティに従います。

b j + b'j + 1 = 10 （バイナリ）

次に、上記から、次のように推測できます。b j = NOT（b'j）したがって、b j＆b' j = 0

一方、0 <= j < iとなるような位置jにある-xのビットb'jは、次のように支配されます。

b j + b'j =0または10

関連するすべてのbjが0に設定されているため、唯一のオプションはb'j =0です。

したがって、xと-xの両方で1である唯一のビットは、位置iにあるビットです。

あなたの例では：

x = 001011001111000
-x = 110100110001000

したがって、

0.0.1.0.1.1.0.0.1.1.1.1.0.0.0
1.1.0.1.0.0.1.1.0.0.0.1.0.0.0 AND
\ ================== === /
0.0.0.0.0.0.0.0.0.0.1.0.0.0

次に、リップルは、位置i（ビットiを含む）の後のすべての連続する「1」を0に変え、最初の次の0ビットを1に変えます（キャリー伝搬のため）。それがあなたが波紋を立てる理由です：

r（x）= 0.0.1.0.1.1.0.1.0.0.0.0.0.0.0

1は、smallest（r（x））をsmallest（x）で割ったものとして計算されます。minimum（x）は、位置iで1ビットのみが1に設定された整数であるため、次のようになります。

（最小（r（x））/最小（x））>> 1 =最小（r（x））>>（i +1）

結果の整数も1に設定されたビットが1つだけで、たとえばインデックスpであるため、この値に-1を引くと、次のような整数が得られます。

0 <= j < pとなる各j について、1つj = 1 p <= j <nとなる各jに対して、1つj = 0


最後に、戻り値は次のような整数です。

  • 引数の1ビットの最初のサブシーケンスは0に設定されます。
  • サブシーケンスの前のすべての0ビットは1に設定されます。
  • サブシーケンスの後の最初の0ビットは1に設定されます。
  • 残りのビットは変更されません

それでは、文がわからなかったので、残りの部分を説明することはできません：

mをメンバーとして含むセットが取得されます

于 2013-01-31T10:45:53.513 に答える
1

実際には2の補数を利用しているため、少し誤解を招く恐れがあります。まず、smallest：の計算

2の補数表現ではx、コメントの-xは110100110001000です。その最下位ビットに焦点を当てxます。2の補数は基本的に1の補数に1を加えたものであるため、そのビットは両方に設定され、xその後-x（LSBに向かう途中）の他のビット位置にはそのプロパティがありません。これが、最小のビットセットを取得する方法です。

rippleは非常に単純で、MSBに伝播するため、そのように名前が付けられており、smallest_ripple上記の説明に基づいています。

onesn要素を選択し続けるためにリップルに追加する必要がある数です。以下に図を示します。

ones: 11  next set: 100011
ones:  1  next set: 100101
ones:  0  next set: 100110

それを実行すると、アイテムnからビットを選択するすべての方法が実際に示されます（ nビット数は最悪の場合n + 1ビットを表す必要があるため、ビットが必要です）。CHAR_BIT * sizeof(int) - 1CHAR_BIT * sizeof(int)-x

于 2013-01-31T10:26:53.357 に答える
1

まず、ここではn=4で取得できる出力の例を示します。考え方は、「n」LSBを「1」に設定して開始し、次に同じビット数を「1」に設定した数値のすべての組み合わせを反復処理することです。

    1111
   10111
   11011
   11101
   11110
  100111
  101011
  101101
  101110 (*)
  110011
  110101
  110110
  111001
  111010
  111100
 1000111
 1001011
 1001101

次のように動作しています。例として、上の星の数字を使用します。

      101110

  • 他の回答で明確に説明されているように、LSBを「1」に設定します。

      101110
& 010011
= 000010

  • LSBを元の数値に追加して、LSBを1つ左に「移動」します。すぐ左のビットが「0」の場合、後続の操作は何もしないため、これは理解しやすいです。この左ビットが「1」の場合、左に伝搬するキャリーを取得します。この最後のケースの問題は、「1」の数が変わることです。そのため、カウントを一定に保つために、「1」をいくらか戻す必要があります。

      101110
+ 000010 
= 110000

  • そのために、新しい結果のLSBを取得し、それを前のLSBで除算することにより、キャリーが伝播したビット数を取得します。これは、「-1」を使用して最も低い位置でプレーンな「1」に変換されます。

      010000
/ 000010
= 001000
>>     1 
-      1
= 000011

  • 最後に、加算の結果とその結果をORします。

    110011
于 2013-01-31T12:30:33.037 に答える
0

「エクスプロイト」は、操作（x＆-x）での符号なしの符号の変更にあると言えます。

于 2013-01-31T09:57:09.127 に答える