2개의 정수의 XOR이 범위를 벗어날 수 있습니까?

2개의 정수의 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]

데이터형으로는 나타낼 수 없는 큰 정수로 이어질 수 있습니다.int이 경우는,질문은 다음과 같습니다.

1. 할 수 있는 일인가?XOR에 저장할 수 없는 큰 정수 값을 생성합니다.int입력하시겠습니까?
2. 만약 이것이 일어날 수 없다면 이에 대한 증거가 있나요?

(이 투고는 C++가 아닌 C에 적용됩니다.)

비활성 패딩 비트를 설정했기 때문에 비트 연산자는 트랩 표현을 할 수 없습니다.C11 6.2.6.2/1 각주를 참조해 주세요.

...유효한 값에 대한 산술 연산은 트랩 표현을 생성할 수 없습니다...

("산술 연산"의 의미는 불분명하지만 지수는 XOR의 정의인 6.5.11로 연결된다.)

그러나 C에서는 음의 0이 생성될 수 있습니다.2의 보에는 마이너스 0이 없다.그러나 1의 보수가 있는 시스템에 있다고 가정하면 다음 방법으로 마이너스 0을 생성할 수 있습니다.^또, 이것에 의해 트랩이 표시되는 경우가 있습니다. 6.2.6.2/3에서는, 이것이 가능하다고 명시적으로 말하고 있습니다.

구현에서 음의 0이 지원되는 경우, 음의 0은 다음 방법으로만 생성되어야 합니다.

- 이러한 값을 생성하는 오퍼랜드를 가진 &, |, ^, ~, << 및 > 연산자

마지막으로 6.2.6.2/2는 다음을 초과하는 정수를 나타내는 값 비트의 조합을 가질 수 없음을 암시합니다.INT_MAX

---

요약하면 다음과 같은 결과가 발생할 수 있습니다.^둘에ints:

• 다른 유효한 것intvalue(같은 값의 다른 버전에 대한 다른 패딩 비트로 대체)
• 마이너스 0: 트랩을 발생시키거나 발생시키지 않을 수 있습니다.

XOR는 비트를 조합하여 이전에 비트가 설정되지 않았던 새로운 비트를 생성하지 않기 때문에 경계를 벗어나지 않습니다.

결과5정답입니다.가치의 바이너리 표현과XOR결과

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

다수의 결과를 쉽게 계산할 수 있습니다.XORed 값은 다음과 같습니다.그 결과 홀수 수의 비트가 조합되는 비트가 설정되고 짝수 수의 비트가 설정되지 않습니다.

만약 이것이 일어날 수 없다면 이에 대한 증거가 있나요?

XOR는, 개개의 비트로 반송하지 않는 덧셈과 같습니다.반송하지 않고 비트를 추가하면 오버플로가 발생하지 않기 때문에int값은 범위를 벗어날 수 없습니다.

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

발생할 수 있는 것은 오버플로이며, 이 오버플로우는 작업에 캐리(carry)가 있을 때 발생할 수 있습니다.2의 보완에서는 상위 열로의 이월량이 상위 열의 이월량과 같지 않은 경우를 말합니다.더 읽다

단, XOR은 NOT와 같은 비트 단위 동작이기 때문에 XOR 동작은 캐리를 생성하지 않기 때문에 오버플로우 할 수 없습니다.

XOR, AND, OR, NOT 및 기타 비트 연산자는 입력의 정확히 동일한 위치에 있는 비트로부터 결과 비트를 조합하여 비트별 결과를 생성합니다.따라서 n비트 입력은 더 높은 비트 없이 n비트를 생성하는데 어떻게 경계를 벗어날 수 있을까요?

엄밀히 말하면 두 정수를 XOR할 수 없습니다.두 개의 정수 크기 비트의 백을 XOR할 수 있으며, 다른 경우 해당 비트 백을 정수로 처리할 수 있습니다.다른 시간에는 정수로 취급할 수도 있습니다.

하지만 XOR 연산을 실행하는 순간에는 정수나 짝수 그 자체와는 상당히 다른 것으로 간주됩니다. 즉, 두 개의 비트 시퀀스에 불과하며, 대응하는 비트가 비교됩니다.오버플로우 개념은 여기에 적용되지 않으므로 결과를 정수로 처리하면 오버플로우도 허용되지 않습니다.

그 결과, 그 표현에 필요한 비트의 수는, 「너무 크다」라고는 할 수 없습니다.int는 오퍼랜드의 비트값을 조합하도록 정의되어 있기 때문에 새로운 비트는 생성되지 않습니다.아마도 더 나은 질문은, 그 결과가 유효한 가치 표현 이외의 것이 될 수 있는가 하는 것입니다.int?

부호 없는 정수의 경우 아니요.모든 비트 패턴 및 모든 비트 연산의 결과는 유효한 값 표현입니다.

부호 있는 정수의 경우 음수 값의 구현 정의 표현에 따라 달라집니다.발생할 가능성이 높은 모든 구현에서는 2의 완성을 사용합니다.이 경우 모든 비트 패턴이 유효합니다.따라서 비트 단위 연산의 결과는 유효한 표현입니다.

단, 이 표준에서는 비활성 비트패턴이 1개 이상 존재할 수 있는 다른 표현도 허용하고 있습니다.이 경우 2개의 유효한 오퍼랜드가 있는 비트 단위 연산이 해당 패턴을 생성하여 무효 결과를 생성할 수 있습니다.

가정하다

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 타입에 저장할 수 없는 큰 정수값을 생성할 가능성이 있습니까?

오퍼랜드가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.

Q.E.D.

GENERAL CASE의 경우 기술된 알고리즘은 배열 내에서 외로운 정수를 실제로 찾을 수 없습니다.그게 실제로 찾아낸 건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'- 2회, 요소'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)

예.,

a)...EVEN 횟수만큼 발생하는 모든 요소는 0이 됩니다.

b)...홀수 횟수로 발생하는 모든 요소를 XOR로 편집하여 최종 결과를 생성합니다.

XOR비트에 의한 조작이기 때문에, 물론 오버플로는 할 수 없습니다.

언급URL : https://stackoverflow.com/questions/28320454/can-xor-of-two-integers-go-out-of-bounds