CODEWITHSUNDEEP
golinked-listbit-manipulationbitwise-operators
Aziz
Aziz

Reputation: 1018

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

I'm writing the PopBack() operation for a LinkedList in Go, the code looks like this:

// 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
    }
}

I don't like the last if clause; if the size is zero we don't want to decrement to a negative value. I was wondering if there is a bitwise operation in which whatever the value is after the decrement, if it's only negative it should covert to a zero?

Upvotes: 0

Views: 962

Answers (2)

phuclv
phuclv

Reputation: 42002

Negative values have the sign bit set, so you can do like this

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

Suppose ll.size is int32 and ll.Size() returns ll.size. Of course this also implies that size is never negative. When the size is positive then the right shift will sign-extend -ll.size to make it -1, otherwise it'll be 0

If ll.size is int64 then change the shift count to 63. If ll.size is uint64 you can simply cast to int64 if the size is never larger than 263. 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)

It's basically a bitwise mux that's usually used in bithacks because you cannot cast bool to int without if in golang

Neither of these are quite readable at first glance so the if block is usually better

Upvotes: 3

user13631587
user13631587

Reputation:

Trade a nil check in each iteration of the loop for a single nil check before the loop. With this change, the loop runs faster and the operator for updating size is subtraction.

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

Upvotes: 1

Related Questions