Friday, July 01, 2016

compare bitwise

Return +1, 0, -1 for compare(a, b) with no comparison or if-else operator. Based on max bitwise.

Note: isgreater(a, b) cannot return 1 when a == b. Which means ispositive(0) cannot return 1. So make isgreater(a, b) return 1 if a > b and 0 for a <= b by making ispositive(x) return 1 if x > 0 and 0 if x <= 0 and issamesign(a, b) return 1 when a and b are +ve or -ve and neither is 0 (same for isdiffsign(a, b)) and add special cases when either a or b is 0.
int compare(a, b):
    return
    (+1 * isgreater(a, b)) +
    (-1 * isgreater(b, a))

//returns 1 if a > b, 0 if a <= b
bit isgreater(a, b):
    return
    // ++ or --
    (issamesign(a, b) & ispositive(a-b)) +
    // +- or -+
    (isdiffsign(a, b) & ispositive(a)) +
    // 0-
    (iszero(a) & isnegative(b)) +
    // +0
    (ispositive(a) & iszero(b))

// returns 1 if ++ or --, 0 if either is 0
bit issamesign(a, b):
    return
    (ispositive(a) & ispositive(b)) |
    (isnegative(a) & isnegative(b))

// returns 1 if +- or -+, 0 if either is 0
bit isdiffsign(a, b):
    return
    (ispositive(a) & isnegative(b)) |
    (isnegative(a) & ispositive(b))

// returns 1 if +, 0 if 0
bit ispositive(x):
    return (msb(x) ^1) * isnotzero(x)
// returns 1 if -, 0 if 0
bit isnegative(x):
    return msb(x)
bit isnotzero(x):
    return msb(x | -x)
bit msb(x):
    return (x >>31) &1

No comments:

Post a Comment