c언어 질문입니다!

seopy의 이미지

arr[4] 라는 곳에 맨 아래에 있는 코드를 이용해서 0000 ~ 1111 까지 저장을 했습니다.
제가 하고 싶은 것을 예시를 통해 보여드리도록 하겠습니다.

ex) 16개 중 4개만 예시로 해보겠습니다.
[0번] 0 0 0 0
[1번] 0 0 0 1
[2번] 1 0 1 0
[3번] 1 1 1 1

0번과 1번의 차이값은 1입니다.
1번과 3번의 차이값은 3입니다.
2번과 3번의 차이값은 2입니다.
0번과 4번의 차이값은 4입니다.

보시면 아시겠지만 차이값은 n번과 m번을 비교해 각 주소값이 다르면 1씩 증가시킨 것입니다.
이렇게 0000 부터 1111 까지 모두 비교했을 때, 차이값이 2이상인 애들만 뽑고 싶은데 어떻게 해야하나요?

결과는 다음과 같이 총 8개가 나옵니다. (직접 손으로 비교해본 결과)
0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111
(8개중 2개를 임의로 골라 비교해보면 차이값이 2이상인 애들로만 있을거에요)

가능하시다면 arr[4] 가 아니더라도 즉, arr[6] ,arr[8] ... 일 경우에도 성립할 수 있도록 해주시면 감사하겠습니다.

int main()
{
 int i, j;
 int arr[4];
 int cnt = 0;
 
 for (i = 0; i < 16; i++)
 {
  for (j = 0; j < 4; j++)
  {
   arr[j] = (i >> (3 - j)) % 2;
   printf("%d ", arr[j]);
  }
  if (j % 4 == 0)
   printf("\n");
  cnt++;  
 }
 printf("\ncnt : %d\n", cnt);
 return 0;
}

라스코니의 이미지

XOR 연산을 쓰면 간단히 해결할 수 있습니다.
두 값을 XOR 연산한 후 그 결과 비트 스트림에서 '1'의 개수를 세면 되죠.

예를 들어
1001 ^ 1010 = 0011, 0011 중에는 '1'이 2개 있음

이것을 모든 집합에 대해서 반복하면 2개 이상의 집합을 끄집에 낼수도 있을 겁니다.

요는 어떻게 빠르고 간단하게 비트 스트림에서 '1'의 개수를 셀수 있느냐죠.

seopy의 이미지

헉..정말 그렇네요!!감사합니다ㅜㅜ

익명 사용자의 이미지

총 2^n개의 n비트 비트열 중에서, 조건을 만족하는 가장 큰 부분집합은 아래와 같이 두 개 찾을 수 있습니다.

(1) 1이 짝수 번 나타나는 비트열, 2^(n-1)개. ex) 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111
(2) 1이 홀수 번 나타나는 비트열, 2^(n-1)개. ex) 0001, 0010, 0100, 1000, 0111, 1011, 1101, 1110

왜 이렇게 되는지에 대한 증명은 독자를 위한 연습 문제로 남기도록 하겠습니다. :)

사족: 위와 같은 성질을 두고 "Hypercube graphs are bipartite" 이라고 합니다.

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.