N 이상으로 설정된 비트 수를 계산하십시오.

Question

현재 IP 멀티 캐스팅을 살펴보고 N 호스트의 모든 가능한 조합을 처리하는 데 필요한 고유 멀티 캐스트 그룹 수를 결정합니다.

예를 들어, 3 개의 최종 호스트 (A, B, C)가있는 경우 이러한 호스트의 가능한 모든 조합을 처리 할 수 ​​있도록 총 4 개의 멀티 캐스트 그룹을 만들어야합니다 (AB, AC, BC, ABC). 1 또는 0 호스트가 처리되는 인스턴스는 제외됩니다.

내가 알 수있는 한, 1 또는 0 호스트가 주소 지정되는 인스턴스를 제외한 고유 그룹 수는 [2^N - (N + 1)]로 표시 할 수 있습니다. 여기서 N은 호스트 수입니다.

그러나 적어도 특정 비율의 시스템 만 처리 될 때 얼마나 많은 그룹이 존재하는지 살펴 보는 데 관심이 있습니다.

예를 들어 시스템이 5 개인 경우 총 26 개의 멀티 캐스트 그룹을 갖게됩니다. 그러나 3 개 이하의 시스템을 대상으로하는 그룹을 제외하면 (그룹 만 보거나 4 개의 시스템 만 처리됨) 우리는 6 개의 그룹 만 가질 수 있습니다. 나는 아래와 같이 이것을 손으로 결정할 수있다.

계산 대신이 계산식을 사용할 수 있습니까? 따라서 N 개의 호스트가 있고 Y 호스트 이상을 포함하는 멀티 캐스트 그룹 만 만들려는 경우 Z 멀티 캐스트 그룹이 있음을 의미합니다. 상기 예에서, Y = 4, Z는 것으로 결정 6.

상관 원조 또는 항상

1 with 0 bits set 
00 - 00000 

5 with 1 bit set 
01 - 00001 
02 - 00010 
04 - 00100 
08 - 01000 
16 - 10000 

10 with 2 bits set 
03 - 00011 
05 - 00101 
06 - 00110 
09 - 01001 
10 - 01010 
12 - 01100 
18 - 10010 
20 - 10100 
17 - 10001 
24 - 11000 

10 with 3 bits set 
07 - 00111 
11 - 01011 
13 - 01101 
14 - 01110 
19 - 10011 
21 - 10101 
22 - 10110 
25 - 11001 
26 - 11010 
28 - 11100 

5 with 4 bits set 
15 - 01111 
23 - 10111 
27 - 11011 
29 - 11101 
30 - 11110 

1 with 5 bits set 
31 - 11111 

Answer 1

조합 문제와 같이 처리하면 도움이됩니다. http://en.wikipedia.org/wiki/Combination

N 비트 중 Y와 N 비트가 설정된 조합의 합계를 알고 싶습니다. 이 의사 코드 같은

뭔가 : N choose k이 예를 들어 N!/(k! * (N-k)!)

로 계산 될 수있다

for k from Y..N 
    total += (N choose k) 

당신은 얻을 것이다 : 그러나

5 choose 4 = 5 
5 choose 5 = 1 
-------------- 
    total = 6 

Answer 2

Sum[i=0 to N] N{C}i = Sum of all combinations of i hosts out of N hosts = 2^N 
--- [1] 
Sum[i=0 to Y] N{C}i = Sum of all combinations of multicast groups with Y or fewer hosts, including single hosts. 
--- [2] 

찾는 감사 피드백 ([1] - [2]) .