Может ли XOR двух целых чисел выйти за пределы?

Я изучал алгоритм поиска одиночных целых чисел в массиве, и вот реализация:

int arr[] = {10, 20, 30, 5, 20, 10, 30}; int LonelyInteger = 0; for(int i=0; i< 7; i++) { LonelyInteger = LonelyInteger ^ arr[i]; } 

Результат – 5 .

Мой вопрос: предположительно, целые числа (генерируемые операцией XOR ) слишком велики из-за этой операции:

 LonelyInteger ^ arr[i] 

Это приводит к потенциально большому целому числу, которое не может быть представлено типом данных say int в этом случае. Мои вопросы:

  1. Возможно ли, что XOR будет генерировать такое большое целочисленное значение, которое не может быть сохранено в типе int ?
  2. Если это невозможно, то это может быть доказательством для этого?

XOR никогда не выйдет за пределы, потому что он объединяет биты и не создает новые биты, где ранее не были установлены биты.

Результат 5 правильный. Посмотрите на двоичное представление вашего значения и результат XOR

 10 00001010 20 00010100 30 00011110 5 00000101 20 00010100 10 00001010 30 00011110 -------------- 00000101 => 5 

Легкая помощь для вычисления результата многих значений XOR ed: Результат будет иметь бит, в котором нечетное число бит будет объединено, а бит не установлен для четного количества бит.

Если это невозможно, то это может быть доказательством для этого?

XOR эквивалентно добавлению без переноса отдельных битов. Когда вы добавляете биты без переноса, переполнение не может произойти, и поэтому значение int не может выйти за пределы.

Результат никогда не может быть «слишком большим» в смысле его представления, требующего больше бит, чем int , поскольку операция определена для объединения значений битов своих операндов, а не для создания каких-либо новых бит. Возможно, лучший вопрос может быть, может ли результат быть чем-то иным, чем действительным значением представления int ?

Для целых чисел без знака нет. Все битовые шаблоны и, следовательно, результат всех побитовых операций, являются допустимыми представлениями значений.

Для целых чисел со знаком это зависит от представления отрицательных значений, определенных реализацией. Каждая реализация, с которой вы, вероятно, столкнетесь, использует 2′-дополнение, в котором снова используется каждый бит-шаблон; так что результат любой побитовой операции будет действительным представлением.

Однако стандарт также допускает другие представления, в которых может быть один или несколько недопустимых битовых шаблонов. В этом случае возможна побитовая операция с двумя действительными операндами для создания этого шаблона и, следовательно, получение недопустимого результата.

(Это сообщение относится к C, а не C ++)

Побитовые операторы не могут вызвать представление ловушки из-за установки недопустимых битов заполнения, см. C11 6.2.6.2/1 сноска:

… никакая арифметическая операция над допустимыми значениями не может генерировать ловушку …

(Значение «арифметической операции» неясно, но индекс ссылается на 6.5.11, который является определением XOR).

Однако в C они могут вызвать генерирование отрицательного нуля . В дополнении 2 нет отрицательного нуля. Но скажите, что вы были в системе с дополнением 1, тогда вы могли бы генерировать отрицательный ноль через ^ и это может вызвать представление ловушки. В 6.2.6.2/3 прямо сказано, что это возможно:

Если реализация поддерживает отрицательные нули, они должны генерироваться только:

– операторы &, |, ^, ~, << и >> с операндами, которые производят такое значение;

Наконец, в 6.2.6.2/2 подразумевается (я уверен, в любом случае), что невозможно иметь комбинацию битов значений, которая представляла бы целое число, превышающее INT_MAX


Резюмируя, возможные результаты ^ на двух int s:

  • Еще одно допустимое значение int (возможно, с разными, но не улавливающими битами дополнения к другим версиям одного и того же значения)
  • Отрицательный ноль, который может или не может вызвать ловушку

Строго говоря, вы не можете XOR два целых числа . Вы можете XOR два целочисленных мешка с битами, и вы можете обрабатывать эти мешки с битами как целые числа в другое время. Вы можете даже рассматривать их как целые числа в любое другое время.

Но на данный момент вы выполняете операцию XOR, вы рассматриваете их как нечто совершенно отличное от целых чисел или даже чисел, как таковых : они всего две последовательности бит, где сравниваются соответствующие биты. Концепция переполнения не применяется к этому, и поэтому, если вы затем решите рассматривать результат как целое число, оно также не может переполняться.

Возможно ли, что XOR будет генерировать такое большое целочисленное значение, которое не может быть сохранено в типе int?

Если операнды являются int , тогда нет.

Если это невозможно, то это может быть доказательством для этого?

Ну, это тривиально из определения. Это вряд ли является математически строгим доказательством, но вы можете подумать, что бит на выходе XOR будет равен 1, если один из операндов имеет 1 в этой позиции. Так как бит вне диапазона не может быть 1 в операндах, бит выхода со значением 1 не выходит за пределы диапазона.

Нет, не может. В отличие от других ответов мое было бы математическим доказательством.

XOR является ярлыком для эксклюзивной или эксклюзивной дизъюнкции ( ) и может быть определен как:

 A ⊕ B = (A ∪ B)\(A ∩ B) 

Ваш тезис состоит в том, что

 ∃x: x ∉ A ∧ x ∉ B ∧ x ∈ (A ⊕ B) 

Итак, из первого уравнения

 x ∈ (A ∪ B)\(A ∩ B) 

Что можно выразить как

 x ∈ (A ∪ B) ∧ x ∉ (A ∩ B) 

Вторая часть может быть выражена как:

 x ∉ A ∧ x ∉ B 

Первая часть может быть выражена как:

 x ∈ A ∨ x ∈ B 

Что противоречит нашему предположению, что x ∉ A ∧ x ∉ B поэтому тезис неверен для любого множества A и B

QED

XOR, AND, OR, NOT и любые другие побитовые операторы создают побитовые результаты, а биты в результате объединены из битов в точно такой же позиции на входах. Таким образом, n-разрядные входы производят n-бит без какого-либо более высокого бита, поэтому как он может уйти с границ?

В ОБЩЕМ СЛУЧАЕ описанный алгоритм не может действительно найти одиночное целое число в массиве. То, что он действительно находит, это XOR всех элементов, которые там встречаются нечетным числом раз.

Итак, если есть только один «одинокий» элемент, скажем, элемент 'a' , а все остальные элементы имеют число EVEN в массиве, тогда он работает «по мере необходимости» -> он находит этот одинокий элемент 'a' ,

Зачем?

Алгоритм выполняет XOR всех элементов в массиве (a ^ b ^ c ^ d ^ ...)

Операция XOR обладает следующими свойствами:

1) a ^ a = 0 (non-equivalence)

2) a ^ 0 = a (neutrality of 0)

3) a ^ b = b ^ a (commutative property)

4) (a ^ b) ^ c = a ^ (b ^ c) (associative property)

Предположим, например, массив с элементами: {a, b, c, a, c, b, a, c}

(элемент 'a' – 3 раза, элемент 'b' – дважды, элемент 'c' – 3 раза)

Затем, согласно вышеупомянутым свойствам XOR , результат алгоритма

R = (((((((a ^ b) ^ c) ^ a) ^ c) ^ b) ^ a) ^ c)

могут быть перегруппированы следующим образом:

R = (a ^ b) ^ (c ^ a) ^ (c ^ b) ^ (a ^ c) =

= (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ (a ^ c) =

= 0 ^ 0 ^ 0 ^ (a ^ c) = (a ^ c)

т.е.

а) … все элементы, которые имеют число EVEN, приводят к нулю

b) … все элементы, которые имеют время ODD, являются XOR-ed и создают окончательный результат

XOR – это бит-мудрая операция, поэтому она никогда не может переполняться, конечно.

предполагать

 int xor = x^y; Max value of int is x = 999999999; Max value of Xor will come if y=0; and Max Xor is 999999999; 

который находится в пределе. 🙂

Возможно ли, что XOR будет генерировать такое большое целочисленное значение, которое не может быть сохранено в типе int?

 Data-Type3 = Data-Type1 operator Data-Type2 

Если это невозможно, то это может быть доказательством для этого?

У нас Data-Type3 в случае целых чисел есть один из Data-Type1 и Data-Type2 который имеет больший размер, даже в случае сложения или умножения.

 SIZE(Data-Type3) = MAX(SIZE(Data-Type1), SIZE(Data-Type2)) 

Поэтому, если Data-Type1 = Data-Type2 то это тоже возвращаемый тип.

 Short + Short = Short Short + Integer = Integer Short + Long = Long Integer + Short = Integer Integer + Integer = Integer Integer + Long = Long Long + Short = Long Long + Integer = Long Long + Long = Long 

Что может случиться, это переполнение, которое может произойти, когда операция имеет перенос. В дополнении 2 это происходит, когда перенос в колонну высокого порядка не равен выполнению столбца высокого порядка. прочитайте больше

Но операция XOR не может переполняться , потому что операция XOR не генерирует перенос, поскольку XOR – бит-мудрая операция, например NOT.