maxnc Namespace Reference

Maximum of two numbers without conditionals. More...

Functions
def	maxnc (a, b)
	Return the maximum of two numbers. More...
def	main ()

Detailed Description

Maximum of two numbers without conditionals.

  a > b, a + b + a - b = 2a
  a < b, a + b - a + b = 2b
  max(a,b) = (a + b + abs(a-b)) / 2
  

Author

Paulo Roma

Date

07/04/2018

See also

https://stackoverflow.com/questions/1375882/mathematically-find-max-value-without-conditional-comparison

Function Documentation

main()

def maxnc.main

(

)

maxnc()

def maxnc.maxnc	(		a,
			b
	)

Return the maximum of two numbers.

(a + b + math.sqrt((a-b)*(a-b))) / 2.0

Note that even square root has also a conditional test.

• Whenever c > 0 and \(c^2 = d\), we have a second solution -c, because \((-c)^2 = (-1)^2*c^2 = 1*c^2 = d.\)
• Square root returns the greatest in the pair. It comes with a built in:

    int max(int c1, int c2) {
        return c1 > c2 ? c1 : c2;
    }
   

A second approach is using bitwise operators, which works for integers.

Let nb be the number of bits in a word minus one.

• a-((a-b)&((a-b)>>nb))

(a-b)>>nb gets the sign bit

• For unsigned numbers, the bit positions that have been vacated by the right shift operation are zero-filled.
• For signed numbers, the sign bit is used to fill the vacated bit positions.
• In other words, if the number is positive, 0 is used, and if the number is negative, 1 is used.

This results in:

• -1 for negative and 0 for positive
• if a > b \(\rightarrow\) (a-b)&0 is 0 \(\rightarrow\) a - (a-b)&0 = a

Two complement is all bits negated plus 1.

• a-b = a + (~b+1).
• So, -1 is a number with all bits set: (111111...1)
• x & -1 is x.
• if a < b \(\rightarrow\) (a-b)&-1 is (a-b) = -abs(a-b) \(\rightarrow\) a - (a-b)&-1 = b

Parameters

a	first number.
b	second number.

See also

https://msdn.microsoft.com/en-us/library/336xbhcz.aspx