Monday, August 10, 2015

max of two integers, no compare operator or if else

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)

No comments:

Post a Comment