How to calculated the absolute value via of bit operations

Question

In the Hacker's delight, there is an example of calculating the absolute value of x as (х XOR (x >> 31)) - (x >> 31).

I know that x >> 31 returns the sign of x. I understand Boolean algebra, but how does (х XOR (x >> 31)) - (x >> 31) work?

Answer 1

It follows from the definition of two's complement, -x = ~x + 1

If x is negative: y = x>>31 = -1. Rewrite the ~x inversion as x ^ -1, and the +1 to subtracting -1, to get:

-x = (x ^ -1) - -1 = abs(x)

If x is non-negative: y = 0, and (x ^ 0) - 0) is obviously just x.

Answer 2

(x XOR y) - y is just doing 2's complement on a negative number. For positive number, y will be 0 so x remains unchanged.

Example. x = -2.

-2 is represented as 0xFFFFFFFE

x>>31 will make y = 0xFFFFFFFF (ie. -1)

x XOR y will flip all the bits in x giving result as 0x00000001

(x XOR y) - y = 0x00000001 - (-1) = 0x00000002.