Finding min and max between two numbers using bit manipulation in Go-CodePudding

What's the equivalent in Go syntax of the functions below:

/*Function to find minimum of x and y*/
public  static int min(int x, int y) { 
   return y ^ ((x ^ y) & -(x < y)); 
} 

/*Function to find maximum of x and y*/
public  static int max(int x, int y) { 
   return x ^ ((x ^ y) & -(x < y)); 
}

The part that I'm finding difficult to write is the negation of x less than y check. I have a version of the using the second suggestion in the article:

    min := y   ((x - y) & ((x - y) >> 31 ))
    max := x - ((x - y) & ((x - y) >> 31 ))

I want a bit-manipulation approach to avoid using branching.

source of the code from http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax

Note that this has been discussed here but not in the context of Go. It seems that the method has an undefined behavior for x-y.

CodePudding user response：

Because the expression x < y evaluates to a bool in Go, you will need to use an if statement to convert the result to 0 or 1. Otherwise, the operators in Go are the same as the operators in C .

func Min(x, y int) int {
    var s int
    if x < y {
        s = -1
    }
    return y ^ ((x ^ y) & s)
}

func Max(x, y int) int {
    var s int
    if x < y {
        s = -1
    }
    return x ^ ((x ^ y) & s)
}

CodePudding user response：

Can it be done? Arguably yes, but turning a boolean into an int in a way that satisfies your criteria results in Weird Hacks, for example:

func convertBoolToInt(b bool) int {
    return *(*int)(unsafe.Pointer(&b)) & 1
}

This of course blatantly reads more bytes than were written to the address of b, the & 1 gets rid of any "dirty bits" but it's definitely a hack.

Then this can be used around the comparisons to turn them into integers:

y ^ ((x ^ y) & -convertBoolToInt(x < y))

About y ((x - y) & ((x - y) >> 31 )), as the linked article notes, it has some limitation on the inputs. Actually it works for 75% of possible inputs.

In many cases that limitation is acceptable, because the inputs for which it breaks are far outside of the "typically used values". For when it is not acceptable, here is an alternative. The "comparison mask" (equivalent to -(x < y)) can be calculated as ((x - y) ^ ((x ^ y) & ((x - y) ^ x))) >> 31 (source: Hacker's Delight chapter 2, Basics). Plugging that into the first approach, we get:

func min(x int, y int) int { 
   return y ^ ((x ^ y) & (((x - y) ^ ((x ^ y) & ((x - y) ^ x))) >> 31))
}

The obvious downside being that it costs a lot more operations.