max of two integers bitwise

No comparison operators.

Use bit arithmetic.

For +ve (and 0), msb is 0. For -ve, msb is 1.

max(a, b)
- returns a, when a > b, a-b is +ve, so a * 1 + b * 0
- returns b, when b > a, a-b is -ve, so a * 0 + b * 1

// 0 for +ve, 1 for -ve, 0 for 0.
msb(x):
    return (x >> 31) & 1
lsb(x):
    return x & 1

// returns 1 if +ve, 0 if -ve, 1 if 0.
// bit is 0 or 1 only
ispositive(bit):
    return msb(bit) ^1 //or ~msb(bit) &1

//bug
max(a, b):
    return
    a * ispositive(a-b) +
    b * ispositive(b-a)

But (a-b) could cause overflow when a, b are of different signs.
(int.max, -1), int.max-(-1) = -ve number
(int.min, 1), int.min-1 = +ve number

When a, b are of different signs, the +ve number is max.

So two functions - different signs and same signs.

// when a, b have same signs
    return
    a * ispositive(a-b) +
    b * ispositive(b-a)

// when a, b have different signs
    return
    a * ispositive(a) +
    b * ispositive(b)

So for max, multiply functions with their masks and sum.

a b  a^b
--same--
0 0    0
1 1    0
--diff--
0 1    1
1 0    1

//bug
max(a, b):
    return
    issamesign(a, b) * (
        a * ispositive(a-b) +
        b * ispositive(b-a)
        )
    +
    isdiffsign(a, b) * (
        a * ispositive(a) +
        b * ispositive(b)
        )

isdiffsign(a, b):
    return msb(a) ^ msb(b)
issamesign(a, b):
    return toggle(isdiffsign(a, b))

toggle(bit):
    return lsb(bit) ^ 1

[Hat tip to ctci]

But when a == b (except 0), max(a, b) returns a+b i.e 2a or 2b. So this refactor to fix ispositive(x):

// return 1 for +ve, 0 for -ve and 0.
ispositive(x):
    return (msb(x) ^ 1) * isnotzero(x)
isnotzero(x):
    return msb(x | -x)

iszero(x):
    return toggle(isnotzero(x))

int max(a, b):
    return
    issamesign(a, b) * (
        a * ispositive(a-b) +
        b * ispositive(b-a)
        )
    +
    isdiffsign(a, b) * (
        a * ispositive(a) +
        b * ispositive(b)
        )
    +
    iszero(a-b) * (a|b)

Instead of a mutually exclusive implementation of ispositive(x) for +ve and 0, since isnegative(x) is mutually exclusive (1 only if -ve), it suffices for a mutually exclusive implementation of isgreater(a, b) where a is greater if same signs and b-a is negative OR diff signs and b is negative.

int max(a, b):
    isgreater(a, b) * a +
    isgreater(b, a) * b +
    iszero(a - b) * (a|b)

// 1 if a > b, 0 if a <= b
bit isgreater(a, b):
    return
    issamesign(a, b) * isnegative(b-a) |
    isdiffsign(a, b) * isnegative(b)

bit issamesign(a, b):
    return toggle(isdiffsign(a, b))
bit isdiffsign(a, b):
    return msb(a ^ b)

// 1 if neg, 0 if >= 0
bit isnegative(x):
    return msb(x)

bit toggle(x):
bit msb(x):
bit lsb(x):