내가 <code>n</code>는 것을 알고 <code>n * (n + 1)/2</code>을 구현하기 위해 노력하고

Question

동시에 n 개의 * (N + 1)/2 및 취급 오버 플로우를 계산하기 위해 모든 간결한 방법은 int는 < = 2^16-1 (이것은 그 n * (n + 1)/2 <= 2^31 - 1 그래서이 보장 오버플로가 없음).

그러면 n * (n + 1)/2은 음수가 아닌 정수가됩니다. 프로그램에서이 값을 계산할 때, 우선 n *(n + 1) 곱셈을하면 정수 오버플로 문제가 발생할 수 있습니다. 내 생각은 서투른 조건을 사용하는 것입니다.

int m; 
if (n % 2 == 0) { 
    m = (n/2) * (n + 1); 
} else { 
    m = n * ((n + 1)/2); 
} 

더 이상 간결한 방법이 있습니까?

Answer 1

당신은 어떻게 생각에 대해 :

m = ((n + (n & 1)) >> 1) * (n + !(n & 1)); 

설명 :

이 솔루션 것은 두 가지 목표를 달성하려고 :

• if then else 조건을 사용하는
• 피를 오버 플로우하지 말고, 파이프 라인 친화적이다.

오버플로를 피하기 위해 먼저 나누고 곱합니다. 분수가 절반 (2 분)으로 나누어지면 흥미로운 속성이 생깁니다. 숫자가 홀수이면 분대가 정확하며 간단하게 을 우회하여을 1 씩 우회 할 수 있습니다.

숫자가 if then else 조건없이 홀수 인 경우 다음과 같은 트릭을 사용합니다.

숫자가 홀수 인 경우 하위 비트가 0 (1로 올림하여 캡처 됨)을 나타냅니다. 그렇지 않으면 짝수입니다. 따라서 숫자가 홀수이면 2로 나눕니다. 그렇지 않으면 홀수와 나눗셈인지 확인하기 위해 먼저 1을 더합니다.

말하면

,이 용액에 상당 :

if (n is odd) 
    m = (n >> 1) * (n + 1); 
else 
    m = ((n + 1) >> 1) * n; 

Answer 2

가장 간단한 해결책은 더 큰 중간 형 사용할 아마도 : 자동 보낸 모든 피연산자들을 전송할 필요가 없다

int m = (int)((long long)n * (n + 1)/2) ; 

을 타입 프로모션이 적용됩니다.

Answer 3

이 삼항 연산자를 사용하여 테스트를 작성하는 더 간결한 방법 :

int m = (n % 2 == 0) ? (n/2) * (n + 1) : n * ((n + 1)/2); 

는하지만 동일한 코드를 생성 할 가능성이있다. 당신은 추가 정밀 long long을 활용할 수

는 (적어도 63 값 비트)를 제공하기 위해 보장 :이 타겟 CPU에 따라 달라집니다 더 많거나 적은 효율적인 테스트 버전보다 여부

int m = (long long)n * (n + 1)/2; 

및 컴파일러 버전 및 옵션 이 버전은 읽고 이해하기가 더 쉽습니다. 결과가 왜 범위 내에 있는지 설명하기 위해 주석을 추가하는 것이 유용 할 것입니다.

int m = (n + (n & 1))/2 * (n + 1 - (n & 1)); 

데모 :

• n 인 경우 아마데우스에 의해 제안에서 파생
  는

  , 여기에 64 비트를 arithmetics를 사용하지 않는, 더 간결하지만, 훨씬 덜 읽을 수있는 대안이다 홀수, 우리가 얻을 m = (n + 1)/2 * n;

• n 경우, 우리는 얻을 : m = n/2 * (n + 1);.

Answer 4

하나 이상 :

int m = (n/2 * n) + ((n%2) * (n/2)) + (n/2) + (n%2); 

Answer 5

아마

result = (n) * (n/2) + (n & 1) * (n) + n/2 ;