비트마스크로 부분집합 구하는 법점..

  • cjkis
    cjkis

    정수 변수를 이용해 정수의 집합을 표현하기로 합시다. 해당 집합에 숫자 i가 들어 있다면 i번째 비트가 켜져있는 것이죠. 그러면 1024 미만의 짝수와{1,2,...,9}의 부분 집합 간에 1:1 대응이 성립합니다.

    라고 되어있는데요..
    이게 어떻게 가능하죠?
    제가 생각했을 때는
    1024 미만의 짝수를 몇개 구해보면

    1024 미만 짝수 2진수 부분집합
    0 0 -
    2 10 {2}
    4 100 {3}
    6 110 {2,3}
    8 1000 {4}
    10 1010 {2,4}
    12 1100 {3,4}

    이렇게 홀수인 3({1,2}), 5({1,3})와 같은 부분집합은 빠지게 되는게 이게 어떻게 {1,2,...,9}의 부분 집합과 1:1 대응이 되는거죠?


    4년 전
4개의 댓글이 있습니다.
  • Signin
    Signin

    1024 = 2^10 이므로 0이상 1024미만 짝수의 개수는 2^9개입니다.
    또한 {1,2, ..., 9} 는 원소를 9개 가진 집합이므로
    이 집합의 부분집합 개수는 2^9개입니다.
    둘의 개수가 일치하므로 1:1 대응을 시킬 수 있습니다.

    10개 비트로는 0~1023 까지 표현이 가능합니다.
    그런데 여기서는 9개의 비트로 짝수만 표현하므로,
    쉽게 대응시켜 보면 이진수 값에 2를 곱한 결과가 실제 숫자라고
    생각하시면 편할 듯 합니다.

    ex1) {1} = 1(이진수) = 실제 값은 1 x 2 = 2
    ex2) {1,2} = 0011(이진수) = 실제 값은 3 x 2 = 6


    4년 전 link
  • kriii
    kriii

    1에서 10이 아니라 0에서 9인거 아닐까요


    4년 전 link
  • astein
    astein

    제일 마지막자리를 0으로 보시면 됩니다.

    1024 미만 짝수 2진수 부분집합
    0 0 -
    2 10 {1}
    4 100 {2}
    6 110 {1,2}
    8 1000 {3}
    10 1010 {1,3}
    12 1100 {2,3}

    4년 전 link
  • cjkis
    cjkis

    설명해 주신 분들 ㄳㄳㄳ


    4년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.