C에서 + 연산자는 이렇게 구현됩니까?

C에서 + 연산자는 이렇게 구현됩니까?

다음과 같은 원시 연산자를 이해하는 경우+,-,*그리고./C에 구현되어 있습니다.저는 흥미로운 답변에서 다음과 같은 단편들을 발견했습니다.

// replaces the + operator
int add(int x, int y) {
    while(x) {
        int t = (x & y) <<1;
        y ^= x;
        x = t;
    }
    return y;
}

이 함수는 다음 방법을 보여 주는 것 같습니다.+실제로 백그라운드에서 작동합니다.하지만 너무 혼란스러워서 이해할 수가 없어요.컴파일러가 생성한 조립 디렉티브를 사용하여 오랫동안 작업을 할 수 있다고 생각했습니다!

이요?+운영자는 MOST 구현에 게시된 코드로 구현되었습니까?2개의 보완 기능 또는 기타 구현 의존 기능을 이용할 수 있습니까?

현학적 관점에서 C 사양에는 추가 구현 방법이 명시되어 있지 않습니다.

근데 사실적으로 말하면+CPU의 워드사이즈 이하의 정수유형의 연산자는 CPU의 가산명령어로 직접 변환되며, 큰 정수유형은 오버플로를 처리하기 위한 추가 비트를 포함한 복수의 가산명령어로 변환됩니다.

CPU는 내부적으로 논리회선을 사용하여 추가를 구현하며 루프, 비트시프트 또는 C의 동작방식과 매우 유사한 것은 사용하지 않습니다.

2비트를 더하면 다음과 같은 결과가 나옵니다(참고 자료 표).

a | b | sum (a^b) | carry bit (a&b) (goes to next)
--+---+-----------+--------------------------------
0 | 0 |    0      | 0
0 | 1 |    1      | 0
1 | 0 |    1      | 0
1 | 1 |    0      | 1

그래서 비트 단위로 xor를 하면 캐리어 없이 합계를 얻을 수 있습니다.비트를 사용하면 캐리 비트를 얻을 수 있습니다.

멀티비트 번호에 대해 이 관찰 확장a그리고.b

a+b = sum_without_carry(a, b) + carry_bits(a, b) shifted by 1 bit left
    = a^b + ((a&b) << 1)

한번만b이0:

a+0 = a

알고리즘의 요점은 다음과 같습니다.

Add(a, b)
  if b == 0
    return a;
  else
    carry_bits = a & b;
    sum_bits = a ^ b;
    return Add(sum_bits, carry_bits << 1);

재귀를 제거하고 루프로 변환하는 경우

Add(a, b)
  while(b != 0) {
    carry_bits = a & b;
    sum_bits = a ^ b;

    a = sum_bits;
    b = carrry_bits << 1;  // In next loop, add carry bits to a
  }
  return a;

---

상기의 알고리즘을 염두에 두고, 코드의 설명을 간단하게 해 주세요.

int t = (x & y) << 1;

비트를 운반하다.양쪽 오퍼랜드에서 오른쪽의 1비트가 1이면 반송 비트는 1입니다.

y ^= x;  // x is used now

반송 없음 추가(반송 비트 무시)

x = t;

x를 재사용하여 이동하도록 설정

while(x)

더 많은 반송 비트가 있을 때 반복합니다.

---

재귀 구현(이해하기 쉬운)은 다음과 같습니다.

int add(int x, int y) {
    return (y == 0) ? x : add(x ^ y, (x&y) << 1);
}

이 기능은 +가 실제로 백그라운드에서 작동하는 방식을 보여주는 것 같습니다.

아니요. 보통 정수 덧셈은 기계 명령 덧셈으로 변환됩니다.이것은 비트 단위 xor 및 를 사용한 대체 구현을 보여줍니다.

이 기능은 +가 실제로 백그라운드에서 작동하는 방식을 보여주는 것 같습니다.

아니요. 이것은 네이티브에게 번역된 것입니다.add실제로 하드웨어 가산기를 사용하고 있는 머신 명령어ALU.

컴퓨터가 어떻게 추가되는지 궁금하다면, 여기 기본적인 추가기가 있습니다.

컴퓨터에 있는 모든 것은 대부분 트랜지스터로 만들어진 논리 게이트를 사용하여 이루어집니다.완전 가산기에는 반 가산기가 들어있다.

로직 게이트 및 추가에 대한 기본 자습서는 다음을 참조하십시오.비디오는 길지만 매우 도움이 됩니다.

이 비디오에서는 기본적인 반감기가 표시되어 있습니다.간단한 설명은 다음과 같습니다.

반 가산기 더하기 2비트가 주어집니다.사용 가능한 조합은 다음과 같습니다.

• 0과 0을 더하다= 0
• 1 더하기 0 = 1
• 1과 1을 더하면 = 10(표준)

그럼 반감산기는 어떻게 작동할까요?세 개의 논리 게이트로 이루어져 있어요and,xor및 그nand.그nand 두 입력 모두 음의 경우 양의 전류를 공급하므로 0과 0의 경우가 해결됩니다.그xor입력 중 하나는 양의 출력이고 다른 하나는 음의 출력이므로 1과 0의 문제를 해결할 수 있습니다.그and는, 양쪽의 입력이 플러스인 경우에만 플러스 출력을 얻을 수 있기 때문에, 1과 1의 문제가 해결됩니다.기본적으로, 우리는 이제 반쪽 더미를 갖게 되었습니다.하지만 여전히 비트만 추가할 수 있습니다.

이제 우리는 전력을 다한다.풀 가산기는 하프 가산기를 몇 번이고 호출하는 것으로 구성됩니다.이제 이건 캐리어예요.1과 1을 더하면 캐리 1이 나옵니다.풀 가산기는 반 가산기에서 캐리어(carry)를 가져와 저장하고 다른 인수로 반 가산기에 전달합니다.

반송을 어떻게 통과해야 할지 혼란스러울 경우 기본적으로 먼저 반감기를 사용하여 비트를 더한 다음 합계와 반송을 더합니다.자, 이제 캐리를 두 비트로 추가했습니다.따라서 추가할 비트가 끝날 때까지 이 작업을 반복하면 결과를 얻을 수 있습니다.

놀랐어요?실제로 일어나는 일은 이렇습니다.긴 과정처럼 보이지만, 컴퓨터는 그것을 1나노초의 몇 분의 1초, 더 구체적으로 말하면, 반 클럭 사이클로 한다.1회 클럭 사이클이라도 실행할 수 있습니다.기본적으로 컴퓨터는ALU(의 주요 부분)CPU메모리, 버스 등

로직 게이트, 메모리, ALU 등 컴퓨터 하드웨어를 배우고 싶다면 이 과정을 참고하세요.이 과정에서는 이 모든 것을 배웠습니다.제1원칙에 입각한 최신 컴퓨터 구축

전자 인증서를 원하지 않으면 무료입니다.2부 코스는 올해 봄에 나온다.

C는 추상기계를 사용하여 C코드의 기능을 기술합니다.그래서 어떻게 동작하는지는 명시되어 있지 않다.예를 들어 실제로 C를 스크립트 언어로 컴파일하는 C "컴파일러"가 있습니다.

그러나 대부분의 C 구현에서는+기계 정수 크기보다 작은 두 정수 사이에 (여러 단계를 거친 후) 어셈블리 명령으로 변환됩니다.어셈블리 명령은 기계 코드로 변환되어 실행 파일에 포함됩니다.어셈블리는 기계 코드에서 "한 단계 제거"된 언어이며, 팩된 이진수 묶음보다 읽기 쉽도록 고안되었습니다.

그런 다음 대상 하드웨어 플랫폼에 의해 기계 코드가 해석되고 CPU의 명령 디코더가 해석됩니다.이 명령 디코더는 명령을 받아 이를 신호로 변환하여 "제어 라인"을 따라 전송합니다.이러한 신호는 레지스터와 메모리에서 CPU를 통해 데이터를 라우팅하며, 여기서 값이 종종 산술 로직 유닛에서 함께 추가됩니다.

연산 로직 유닛에 별도의 가산기와 곱셈기가 있거나 함께 혼합될 수 있습니다.

연산 로직 유닛에는 덧셈 연산을 수행한 다음 출력을 생성하는 트랜지스터 다발이 있습니다.상기 출력은 명령 디코더에서 생성된 신호를 통해 라우팅되어 메모리 또는 레지스터에 기억된다.

연산 로직 유닛과 명령 디코더(및 광택 처리한 부분)의 양쪽 트랜지스터 레이아웃은 공장의 칩에 식각되어 있다.식각 패턴은 하드웨어 기술 언어를 컴파일하여 생성되는 경우가 많습니다.하드웨어 기술 언어는 무엇이 어떻게 동작하는지 추상화하여 트랜지스터 및 인터커넥트 라인을 생성합니다.

하드웨어 기술 언어에는 시프트와 루프가 포함되어 있습니다.시프트와 루프는 시간(예를 들어 차례차례)에 발생하는 것이 아니라 공간(하드웨어의 다른 부분 간의 접속)에 대해 기술합니다.상기 코드는 위에 게시한 코드와 매우 모호하게 보일 수 있습니다.

위의 내용은 많은 부품과 레이어를 망라하고 부정확한 내용을 포함하고 있습니다.이것은, 제 자신의 무능함(하드웨어와 컴파일러의 양쪽 모두를 기술하고 있습니다만, 어느쪽도 능숙하지 않습니다)과 상세한 것에 대해서는, SO직이 아니고, 커리어나 커리어나 커리어나 커리어나 커리어나 커리어나 커리어나 커리어나 커리어나, 어느쪽도 필요 없기 때문입니다.

여기 8비트 가산기에 대한 SO 게시물이 있습니다.여기 SO 이외의 투고가 있습니다.이 투고에서는, 일부의 추가 기능만이 사용되고 있는 것을 알 수 있습니다.operator+(HDL 자체 인식)+하위 레벨 가산기 코드를 생성합니다).

컴파일된 C코드를 실행할 수 있는 거의 모든 최신 프로세서는 정수 덧셈을 지원합니다.게시한 코드는 정수 추가 opcode를 실행하지 않고 정수 추가를 수행할 수 있는 현명한 방법이지만 일반적으로 정수 추가가 수행되는 방법은 아닙니다.실제로 함수 링크는 스택포인터를 조정하기 위해 어떤 형태의 정수 덧셈을 사용합니다.

게시한 코드는 x와 y를 추가할 때 공통 비트와 x 또는 y 중 하나에 고유한 비트로 분해할 수 있다는 관찰 결과에 따라 달라집니다.

표현x & y(비트 AND)는 x 및 y에 공통되는 비트를 제공합니다.표현x ^ y(비트 배타적 논리합)은 x 또는 y 중 하나에 고유한 비트를 제공합니다.

합계x + y는, 공통의 2배의 비트(x 와 y 의 양쪽 모두 비트에 기여하기 때문에)와 x 또는 y 의 일의 비트의 합계로서 고쳐 쓸 수 있습니다.

(x & y) << 1는, 공통의 비트의 2배입니다(좌측 시프트에 1을 곱하면 2가 됩니다).

x ^ yx 또는 y 중 하나에 고유한 비트입니다.

따라서 x를 첫 번째 값으로, y를 두 번째 값으로 바꾸면 합계는 변경되지 않습니다.첫 번째 값은 비트 추가의 반송으로, 두 번째 값은 비트 추가의 하위 비트로 생각할 수 있습니다.

이 과정은 x가 0이 될 때까지 계속되며, 여기서 y는 합계를 유지합니다.

발견된 코드는 매우 원시적인 컴퓨터 하드웨어가 "추가" 명령을 구현하는 방법을 설명하려고 합니다.이 방법은 CPU에 의해 사용되지 않는다는 것을 보증할 수 있기 때문에 "아마도"라고 말하는 것입니다.그 이유를 설명하겠습니다.

일상에서는 10진수를 사용하고, 그 수를 추가하는 방법을 배웠습니다.두 숫자를 추가하려면 가장 낮은 두 숫자를 추가합니다.결과가 10 미만일 경우 결과를 적어 다음 자리 위치로 진행합니다.결과가 10 이상일 경우 결과에서 10을 뺀 값을 적어 다음 자리까지 이동한 후 1을 더하는 것을 기억하십시오.예를 들어, 23 + 37, 3+7 = 10을 더하고 0을 쓴 다음 다음 위치에 1을 더해야 합니다.10s 위치에서 (2+3) + 1 = 6을 더하고 기록합니다.결과는 60입니다.

이진수에서도 똑같이 할 수 있습니다.차이는 0과 1의 자리수밖에 없기 때문에 가능한 합계는 0, 1, 2뿐이라는 것입니다.32비트 번호의 경우는, 1 자리수의 위치를 차례차례 처리합니다.그리고 이것이 진짜 원시적인 컴퓨터 하드웨어가 할 수 있는 방법입니다.

이 코드는 다르게 동작합니다.두 자리수가 모두 1이면 두 자리수의 합계는 2입니다.두 자리가 모두 1이면 다음 2진수 위치에 1을 더하고 0을 적습니다.이것이 t의 계산입니다.두 자리 숫자가 모두 1(&)인 모든 위치를 찾아 다음 자리 위치(< 1)로 이동합니다.그런 다음 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1은 2이지만 0을 적습니다.그게 배타적 또는 운영자가 하는 일입니다.

하지만 당신이 다음 자리까지 처리해야 했던 1은 모두 처리되지 않았습니다.아직 추가해야 합니다.그래서 코드가 루프를 하는 거야다음 반복에서는 추가 1이 모두 추가됩니다.

왜 어떤 프로세서도 그렇게 하지 않는 거죠?왜냐하면 루프이기 때문에 프로세서는 루프를 싫어하고 속도가 느리기 때문입니다.최악의 경우 32번의 반복이 필요하기 때문에 속도가 느립니다.숫자 0xffffff(32개의 1비트)에 1을 더하면 첫 번째 반복에서는 비트0의 y가 클리어되고 x가 2로 설정됩니다.두 번째 반복에서는 비트1 of y가 지워지고 x가 4로 설정됩니다.기타 등등.결과를 얻으려면 32번의 반복이 필요합니다.단, 각 반복은 x와 y의 모든 비트를 처리해야 하므로 많은 하드웨어가 필요합니다.

원시 프로세서는 가장 낮은 위치부터 가장 높은 위치까지 10진수 산술처럼 빠르게 작업을 수행할 수 있습니다.또한 32개의 스텝이 필요하지만 각 스텝은 이전 비트 위치에서 2비트와 1개의 값만 처리하기 때문에 구현이 훨씬 쉬워집니다.또한 원시 컴퓨터에서도 루프를 구현하지 않고도 이를 수행할 수 있습니다.

현대적이고 빠르고 복잡한 CPU는 "조건부 합산 가산기"를 사용합니다.특히 64비트 가산기 등 비트 수가 많은 경우 시간이 많이 절약됩니다.

64비트 가산기는 다음 두 부분으로 구성됩니다.먼저, 가장 낮은 32비트에 대해 32비트를 가산합니다.이 32비트 가산기는 합계와 "carry"(다음 비트 위치에 1을 추가해야 함을 나타내는 표시기)를 생성합니다.다음으로 상위 32비트에 대해 2개의 32비트애더:하나는 x + y를 더하고 다른 하나는 x + y + 1을 더합니다.3개의 애드 모두 병렬로 동작합니다.첫 번째 가산기에서 캐리어가 생성되면 CPU는 x + y 또는 x + y + 1 중 어느 쪽이 올바른지를 선택하면 완전한 결과를 얻을 수 있습니다.따라서 64비트 가산기는 32비트 가산기보다 아주 조금 더 오래 걸릴 뿐이지 2배는 더 길지 않습니다.

The 32 bit adder parts are again implemented as conditional sum adders, using multiple 16 bit adders, and the 16 bit adders are conditional sum adders, and so on.

My question is: Is the + operator implemented as the code posted on MOST implementations?

Let's answer the actual question. All operators are implemented by the compiler as some internal data structure that eventually gets translated into code after some transformations. You can't say what code will be generated by a single addition because almost no real world compiler generates code for individual statements.

The compiler is free to generate any code as long as it behaves as if the actual operations were performed according to the standard. But what actually happens can be something completely different.

A simple example:

static int
foo(int a, int b)
{
    return a + b;
}
[...]
    int a = foo(1, 17);
    int b = foo(x, x);
    some_other_function(a, b);

There's no need to generate any addition instructions here. It's perfectly legal for the compiler to translate this into:

some_other_function(18, x * 2);

Or maybe the compiler notices that you call the function foo a few times in a row and that it is a simple arithmetic and it will generate vector instructions for it. Or that the result of the addition is used for array indexing later and the lea instruction will be used.

You simply can't talk about how an operator is implemented because it is almost never used alone.

In case a breakdown of the code helps anyone else, take the example x=2, y=6:

---

x isn't zero, so commence adding to y:

while(2) {

x & y = 2 because

        x: 0 0 1 0  //2
        y: 0 1 1 0  //6
      x&y: 0 0 1 0  //2

2 <<1 = 4 because << 1 shifts all bits to the left:

      x&y: 0 0 1 0  //2
(x&y) <<1: 0 1 0 0  //4

In summary, stash that result, 4, in t with

int t = (x & y) <<1;

Now apply the bitwise XOR y^=x:

        x: 0 0 1 0  //2
        y: 0 1 1 0  //6
     y^=x: 0 1 0 0  //4

So x=2, y=4. Finally, sum t+y by resetting x=t and going back to the beginning of the while loop:

x = t;

When t=0 (or, at the beginning of the loop, x=0), finish with

return y;

Just out of interest, on the Atmega328P processor, with the avr-g++ compiler, the following code implements adding one by subtracting -1 :

volatile char x;
int main ()
  {
  x = x + 1;  
  }

Generated code:

00000090 <main>:
volatile char x;
int main ()
  {
  x = x + 1;  
  90:   80 91 00 01     lds r24, 0x0100
  94:   8f 5f           subi    r24, 0xFF   ; 255
  96:   80 93 00 01     sts 0x0100, r24
  }
  9a:   80 e0           ldi r24, 0x00   ; 0
  9c:   90 e0           ldi r25, 0x00   ; 0
  9e:   08 95           ret

Notice in particular that the add is done by the subi instruction (subtract constant from register) where 0xFF is effectively -1 in this case.

Also of interest is that this particular processor does not have a addi instruction, which implies that the designers thought that doing a subtract of the complement would be adequately handled by the compiler-writers.

Does this take advantage of two's complement or other implementation-dependent features?

It would probably be fair to say that compiler-writers would attempt to implement the wanted effect (adding one number to another) in the most efficient way possible for that particularly architecture. If that requires subtracting the complement, so be it.

ReferenceURL : https://stackoverflow.com/questions/35652492/is-this-how-the-operator-is-implemented-in-c