英文:
Finding min and max between two numbers using bit manipulation in Go
问题
以下是上述函数在Go语法中的等效写法：
// Function to find minimum of x and y
func min(x, y int) int {
return y ^ ((x ^ y) &^ -(x < y))
}
// Function to find maximum of x and y
func max(x, y int) int {
return x ^ ((x ^ y) &^ -(x < y))
}
在这里，我们使用了位运算符 ^（异或）和 &^（按位清除）来实现最小值和最大值的计算。注意，-（取反）和 <（小于）运算符在Go语言中也适用于整数类型。这样，我们就避免了使用分支语句来实现最小值和最大值的计算。
请注意，这段代码的来源是http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax。在这个链接中，有关于使用位操作来计算最小值的讨论，但没有涉及到Go语言的上下文。同时，这种方法在 x-y 的情况下可能会有未定义的行为。
英文:
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.
答案1
得分: 3
因为在Go语言中，表达式x < y的结果是一个bool类型的值，所以你需要使用if语句将结果转换为0或1。除此之外，Go语言中的运算符与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)
}
英文:
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)
}
答案2
得分: 1
可以吗？可以说是可以，但是以满足你的条件将布尔值转换为整数的方式会导致奇怪的黑客行为，例如：
func convertBoolToInt(b bool) int {
return *(*int)(unsafe.Pointer(&b)) & 1
}
这显然读取的字节数比写入到b地址的字节数要多，& 1可以去除任何“脏位”，但这绝对是一种黑客行为。
然后可以在比较中使用这个函数将它们转换为整数：
y ^ ((x ^ y) & -convertBoolToInt(x < y))
关于y + ((x - y) & ((x - y) >> 31))，正如链接的文章所指出的，它对输入有一些限制。实际上，它适用于可能输入的75%。
在许多情况下，这种限制是可以接受的，因为它无法处理的输入远远超出了“通常使用的值”的范围。对于不可接受的情况，这里有一个替代方案。可以计算“比较掩码”（等同于-(x < y)）为((x - y) ^ ((x ^ y) & ((x - y) ^ x))) >> 31（来源：《黑客的乐趣》第2章，基础知识）。将其插入到第一种方法中，我们得到：
func min(x int, y int) int {
return y ^ ((x ^ y) & (((x - y) ^ ((x ^ y) & ((x - y) ^ x))) >> 31))
}
显而易见的缺点是它需要更多的操作。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论