It's for 2's complement computation.
You could see that b
indeed equals to ~a+1
, which means b
is a
's 2's complement.
Question
Suppose a = a31 a30 . . . a1 a0
is a 32-bit binary word.
Consider the 32-bit binary word b = b31 b30 . . . b1 b0
computed by the following algorithm:
b
until the first 1
is found (which is also copied to b
)a
.For example, a = 10100 . . . 00
is transformed to b = 01100 . . . 00
. Explain what this algorithm computes if a
and b
are interpreted as binary numbers.
La solution
It's for 2's complement computation.
You could see that b
indeed equals to ~a+1
, which means b
is a
's 2's complement.
Autres conseils
It's two's complement, as timrau noted. The answer is easy to find if you already know it (as I did), but harder to derive.
Start with the part that is copied:
copy_mask = a ^ (a - 1) // extract rightmost 1 and smear to the right
Obviously, the part that isn't copied (and thus "negated", as you called it) is simply the complement of that mask:
negated_mask = ~copy_mask
And now we can build b
:
b = (a & copy_mask) | (~a & ~copy_mask)
Substitute:
b = (a & (a ^ (a - 1))) | (~a & ~(a ^ (a - 1)))
Simplify:
// 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
There's probably a shorter way that doesn't skip too many steps..