-3

a = a31 a30 . . . a1 a0が 32 ビットのバイナリ ワードであるとします。次のアルゴリズムで計算された
32 ビットのバイナリ ワードを考えてみましょう。b = b31 b30 . . . b1 b0

  1. a を右から左にスキャンしb、最初のビット1が見つかるまでそのビットを にコピーします (これも にコピーされbます) 。
  2. その後、 のビットのブール否定をコピーしますa。

たとえば、a = 10100 . . . 00に変換されb = 01100 . . . 00ます。aおよびbが 2 進数として解釈される場合、このアルゴリズムが計算する内容を説明してください。

4

2 に答える 2

1

2の補数計算用です。

bが実際に に等しいことがわかります。~a+1つまり、bはaの 2 の補数です。

于 2014-01-20T15:47:01.097 に答える
0

timrau が指摘したように、これは 2 の補数です。答えを知っていれば (私のように) 答えを見つけるのは簡単ですが、導き出すのは困難です。

コピーされた部分から始めます。

copy_mask = a ^ (a - 1)    // extract rightmost 1 and smear to the right

明らかに、コピーされていない部分 (つまり、あなたが呼んだように「否定」された部分) は、単にそのマスクの補数です。

negated_mask = ~copy_mask

そして今、私たちは構築することができますb:

b = (a & copy_mask) | (~a & ~copy_mask)

代わりの：

b = (a & (a ^ (a - 1))) | (~a & ~(a ^ (a - 1)))

簡素化する：

// move complement into xor
b = (a & (a ^ (a - 1))) | (~a & (a ^ ~(a - 1)))
// use two's complement definition
b = (a & (a ^ (a - 1))) | (~a & (a ^ -a))
// use two's complement definition
b = (a & ~(a ^ -a)) | (~a & (a ^ -a))
// use definition of xor: p^q = (p&~q)|(~p&q)
b = a ^ (a ^ -a)
// use xor associativity
b = (a ^ a) ^ -a
// simplify xor with self
b = -a

あまりにも多くのステップをスキップしない、より短い方法がおそらくあります..

于 2014-01-20T16:12:10.777 に答える