^ != <<

In some languages, the '^' operator can be used for exponentiation, but in other popular development stacks, it operates as the exclusive OR (XOR) operator. Today, we'll discuss how this confusion can lead to errors, demonstrate their real-world examples in a popular library's queue implementation, and explain the consequences of these errors.

Introduction

The ^ operator is responsible for bitwise exclusive OR (XOR) in many modern programming languages, including Go. However, in other languages, such as Lua, VB.NET, Julia, R, and others, it represents exponentiation. Plus, people often use ^ to define the power of a number in everyday life, and it makes sense because the symbol kind of shows where the exponent should be.

So, developers might use the exclusive OR ^ instead of the bitwise shift << to raise a number to the power of two. Although this error may seem far-fetched, we added a diagnostic rule to our Go analyzer inspired by a similar rule in CodeQL to detect instances of using the XOR instead of a bitwise shift.

For more on how to make your own analyzer for Go, check out our article "How to create your own Go static analyzer?"

We also came across a discussion on the official GCC website. It brings up the issue that this pattern is often erroneous, and that warnings should be issued where developers may accidentally use ^ instead of <<.

We test our PVS-Studio analyzer on both synthetic examples and real-world projects. For this purpose, we collect open-source projects with specific versions. However, this wasn't enough for this particular error, so we used our own utility, which downloads and analyzes over 1,000 Go projects from GitHub. However, we were surprised to encounter an error related to the use of ^ as an exponentiation operator in real large-scale projects.

Well, the fact that you're reading this article means we've got something to share with you.

What the error is about

As mentioned above, the error is that ^ is used instead of <<:

func main() {
  fmt.Println(2 ^ 32)
}

It's easy to spot: there's 2 to the left of the exclusive OR operator because the developers wanted to get the power of two.

However, the correct way to calculate 2 to the power of 32 is as follows: 1 << 32.

Now, let's move on to discussing errors in real projects.

Inefficient queue

The Lancet project is a comprehensive and efficient Go language library with various auxiliary features and structures. However, we found it interesting because PVS-Studio analyzer detected the following error:

func (q *ArrayQueue[T]) Enqueue(item T) bool {
  if q.tail < q.capacity {
    q.data = append(q.data, item)
    // q.tail++
    q.data[q.tail] = item
  } else {
    //upgrade
    if q.head > 0 {

      ....
    } else {
      if q.capacity < 65536 {
        if q.capacity == 0 {
          q.capacity = 1
        }
        q.capacity *= 2
      } else {
        q.capacity += 2 ^ 16            // <=
      }

      tmp := make([]T, q.capacity, q.capacity)
      copy(tmp, q.data)
      q.data = tmp
    }

    q.data[q.tail] = item
  }

  q.tail++
  q.size++

  return true
}

PVS-Studio warning: V8014 Suspicious use of the bitwise XOR operator '^'. The exponentiation operation may have been intended here. arrayqueue.go 87

The context clearly refers to the operation of adding an element to a queue. The idea is simple: if the queue capacity allows adding an element, we'll add it; if no, we either need to reorganize the space in the queue or increase the capacity.

We can see that if the capacity is less than 65536 (which is 2 to the power of 16), the queue capacity is doubled. And if the capacity is greater than 65536, it'll be increased by 2 to the power of 16. However, due to the use of XOR, 18 (2 ^ 16) will be added.

What's the outcome? This queue becomes inefficient. The capacity increases by only a small amount, leading to more frequent reallocations. So, the code will more often need to copy all elements from the old queue to the bigger new one.

Another clue that this is an error is the way 2 ^ 16 is written. It'd be much easier to just write 18 if that's what was intended.

Now, let's take a look at another example of this diagnostic rule in action. This time, we found an error in the Calico project.

func parsePorts(portsStr string) *bitset.BitSet {
  setOfPorts := bitset.New(2 ^ 16 + 1)                // <=
  for _, p := range strings.Split(portsStr, ",") {
    if strings.Contains(p, "-") {
      // Range
      parts := strings.Split(p, "-")
      low, err := strconv.Atoi(parts[0])
      if err != nil {
        panic(err)
      }
      high, err := strconv.Atoi(parts[1])
      if err != nil {
        panic(err)
      }
      for port := low; port <= high; port++ {
        setOfPorts.Set(uint(port))
      }
    } else {
      // Single value
      port, err := strconv.Atoi(p)
      if err != nil {
        panic(err)
      }
      setOfPorts.Set(uint(port))
    }
  }
  return setOfPorts
}

PVS-Studio warning: V8014 Suspicious use of the bitwise XOR operator '^'. The exponentiation operation may have been intended here. flattener.go 187

Here's the same issue—^ is used instead of <<. It's likely that developers meant to use 2 to the power of 16 instead of 18. So, what could this lead to? The BitSet length will be much smaller than expected due to initialization using bitset.New. The program will spend time extending the length and recopying in the Set method using extendSet:

func (b *BitSet) Set(i uint) *BitSet {
    if i >= b.length { // if we need more bits, make 'em
        b.extendSet(i)
    }
    b.set[i>>log2WordSize] |= 1 << wordsIndex(i)
    return b
}
func (b *BitSet) extendSet(i uint) {
    if i >= Cap() {
        panic("You are exceeding the capacity")
    }
    nsize := wordsNeeded(i + 1)
    if b.set == nil {
        b.set = make([]uint64, nsize)
    } else if cap(b.set) >= nsize {
        b.set = b.set[:nsize] // fast resize
    } else if len(b.set) < nsize {
        newset := make([]uint64, nsize, 2*nsize) // increase capacity 2x
        copy(newset, b.set)
        b.set = newset
    }
    b.length = i + 1
}

This may seem insignificant, but the developers could've avoided all these operations if they had set the correct length for BitSet from the beginning.

How to deal with it

Your project may also contain a similar error. Checking this is simple—just search for the ^ operator, especially since XOR isn't used very often.

If you'd like to detect and fix these issues right at the development stage, we suggest using static analysis tools.

For many years, the PVS-Studio team has been developing and supporting the analyzer for C, C++, C#, and Java. We're also releasing an early access version of the Go analyzer. To make sure you don't miss it, you can visit our PVS-Studio Early Access Program page.

Conclusion

That's it. We discussed a flaw that may look like a simple typo but could also lead to serious consequences.

To maintain code security, we recommend regularly running static code analysis. It helps detect unsafe constructs, potentially dangerous logic blocks, and errors that could lead to application security issues.

Take care of yourself and your code!