~ x + ~ y == ~ (x + y)는 항상 거짓입니까?

~ x + ~ y == ~ (x + y)는 항상 거짓입니까?

---

이 코드는 항상 거짓으로 평가됩니까? 두 변수 모두 2의 보수 부호있는 정수입니다.

~x + ~y == ~(x + y)

조건을 만족하는 숫자가 있어야한다고 생각합니다. 나는 사이의 숫자를 테스트하려 -5000하고 5000있지만, 결코 이루어지지 평등. 조건에 대한 해를 찾기 위해 방정식을 설정하는 방법이 있습니까?

하나를 다른 것으로 바꾸면 프로그램에 교활한 버그가 발생합니까?

---

모순을 위해 다음 x과 같은 일부 y(mod 2 ⁿ ) 가 존재한다고 가정하십시오.

~(x+y) == ~x + ~y

2의 보수 *로 우리는

      -x == ~x + 1
<==>  -1 == ~x + x

이 결과를 주목하면

      ~(x+y) == ~x + ~y
<==>  ~(x+y) + (x+y) == ~x + ~y + (x+y)
<==>  ~(x+y) + (x+y) == (~x + x) + (~y + y)
<==>  ~(x+y) + (x+y) == -1 + -1
<==>  ~(x+y) + (x+y) == -2
<==>  -1 == -2

따라서 모순입니다. 따라서 ~(x+y) != ~x + ~y모든 x및 y(mod 2 ⁿ )에 대해.

---

^{* 1의 보수 연산을 가진 시스템에서, 평등 실제로 모든 사실이 보유하고 있음을주의하는 것이 재미있다 x와 y. 이것은 하나의 보완 아래에 있기 때문 ~x = -x입니다. 따라서 ~x + ~y == -x + -y == -(x+y) == ~(x+y).}

---

2의 보완

온 광대 한 경우 컴퓨터의 대부분, x정수, 다음 -x과 같이 표현된다 ~x + 1. 마찬가지로 ~x == -(x + 1). 방정식 에서이 substution을 만들면 다음과 같이됩니다.

• ~ x + ~ y == ~ (x + y)
• -(x + 1) +-(y + 1) =-((x + y) + 1)
• -x-y-2 = -x-y-1
• -2 = -1

모순이므로 ~x + ~y == ~(x + y)항상 false 입니다.

---

즉, pedants는 C가 2의 보수를 요구하지 않는다는 것을 지적 할 것이므로 우리도 고려해야합니다 ...

보완

에서 1의 보수 , -x간단하게 표현된다 ~x. 0은 모두 0 +0과 ( -1 -0) 표현 을 모두 갖는 특별한 경우 이지만 IIRC, C는 +0 == -0비트 패턴이 다른 경우에도 필요 하므로 문제가되지 않습니다. 그냥 교체 ~와 함께 -.

• ~ x + ~ y == ~ (x + y)
• -x + (-y) =-(x + y)

이는 사실 모두 x와 y.

---

단지 오른쪽 모두의 비트 고려 x하고 y(IE를합니다. x == 13인 1101기본 2, 우리는, 마지막 비트에 보일 것이다 1다음 네 가지 경우가 있습니다)

x = 0, y = 0 :

LHS : ~ 0 + ~ 0 => 1 + 1 => 10
RHS : ~ (0 + 0) => ~ 0 => 1

x = 0, y = 1 :

LHS : ~ 0 + ~ 1 => 1 + 0 => 1
RHS : ~ (0 + 1) => ~ 1 => 0

x = 1, y = 0 :

이것이 숙제이기 때문에 나는 당신에게 맡길 것입니다 (힌트 : x와 y가 바뀐 이전과 동일합니다).

x = 1, y = 1 :

이것도 당신에게 맡기겠습니다.

가능한 한 입력이 주어지면 방정식의 왼쪽과 오른쪽에서 가장 오른쪽 비트가 항상 다름을 보여줄 수 있습니다. 따라서 양쪽 비트가 뒤집힌 비트가 적어도 있기 때문에 양쪽이 같지 않다는 것을 증명했습니다 서로로부터.

---

비트 수가 n 인 경우

~x = (2^n - 1) - x
~y = (2^n - 1) - y


~x + ~y = (2^n - 1) +(2^n - 1) - x - y =>  (2^n + (2^n - 1) - x - y ) - 1 => modulo: (2^n - 1) - x - y - 1.

지금,

 ~(x + y) = (2^n - 1) - (x + y) = (2^n - 1) - x - y.

따라서 그들은 항상 1의 차이로 불평등합니다.

---

힌트:

x + ~x = -1(모드 ²ⁿ )

질문의 목표가 (C-read-the-C- 사양 기술이 아닌) 수학을 테스트하는 것으로 가정하면 대답을 얻을 수 있습니다.

---

In both one's and two's (and even in 42's) complement, this can be proved:

~x + ~y == ~(x + a) + ~(y - a)

Now let a = y and we have:

~x + ~y == ~(x + y) + ~(y - y)

or:

~x + ~y == ~(x + y) + ~0

Therefore in two's complement that ~0 = -1, the proposition is false.

In one's complement that ~0 = 0, the proposition is true.

---

According to the book by Dennis Ritchie, C does not implement two's complement by default. Therefore, your question might not always be true.

---

Letting MAX_INT be the int represented by 011111...111 (for however many bits there are). Then you know that, ~x + x = MAX_INT and ~y + y = MAX_INT, so therefore you will know for certain that the difference between ~x + ~y and ~(x + y) is 1.

---

C does not require that two's complement be what is implemented. However, for unsigned integer similar logics is applied. Differences will always be 1 under this logic!

---

Of course, C doesn't require this behavior because it no require two's complement representation. For example, ~x = (2^n - 1) - x & ~y = (2^n - 1) - y will get this result.

---

Ah, fundamental discrete mathematics!

Check out De Morgan's Law

~x & ~y == ~(x | y)

~x | ~y == ~(x & y)

Very important for Boolean proofs!

참고URL : https://stackoverflow.com/questions/11111956/x-y-x-y-is-always-false