CODEWITHSUNDEEP
c++cbit-manipulationbitwise-operatorsbitwise-and
sandywho
sandywho

Reputation: 453

Finding minimum value between 2 numbers without comparision operators

I have seen the following method which gives the minimum value b/w 2 numbers without relational operators

y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))

In here if x=6 and y=4 x-y=2 is positive and shifting this value 31 times to the right gives 0.(as sign bit is 0 for +ve numbers) and the eqn becomes

y + ((x-y)&0)

From the above eqn we get y as min value which is true.

But for the case where x=4 and y=6, x-y=-2 and shifting it 31 times to right gives 1 and the eqn becomes:

y + ((x-y)&1)

As per my understanding bitwise & of -2 and 1 becomes 0 and the eqn gives o/p as y(6) instead of x(4). Can someone explain?

Full code: https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/

Thanks

Upvotes: 1

Views: 1402

Answers (3)

Evg
Evg

Reputation: 26342

The explanation given on the said website is wrong. When x < y

(x - y) >> 31 = 0b1...1 (32 ones) (*)

And then 

y + ((x - y) & 0b1...1) = y + (x - y) = x

(*) Note that the right shift of a negative number is implementation-defined. Typically, it performs an arithmetic right shift, filling all binary digits with the most significant one which is 1 for a negative number in two's complement representation.

Upvotes: 4

Swift - Friday Pie
Swift - Friday Pie

Reputation: 14673

Until new standard would be approved the representation of signed integers is implementation-based, and >> on them as well ( << is an UB). Let assume that platform got signed values as complements of 2, then -2 in binary is 11111111111111111111111111111110. Shifting it to right 31 times may actually result in value of all bits set (which equals to -1) or in value 1, depends on implementation. It should be static_cast to unsigned to be shifted in definite way.

Upvotes: 2

0___________
0___________

Reputation: 67820

It is not efficient and slower on many architectures than the "normal" way. I should also mention that it is not readable and very error prone.

example:

int foo(int x, int y) 
{
    return (y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1))));
}

int foo1(int x, int y) 
{
    return x > y ? y : x;
}

and the resulting code (ARM Cortex):

foo:
        sub     r0, r0, r1
        and     r0, r0, r0, asr #31
        add     r0, r0, r1
        bx      lr
foo1:
        cmp     r0, r1
        movge   r0, r1
        bx      lr

or x86

foo:
        sub     edi, esi
        mov     eax, edi
        sar     eax, 31
        and     eax, edi
        add     eax, esi
        ret
foo1:
        cmp     edi, esi
        mov     eax, esi
        cmovle  eax, edi
        ret

Upvotes: 2

Related Questions