如何使用按位运算符将任何负值转换为零？

Question

我正在为 Go 中的 LinkedList 编写 PopBack() 操作，代码如下所示：

// PopBack will remove an item from the end of the linked list
func (ll *LinkedList) PopBack() {
    lastNode := &ll.node

    for *lastNode != nil && (*lastNode).next != nil {
        lastNode = &(*lastNode).next
    }

    *lastNode = nil

    if ll.Size() != 0 {
        ll.size -= 1
    }
}

我不喜欢最后一个 if 条款；如果大小为零，我们不想减少到负值。我想知道是否有一个按位运算，其中无论递减后的值是什么，如果它 只是负数 它应该转换为零？

Answer 1

负值设置了符号位，所以你可以这样做

ll.size += (-ll.size >> 31)

假设ll.size是int32和ll.Size()returnsll.size。当然这也意味着 size 永远不会是负数。当大小为正时，右移将符号扩展 -ll.size 使其为 -1，否则将为 0

如果 ll.size 是 int64 然后将轮班计数更改为 63。如果 ll.size 是 uint64 你可以简单地 cast to int64 if the size is never larger than 2⁶³. But if the size can be that large (although almost impossible to occur in the far future) then things are much more trickier:

mask := uint64(-int64(ll.size >> 63)) // all ones if ll.size >= (1 << 63)
ll.size = ((ll.size - 1) & mask) | ((ll.size + uint64(-int64(ll.size) >> 63)) & ^mask)

它基本上是一个 bitwise mux that's usually used in bithacks 因为如果没有 if 在 golang

中你不能将 bool 转换为 int

乍一看，这些都不太可读，所以 if 块通常更好

Answer 2

将循环的每次迭代中的 nil 检查换成循环之前的单个 nil 检查。通过此更改，循环运行得更快，更新大小的运算符是减法。

func (ll *LinkedList) PopBack() {
    if ll.node == nil {
        return
    }
    lastNode := &ll.node
    for (*lastNode).next != nil {
        lastNode = &(*lastNode).next
    }
    *lastNode = nil
    ll.size -= 1
}

如何使用按位运算符将任何负值转换为零？

How to convert any negative value to zero with bitwise operators?

go

linked-list

bit-manipulation

bitwise-operators