operator - xor operation in c




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

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) 는 항상 거짓 입니다.

즉, C가 2의 보수를 필요로하지 않는다는 점을 지적 할 것입니다. 그래서 우리는 또한 고려해야합니다 ...

보완하다

하나의 보완에서 , -x 는 단순히 ~x 로 표현됩니다. 0은 모두 0 ( +0 )과 1 ( -0 ) 표현을 갖는 특수한 경우이지만 IIRC, C는 서로 다른 비트 패턴을 가지고 있어도 +0 == -0 요구 +0 == -0 문제. ~ 로 대체하십시오.

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

그것은 모든 xy 대해 사실 입니다.

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

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

나는 조건을 만족시키는 숫자가 있어야한다고 생각합니다. 저는 -5000 에서 5000 사이의 수를 테스트했지만 평등을 달성하지 못했습니다. 조건에 대한 해답을 찾기 위해 방정식을 설정하는 방법이 있습니까?

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


1과 2의 (그리고 심지어 42의) 보완에서, 이것은 증명 될 수있다 :

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

이제 a = y 라고합시다.

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

또는:

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

그러므로 2의 보수가 ~0 = -1 인 경우 명제는 거짓입니다.

~0 = 0 의 보완에서 명제는 참입니다.


Dennis Ritchie가 쓴 책에 따르면 C는 기본적으로 2의 보수를 구현하지 않습니다. 따라서 귀하의 질문이 항상 사실 일 수는 없습니다.


모순을 위해서 어떤 xy (mod 2 n )가 존재한다고 가정하자.

~(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 xy (mod 2 n )에 대해 ~(x+y) != ~x + ~y .

* 보완 산술 연산을 사용하는 기계에서는 평등이 실제로 모든 xy 대해 적용된다는 점이 흥미 롭습니다. 이는 하나의 보수로 ~x = -x 이기 때문입니다. 따라서 ~x + ~y == -x + -y == -(x+y) == ~(x+y) .


비트 수가 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의 차이로 불평등해질 것입니다.


아, 근본 이산 수학!

De Morgan의 법칙을 확인하십시오.

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

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

부울 교정에 매우 중요합니다!


xy 둘 다의 가장 오른쪽 비트만을 고려해보십시오 (IE x == 13 인 경우, 밑이 2 인 경우 1101 입니다. 마지막 비트 a 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 :

나는 너에게도 이걸 맡길거야.

가능한 한 입력이 주어진 방정식의 왼쪽 손 사이드와 오른손 사이드에서 맨 오른쪽 비트가 항상 다르게 표시된다는 것을 보여줄 수 있습니다. 따라서 적어도 하나의 비트가 뒤집 혔기 때문에 양쪽이 동등하지 않다는 것을 증명했습니다 서로에게서.


힌트:

x + ~x = -1 (mod 2 n )

문제의 목표가 (C 읽기 기술이 아닌) 당신의 수학을 시험한다고 가정하면, 이것은 당신을 답으로 이끌어 줄 것입니다.







twos-complement