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

Результат никогда не может быть «слишком большим» в смысле его представления, требующего больше битов, чем 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это:

• Еще один действительный 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,

Что и требовалось доказать

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

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

Итак, если там только один «одинокий» элемент, скажем, элемент 'a'и все остальные элементы встречаются в массиве даже ДЕСЯТЬ раз, затем он работает «как требуется» -> находит этот одинокий элемент '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' — три раза)

Затем в соответствии с вышеупомянутым 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)

т.е.

а) …все элементы, которые встречаются ДАЖЕ число раз, приводят к нулю

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

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