Number theory: solution need [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this 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:

1. Scan a from right to left and copy its bits to b until the first 1 is found (which is also copied to b)
2. After that, copy the Boolean negations of the bits in 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.

Answer 1

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.

Answer 2

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..