+ 연산자가 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;
}

이 기능은 +실제로 백그라운드에서 작동 하는 방식을 보여주는 것 같습니다 . 그러나 그것을 이해하기에는 너무 혼란 스럽습니다. 이러한 작업은 오랫동안 컴파일러에서 생성 한 어셈블리 지시문을 사용하여 수행한다고 믿었습니다!

는 IS +코드에 게시 된 연산자 구현 가장 구현? 이것은 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 및 and를 사용하는 대체 구현을 보여줍니다.

---

이 함수는 +가 실제로 백그라운드에서 어떻게 작동하는지 보여줍니다.

아니요. 이것은 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이됩니다. 따라서 전체 가산기가하는 일은 절반 가산기에서 캐리를 가져 와서 저장하고이를 절반 가산기에 또 다른 인수로 전달하는 것입니다.

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

놀랐나요? 이것이 실제로 일어나는 방법입니다. 긴 프로세스처럼 보이지만 컴퓨터는 나노초의 몇 분의 1 또는 좀 더 구체적으로 말하면 반 클럭 주기로 처리합니다. 때로는 단일 클록 사이클에서도 수행됩니다. 기본적으로 컴퓨터에는 ALU(의 주요 부분 CPU), 메모리, 버스 등이 있습니다.

논리 게이트, 메모리 및 ALU에서 컴퓨터 하드웨어를 배우고 컴퓨터를 시뮬레이션하려면이 과정을 볼 수 있습니다.이 과정에서 제가이 모든 것을 배웠습니다. 첫 번째 원칙에서 최신 컴퓨터 구축

전자 인증서를 원하지 않으면 무료입니다. 코스의 2 부는 올해 봄에 예정되어 있습니다.

---

C는 추상 기계를 사용하여 C 코드의 기능을 설명합니다. 따라서 작동 방식은 지정되지 않았습니다. 예를 들어 실제로 C를 스크립팅 언어로 컴파일하는 C "컴파일러"가 있습니다.

그러나 대부분의 C 구현 +에서 기계 정수 크기보다 작은 두 정수 사이는 어셈블리 명령어로 변환됩니다 (여러 단계 후). 어셈블리 명령어는 기계어 코드로 번역되고 실행 파일에 포함됩니다. 어셈블리는 기계 코드에서 "한 단계 제거 된"언어로, 압축 된 바이너리 묶음보다 읽기가 더 쉽습니다.

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

산술 논리 장치는 별도의 가산기와 승수를 갖거나 함께 혼합 할 수 있습니다.

산술 논리 장치에는 덧셈 연산을 수행 한 다음 출력을 생성하는 많은 트랜지스터가 있습니다. 상기 출력은 명령 디코더로부터 생성 된 신호를 통해 라우팅되고 메모리 또는 레지스터에 저장된다.

산술 논리 장치와 명령 디코더 모두에있는 상기 트랜지스터의 레이아웃 (그리고 내가 덧칠 한 부품)은 공장의 칩에 새겨 져 있습니다. 에칭 패턴은 종종 하드웨어 설명 언어를 컴파일하여 생성됩니다. 하드웨어 설명 언어는 무엇이 연결되어 있고 어떻게 작동하는지 추상화하고 트랜지스터와 상호 연결 라인을 생성합니다.

하드웨어 설명 언어는 시간 ( 연속 처럼)이 아니라 공간에서 일어나는 일 을 설명하는 시프트와 루프를 포함 할 수 있습니다 . 하드웨어의 다른 부분 간의 연결을 설명합니다. 상기 코드는 위에 게시 한 코드와 매우 유사하게 보일 수 있습니다.

위의 내용은 많은 부분과 레이어에 걸쳐 광택이 있으며 부정확 한 내용이 포함되어 있습니다. 이것은 내 자신의 무능함 (하드웨어와 컴파일러를 모두 작성했지만 둘 다 전문가입니다)과 전체 세부 사항이 SO 게시물이 아닌 경력 한두 번이 필요하기 때문입니다.

다음 은 8 비트 가산기에 대한 SO 게시물입니다. 여기 에 비 SO 게시물이 있습니다. 여기서 일부 가산기 operator+는 HDL에서 사용 합니다! (HDL 자체 +는 저수준 가산기 코드를 이해 하고 생성합니다.)

---

컴파일 된 C 코드를 실행할 수있는 거의 모든 최신 프로세서에는 정수 추가 기능이 내장되어 있습니다. 게시 한 코드는 정수 추가 연산 코드를 실행하지 않고 정수 추가를 수행하는 영리한 방법이지만 정수 추가가 일반적으로 수행되는 방식은 아닙니다. 실제로 함수 연결은 스택 포인터를 조정하기 위해 어떤 형태의 정수 추가를 사용합니다.

게시 한 코드는 x와 y를 추가 할 때 공통된 비트와 x 또는 y 중 하나에 고유 한 비트로 분해 할 수 있다는 관찰에 의존합니다.

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

합계 x + y는 공통된 비트의 두 배 (x와 y가 모두 해당 비트에 기여하기 때문에)와 x 또는 y에 고유 한 비트의 합계로 다시 쓸 수 있습니다.

(x & y) << 1 공통된 비트의 두 배입니다 (왼쪽 시프트에 1이 효과적으로 곱 해짐).

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

따라서 x를 첫 번째 값으로, y를 두 번째 값으로 바꾸면 합계는 변경되지 않아야합니다. 첫 번째 값은 비트 덧셈의 전달로 생각하고 두 번째 값은 비트 덧셈의 하위 비트로 생각할 수 있습니다.

이 프로세스는 x가 0이 될 때까지 계속되며,이 지점에서 y는 합계를 보유합니다.

---

당신이 찾은 코드는 아주 원시적 인 컴퓨터 하드웨어 가 "add"명령을 어떻게 구현할 수 있는지 설명하려고합니다 . 이 방법이 어떤 CPU 에서도 사용되지 않는다는 것을 보장 할 수 있기 때문에 "might"라고 말하며 그 이유를 설명하겠습니다.

정상적인 생활에서는 십진수를 사용하고이를 더하는 방법을 배웠습니다. 두 개의 숫자를 더하려면 가장 낮은 두 자리를 더합니다. 결과가 10 미만이면 결과를 기록하고 다음 자리로 진행합니다. 결과가 10 이상이면 결과를 빼고 10을 적고 ​​다음 숫자로 진행하여 1을 더 추가하는 것을 잊지 마십시오. 예 : 23 + 37, 3 + 7 = 10을 더하고 0을 적고 ​​다음 위치에 1을 더 추가하는 것을 잊지 마십시오. 10 초 위치에서 (2 + 3) + 1 = 6을 더하고 적어 둡니다. 결과는 60입니다.

You can do the exact same thing with binary numbers. The difference is that the only digits are 0 and 1, so the only possible sums are 0, 1, 2. For a 32 bit number, you would handle one digit position after the other. And that is how really primitive computer hardware would do it.

This code works differently. You know the sum of two binary digits is 2 if both digits are 1. So if both digits are 1 then you would add 1 more at the next binary position and write down 0. That's what the calculation of t does: It finds all places where both binary digits are 1 (that's the &) and moves them to the next digit position (<< 1). Then it does the addition: 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 is 2, but we write down 0. That's what the excludive or operator does.

But all the 1's that you had to handle in the next digit position haven't been handled. They still need to be added. That's why the code does a loop: In the next iteration, all the extra 1's are added.

Why does no processor do it that way? Because it's a loop, and processors don't like loops, and it is slow. It's slow, because in the worst case, 32 iterations are needed: If you add 1 to the number 0xffffffff (32 1-bits), then the first iteration clears bit 0 of y and sets x to 2. The second iteration clears bit 1 of y and sets x to 4. And so on. It takes 32 iterations to get the result. However, each iteration has to process all bits of x and y, which takes a lot of hardware.

A primitive processor would do things just as quick in the way you do decimal arithmetic, from the lowest position to the highest. It also takes 32 steps, but each step processes only two bits plus one value from the previous bit position, so it is much easier to implement. And even in a primitive computer, one can afford to do this without having to implement loops.

A modern, fast and complex CPU will use a "conditional sum adder". Especially if the number of bits is high, for example a 64 bit adder, it saves a lot of time.

A 64 bit adder consists of two parts: First, a 32 bit adder for the lowest 32 bit. That 32 bit adder produces a sum, and a "carry" (an indicator that a 1 must be added to the next bit position). Second, two 32 bit adders for the higher 32 bits: One adds x + y, the other adds x + y + 1. All three adders work in parallel. Then when the first adder has produced its carry, the CPU just picks which one of the two results x + y or x + y + 1 is the correct one, and you have the complete result. So a 64 bit adder only takes a tiny bit longer than a 32 bit adder, not twice as long.

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.

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