NoSyu의 주저리주저리 :: 2008년 1학기 시스템 프로그래밍

isLessOrEqual.

즉, x, y 두 인자를 받으면 x≤y인지 확인하여 맞으면 1, 틀리면 0을 내놓습니다.

이것은 이렇게 하였습니다.

먼저 x≤y ⇒ 0≤y-x입니다.

즉, y - x가 0보다 크거나 같다면 원식을 만족합니다.

0보다 크거나 같은 것을 확인하는 방법은 sign bit가 0임을 확인하는 것입니다.

sign bit는 MSB(Most significant bit)에 있으니

이를 LSB(Least significant bit)에 가져옵니다.

그런 다음에 뺄셈을 한 것의 sign bit를 가져옵니다.

마지막으로 이것들의 진리표를 그려 최소항(minterm)을 가져와서

그것을 연산하여 return하도록 하였습니다.

자세한 것은 주석에 적었습니다만, 엉터리 영어로 적은터라 이렇게 한글로 적습니다.^^;;

(하지만 한글도 엉망이네요.;;;)

/*
* isLessOrEqual - if x <= y then return 1, else return 0
*   Example: isLessOrEqual(4,5) = 1.
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 24
*   Rating: 3
*/
int isLessOrEqual(int x, int y) {
    /*
     * + <= - : false
     * - <= + : true
     * + <= +, - <= - : compare with y - x
     *
     * x'MSB    y's MSB        compare_Function    result
     * 0        0            0                    0
     * 0        0            1                    1
     * 0        1            0                    0
     * 0        1            1                    0
     * 1        0            0                    1
     * 1        0            1                    1
     * 1        1            0                    0
     * 1        1            1                    1
     *
     * So I make minterm : AB' + AC + B'C
     *
     * compare_Function
     * x <= y == 0 <= y - x
     * if y - x => 0 then sign bit(MSB) of y - x is 0
     * else y - x < 0 then sign bit(MSB) of y - x is 1
     * So I shift right because all bit to be same bit(sign bit).
     * Last, I use ! because if sign bit 0, then it's true.
     *
     * 20080402 | 20080405
     */
    int x_MSB_value = !!(x >> 31); // x's MSB
    int y_MSB_value = !!(y >> 31); // y's MSB
    int sub_MSB_value = !((y + (~x + 1)) >> 31); // compare x and y
    return (x_MSB_value & ~y_MSB_value) | (x_MSB_value & sub_MSB_value) | (~y_MSB_value & sub_MSB_value); // minterms
}