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 different signs
f_diff(a, b):
    return
    a * ispositive(a) +
    b * ispositive(b)

// when a, b have same signs
f_same(a, b):
    return
    a * ispositive(a-b) +
    b * ispositive(b-a)
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
    f_diff(a, b) * isdiffsign(a, b) +
    f_same(a, b) * issamesign(a, 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), f_same(a, b) returns a+b i.e 2a or 2b. So this refactor:
// 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))

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

No comments:

Post a Comment