knuth - The Art of Computer Programming, Vol 4, Fascicle 2 のタイプミス?

Question

5 ページの下部に「 kをk ⊕ (1 ^{j +1} ) ₂に変更する」というフレーズがあります。2進数でも1の何乗でも1じゃないの？これはタイプミスに違いないと思います。これを報告するためにクヌース博士に電子メールを送信しましたが、何ヶ月も返信が来るとは思っていません。その間、私はこれがどうあるべきかを理解しようとしています。

Answer 1

これは、(...) ₂がビット単位の表現を表すという規則を使用することで解決できます。(1 ^j+1 ) ₂は、累乗を参照するのではなく、j+1 個の 1 のみで構成されます。この規則については、TAOCP Volume 4 Fascicle 1 の 8 ページでより明確に説明されています。たとえば、次のようになります。

x がほぼすべてのゼロ以外の 2 進数の整数である場合、そのビットは次の形式で記述できます。

x = (g01 ^a 10 ^b ) ₂

言い換えると、x は任意の (ただし無限の) バイナリ文字列 g から成り、その後に 0 が続き、その後に a+1 個の 1 と b 個のゼロが続きます。

[エンコードの問題を解決するために、シンボル alpha を g に置き換えました]

元のクエリに戻ります。左辺が^_ _ _{_} ^_ _ ^_ _ _{_} _ ^_ _有効ビットが j+1 (連続) 1 である整数。右辺は累乗です。たとえば、j =3 の場合:

(1 ⁴ ) ₂ = (1111) ₂ = (2 ⁴ - 1)

それが役立つことを願っています。

Answer 2

既知のタイプミスのリストは正誤表ページにあります。

http://www-cs-faculty.stanford.edu/~knuth/taocp.html

報告されたタイプミスはありません。それが本当にタイプミスである場合は、Knuth 自身から賞金を受け取る資格があるかもしれません。