주어진 이진 문자열의 하위 집합을 생성하십시오.이 코드는 어떻게 작동합니까?

Question

하위 집합 생성에 대한 답변을 찾고있는 동안 this code snippet이 발생합니다.

start 

N; //an integer 

X = N 
while true 

    print X 
    if(X == 0) 
     break; 

    X = (X-1) & N; 
end while 
end 

아무도이 코드가 작동하는 이유를 설명 할 수 있습니까? 미리 감사드립니다.

---

답변 해 주셔서 감사합니다. 내 증명 아이디어는 다음과 같습니다 :

N을 마스크로 생각하면 중요한 비트는 N의 1의 위치입니다. 이것을 마스크 된 공간이라고 부릅니다. X은 항상 N의 하위 집합이므로 X의 카운트 다운은 마스크 된 공간에서 카운트 다운과 같습니다 (마스크 된 공간에서 반전 된 비트). 따라서 X과 (X-1) & N 사이에는 다른 하위 집합이 없습니다.

Answer 1

당신은 다음과 같은 인수와 함께 작동 증명할 수 :

1. (X-1) 항상 (랩 어라운드 무시) 작은 수를 생성합니다.
2. (X-1)&N <= (X-1).
3. k & N은 N의 "하위 집합"이어야합니다.
4. k과 k&N 사이의 값이 N의 "하위 집합"일 수 있으므로 아무 것도 놓치지 않았습니다.

Answer 2

실제로 일어나는 일을 이해하려면 여기에서 가장 복잡한 연산 인 빼기를 완전히 이해해야합니다.

다른 방법은 1을 빼는 방법에 대해 생각할 때 가장 중요한 비트에서 숫자를 살펴보기 시작한 다음 처음 1을 찾을 때까지 가장 중요한 비트쪽으로 스캔하는 것입니다. 모든 비트를 뒤집어서 1.

&과 결합하면 가장 낮은 비트 세트를 버리고 은에 해당 비트의 오른쪽에 1이던 비트를 되돌립니다. 예를 들어

는

10110 start here 
10101 subtract 1 
10100 and with N 
10011 subtract 1 
10010 and with N 
10001 subtract 1 
10000 and with N 
01111 subtract 1 
00110 and with N