# ^ \!\= <<

В этой статье расскажем, как можно ошибиться при использовании '^' для возведения в степень\. Хотя в ряде языков он отвечает именно за возведение в степень, во многих популярных стеках разработки этот оператор выполняет операцию исключающего ИЛИ \(XOR\)\. Мы разберём, к каким последствиям приводит подобная путаница, и покажем реальный пример этой ошибки в механизме работы очереди внутри популярной библиотеки\.

![1350_XOR_error_ru/image1.png](https://import.viva64.com/docx/blog/1350_XOR_error_ru/image1.png)

## Введение

Во многих современных языках программирования оператор `^` отвечает за побитовое исключающее ИЛИ \(XOR\); к таким языкам относится Golang\. Однако в некоторых языках этот оператор отвечает за возведение в степень — среди них [Lua](https://www.lua.org/manual/5.5/manual.html#3.4.1), [VB\.NET](https://learn.microsoft.com/en-us/dotnet/visual-basic/language-reference/operators/exponentiation-operator), [Julia](https://docs.julialang.org/en/v1/manual/mathematical-operations/#Arithmetic-Operators), [R](https://cran.rstudio.com/doc/manuals/r-devel/R-lang.html#Operators-1) и другие\. Более того, в повседневной жизни люди зачастую используют именно`^` для обозначения возведения числа в степень\. И это как будто логично — стрелочкой мы как бы указываем на место, где должен быть показатель степени числа\.

Поэтому возможна ситуация, когда разработчик для возведения в степень двойки использует исключающее ИЛИ `^` вместо побитового сдвига `<<`\. Может показаться, что ошибка надуманная, и в действительности разработчики так не ошибаются\. Однако мы все же решили добавить соответствующее диагностическое правило про использование XOR вместо побитового сдвига для нашего Golang\-анализатора, вдохновившись [аналогичным](https://codeql.github.com/codeql-query-help/go/go-mistyped-exponentiation/) из CodeQL\.


> О том, как сделать собственный анализатор для Go, мы писали в статье "\[Как сделать свой статический анализатор для Go?\]\(https://pvs\-studio\.ru/ru/blog/posts/go/1329/\)"\\\.

 

Также мы наткнулись на [обсуждение](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90885) на официальном сайте GCC\. В нём поднимается вопрос о том, что данный паттерн действительно зачастую является ошибочным и стоит выдавать предупреждения на те места, где случайно может быть использован `^` вместо `<<`\.

Свой анализатор PVS\-Studio мы тестируем не только на синтетических примерах, но и на реальных проектах\. Для этого у нас есть выборка открытых проектов с фиксированными версиями\. Но для данной ошибки нашей выборки оказалось мало, поэтому мы использовали свою утилиту, которая скачивает и анализирует свыше 1000 проектов на Go с GitHub\. Однако мы не ожидали встретить ошибку, связанную с использованием `^` в качестве оператора возведения в степень на реальных крупных проектах\.

Но, судя по тому, что вы читаете эту статью, нам есть чем с вами поделиться\.

## Суть ошибки

Как уже упоминалось, ошибка заключается в том, что разработчик использовал `^` вместо `<<`:

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

Распознать её достаточно просто: слева от оператора исключающего ИЛИ находится 2, поскольку разработчик пытается получить какую\-то степень двойки\.

Однако корректный способ вычислить 2 в степени 32 выглядит так: `1 << 32`\.

А теперь перейдём к рассмотрению ошибок на реальных проектах\.

## Неэффективная очередь

Проект [Lancet](https://github.com/duke-git/lancet) позиционируется как комплексная и эффективная библиотека с различными вспомогательными функциями и структурами на языке Go\. Но мы заинтересовались им, потому что наш анализатор PVS\-Studio нашёл следующую ошибку:

```cpp
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: [V8015](https://pvs-studio.ru/ru/docs/warnings/v8015/) Suspicious use of the bitwise XOR operator '^'\. The exponentiation operation may have been intended here\. [arrayqueue\.go](https://github.com/duke-git/lancet/blob/889d0cc3d68d987be61b15332a6bc9e60769f419/datastructure/queue/arrayqueue.go#L87) 87

Из контекста не сложно понять, что речь идёт про операцию добавления элемента в очередь\. Суть проста: если вместимость очереди позволяет добавить туда элемент – мы его добавляем, а если места не хватает, то нужно либо перераспределить места в очереди, либо увеличить вместимость\.

Из кода видно, что если вместимость меньше 65536 \(а это 2 в 16 степени\), то удваиваем вместимость очереди\. А если вместимость уже больше 65536, то мы должны увеличить её на 2 в 16 степени, но из\-за использования XOR будет добавлено 18 \(`2 ^ 16`\)\.

К чему это может привести? К тому, что такая очередь будет работать неэффективно\. Вместимость увеличивается на незначительное значение, поэтому расширять её приходится чаще\. И соответственно чаще придётся копировать все элементы из старой очереди в новую с увеличенным размером\.

Дополнительный признак ошибки — сама запись `2 ^ 16`, намного проще сразу написать 18, если так и задумывалось\.

Давайте рассмотрим ещё одно срабатывание этого диагностического правила\. В этот раз ошибка обнаружена в проекте [Calico](https://github.com/projectcalico/calico)\.

```cpp
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: [V8015](https://pvs-studio.ru/ru/docs/warnings/v8015/) Suspicious use of the bitwise XOR operator '^'\. The exponentiation operation may have been intended here\. [flattener\.go](https://github.com/projectcalico/calico/blob/d008c3c25445c20ca8acbd09197076e48c3f982d/felix/dataplane/windows/flattener.go#L187) 187

Здесь та же проблема — использование `^` вместо `<<`\.  Скорее всего, предполагалось число равное 2 в 16 степени вместо 18\. Но к чему же это может привести? К тому, что длина `BitSet` будет куда меньше ожидаемой в результате инициализации с помощью `bitset.New`\. И программа будет тратить время на расширение длины и перекопирование в методе `Set` посредством метода `extendSet`:

```cpp
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
}
```

Казалось бы, не критично, но всех этих операций можно избежать, если изначально правильно задать длину для `BitSet`\.

## Как с этим бороться

Возможно, подобная ошибка есть и в вашем проекте\. Проверить это несложно – достаточно выполнить поиск по оператору `^`, тем более что исключающее ИЛИ используется не так часто\.

Если же вы хотите иметь возможность находить и устранять такие проблемы сразу же на этапе разработки, советуем обратить внимание на инструменты статического анализа\.

Команда PVS\-Studio уже много лет разрабатывает и поддерживает одноименный анализатор для C, C\+\+, C\# и Java\. Также мы выпускаем анализатор для Golang в ранний доступ\. Чтобы это не пропустить, рекомендуем посетить нашу страницу "[Доступ к ранним версиям PVS\-Studio](https://pvs-studio.ru/ru/pvs-studio-eap/)"\.

## Заключение

Вот и всё\. Мы рассмотрели ошибку, которую с одной стороны можно считать простой опечаткой, но с другой — она способна привести к серьёзным последствиям\.

Чтобы обезопасить код стоит [регулярно выполнять статический анализ кода](https://pvs-studio.ru/ru/blog/posts/1218/)\. Он помогает выявлять небезопасные конструкции, потенциально опасные участки логики и ошибки, которые способны привести к проблемам безопасности приложения\. 

Берегите себя и свой код\!