( c) 정수 a ~ b 까지 더하는 코드좀 해석 도와주실수 있나요??

maireneu의 이미지

using namespace std;
 
long long solution(int a, int b) {
    long long answer = 0;
    if (a > b) a ^= b ^= a ^= b;
    answer = (long long)b * -~b / 2 - (long long)a * ~-a / 2;
    return answer;
}

프로그래밍 공부하는 학생인데요.. 물어볼만한 커뮤니티가 어딘지 몰라서 검색하다가 여기에 가입했어요 ㅠㅠ

디씨 프로그래밍 갤러리 이런데 물어보니 안알려줘서...

윗코드에서
answer = (long long)b * -~b / 2 - (long long)a * ~-a / 2;

이부분이 이해가 안갑니다 ㅠㅠ 혹시 도와주실수 있나요?

maireneu의 이미지

실수로 포스트가 두개 올라간거 같은데 지울순 없나요..

세벌의 이미지

학교에서 배운 공식
n(n+1)/2
를 활용하면 될 거 같네요.

저는
if (a > b) a ^= b ^= a ^= b;
도 이해 못하겠네요...

kldp에 이미 쓴 글은 글쓴이 본인도 지울 수 없도록 되어 있네요.

maireneu의 이미지

(a ^ b) ^ b = a 인걸 응용한거 같아요

등식을 오른쪽부터 풀어보면

변수 b에 마지막에 대입되는 값은

(a ^ b) ^ b = a 가 되고

변수 a에 마지막으로 대입되는 값은

(a ^ b) ^ ((a ^ b) ^ b) = (a ^ b) ^ a = b 가 되요

즉 swap(a,b)의 효과...
a와 b중에 a를 작은값으로 만들어주려고 쓴 구문같아요

익명 사용자의 이미지

똑똑해 보이려 하는 멍청한 코드네요.

1. a ^= b ^= a ^= b;는, a와 b가 모종의 이유로 같은 변수를 가리키는 것이 아니라면, a와 b의 값을 서로 바꿉니다.
xor 비트 연산자의 성질을 이용하면 증명은 어렵지 않으니 연습문제로 남기겠습니다.

언뜻 보기에는 임시 변수를 도입할 필요도 없고 "cool"해 보이지만, 요즘 컴퓨팅 환경에서는 이런 식의 트릭으로 얻을 수 있을 이점이 하나도 없습니다. 차라리 임시 변수를 도입해서 명시적으로 swap하는 것이 나아요. 최적화는 컴파일러에게 맡겨 놓으면 됩니다.

더군다나 주어진 코드는 C99 및 C++03에서 미정의 동작을 유발합니다. 인접한 sequence point 사이에서 a가 두 번 바뀌고 있기 때문이죠. C11 및 C++11 이후에서는 괜찮은 걸로 알고 있습니다.

2. 2의 보수 음수 표기법에서 -a는 (~a) + 1와 같습니다.
그러니 -~b = -(-b-1) = b+1이고 ~-a = -(-a) - 1 = a - 1이 되는 것이죠.
다시 말해 주어진 식은 answer = (long long)b * (b+1) / 2 - (long long)a * (a-1) / 2;과 같습니다.
그 이상의 해석은 1부터 n까지의 합은 n(n+1)/2와 같다는 사실을 이용하면 문제 없겠지요.

마찬가지로, 쓸데없이 자기 비트 연산자 지식을 과시하고 싶은 게 아니면 구태여 -~b나 ~-a 같은 표현을 쓸 필요는 없습니다. 그렇게 쓴다고 컴파일러가 그대로 연산해 준다는 보장도 없어요. (b+1), (a-1)로 쓰는 게 낫습니다.

3. 요즘 컴파일러는 쓸데없는 인간의 자기과시를 풀어헤치고 제 나름대로 최적의 코드를 만드는 능력이 있습니다.

https://gcc.godbolt.org/z/x-tGnD

gcc 8.2가 1에서 plain한 swap 코드를, 2에서 (b+1)과 (a-1)를 계산하는 코드를 생성하는 모습을 보세요.
컴파일러도 많이 발전했지요.

maireneu의 이미지

그렇군요... 프로그래머스 알고리즘 연습 사이트에서 일반적인 방법으로 쉽게 풀고보니 답보니
사람들 답중에 저게 최다 좋아요 먹었길래....

감사합니다!

익명 사용자의 이미지

코드 골프 같은 걸 하는 중이라거나 ioccc 출품작을 만드는 게 아니라면, 이런 트릭들은 알고는 있되 사용은 지양하는 것이 좋습니다.

Dmitry Murashenkov wrote:
After first few years of programming, when the urge to put some cool looking construct only you can understand into every block of code wears off, you’ll likely come to the conclusion that these examples are actually the code you want to encounter when opening a new project.

If we look at the apps written by good vs average programmers (not talking about total beginners) the code itself is not that much different, but if small conveniences everywhere allow you to avoid frustration while reading it - it is likely written by a professional.

https://www.quora.com/Whats-the-best-code-youve-seen-a-professional-programmer-write-How-does-it-compare-to-the-average-programmer/answer/Dmitry-Murashenkov

익명 사용자의 이미지

"C11 및 C++11 이후에서는 괜찮은 걸로 알고 있습니다."

잘못 알고 계십니다.

익명 사용자의 이미지

어려운 부탁인 줄은 알고 있습니다만 조금 더 설명해 주셨으면 좋겠네요.

karkayan의 이미지

C11과 C++11에서도 피연산자의 evaluation은 unsequenced 입니다.
좀 더 설명하면, a + (++a)와 같은 코드에서 a가 먼저 연산될지 ++a가 먼저 연산될지는 정의되지 않았습니다. a가 ++a보다 먼저 연산되면 결과는 2a+1이 될테고, 반대라면 2a+2가 되겠죠. 하지만 표준에는 어떤것을 먼저 연산할지 정의하지 않았습니다.
위의 코드에서도 비슷한 문제가 있습니다.

Java나 C#에서는 이런 문제가 없습니다. 아마 이거랑 헷갈리신게 아닐까요.

익명 사용자의 이미지

예, C++11에 일반적으로 그런 문제가 있다는 것은 알고 있습니다.
하지만 여기서는 a ^= b ^= a ^= b;에 한정지어서 생각하는 것입니다.

C++03까지는 위 expression 내부에 sequence point가 없기 때문에, a의 값이 두 번 이상 변하는 것만으로 undefined behavior입니다.

C++11에서 대입 연산자의 대입은 "좌측/우측 피연산자의 평가가 끝난 후" 그리고 "대입 표현식의 값 계산이 끝나기 전"에 이루어진다고 기술되어 있습니다. 이러한 기준에 따라 a에 대한 두 차례의 대입은 그 순서가 완전히 결정이 되므로 적법한 표현식이 됩니다.

... 라고 알고 있었는데 제가 틀리게 알고 있는지요?

C11에 대해서는, 지금 다시 찾아봤는데 대입에 따른 side effect가 좌측/우측 피연산자의 평가가 끝난 후에 이루어진다는 기술만 있고, 대입 표현식의 값 계산이 끝나기 전에 이루어진다는 기술이 없기 때문에 여전히 문제가 되는군요. 이 부분에 대해서는 제가 잘못 알고 있었던 것이 맞는 것 같습니다.

karkayan의 이미지

말씀하신 내용은 맞습니다만, 결국 좌측, 우측 피연산자중 어느것이 먼저 계산이 되는지에 대한 정의는 없습니다.
위의 예를 다르게 쓰면 a = a ^ (b = b ^ (a = a ^ b)) 인데,
제일 처음에 a ^ (b ..) 부분에서 a의 값계산이 먼저 이루어지면 a의 값은 a가 되고, (b ..) 부분의 값계산이 먼저 이루어지면 a의 값은 a^b가 됩니다.

익명 사용자의 이미지

아하, 제가 그 점을 간과했군요.
예. 제가 잘못 알고 있었다는 점 인정하겠습니다.

익명 사용자의 이미지

대입 연산자의 시맨틱 변화만 신경쓰다가, 정작 ^ 연산자의 피연산자 평가에 대해서 신경을 못썼네요.
귀한 시간 내셔서 일깨워 주신 분들께 감사드립니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.