c언어 질문입니다!
글쓴이: seopy / 작성시간: 월, 2019/07/22 - 4:15오후
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; }
Forums:
XOR 연산을 쓰면 간단히 해결할 수 있습니다.
XOR 연산을 쓰면 간단히 해결할 수 있습니다.
두 값을 XOR 연산한 후 그 결과 비트 스트림에서 '1'의 개수를 세면 되죠.
예를 들어
1001 ^ 1010 = 0011, 0011 중에는 '1'이 2개 있음
이것을 모든 집합에 대해서 반복하면 2개 이상의 집합을 끄집에 낼수도 있을 겁니다.
요는 어떻게 빠르고 간단하게 비트 스트림에서 '1'의 개수를 셀수 있느냐죠.
헉..정말 그렇네요!!감사합니다ㅜㅜ
헉..정말 그렇네요!!감사합니다ㅜㅜ
총 2^n개의 n비트 비트열 중에서, 조건을 만족하는
총 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" 이라고 합니다.
댓글 달기