(편집-서문 : 주어진 크기의 모든 하위 집합을 통해 반복 가능을 구현하고 있습니다. 다음 조합을 얻으려면 Gosper의 해킹을 사용하여 사전 식으로 다음 조합의 0/1 벡터를 빠르게 얻습니다. 이제 다음의 벡터를 빠르게 매핑해야합니다. 내 세트의 요소 배열에 대한 조합입니다. 운 좋게도 요소는 개별 비트의 힘과 매우 동일하며 C #에 빠른 단축키가 없는지 궁금합니다.)
숫자 0-(N-1)의 K 번째 부분 집합 (사전 순)을 얻으면 K의 이진 표현에있는 비트가 어떤 요소를 선택해야하는지 알려줍니다. 어떤 비트가 설정되었는지 확인하고이를 기반으로 하위 집합 (배열)을 만드는 가장 우아한 방법은 무엇입니까?
다음과 같은 것 :
var BitPowers = new List<int>();
for(int i = 0; i<N; ++i)
{
if((K & (1<<i)) != 0)
{
BitPowers.Add(i);
}
}
return BitPowers.ToArray();
아마도 충분할 것이지만 이것이 최선의 방법입니까? 비트 연산이 빠르다고 생각하지만 가능한 집합의 수가 기하 급수적이므로이 기능을 최대한 최적화하는 것이 이상적입니다.
내가 아는 것처럼 이러한 작업을 수행하는 .NET 내장 API는 없습니다.
Linq 마술
이 압축 코드를 하나의 할당으로 작성할 수 있지만 속도에 대해서는 덜 최적화되어 있습니다.
int value = 0b10110010;
var BitPowers = Convert.ToString(value, 2)
.Reverse()
.Select((bit, index) => new { index, bit })
.Where(v => v.bit == '1').Select(v => v.index);
foreach ( int index in BitPowers )
Console.WriteLine(index);
정수를 문자열의 이진 표현으로 변환하고, 왼쪽에서 오른쪽으로 좋은 인덱스를 가지도록 반전 한 다음 (비트, 인덱스) 쌍을 선택한 다음 정의 된 항목을 필터링 한 다음 생성 할 인덱스를 선택합니다. 열거 가능한 목록.
산출
1
4
5
7
우아함과 속도의 타협
BitArray 인스턴스를 사용하여 루프를 단순화 할 수 있습니다.
아마도 당신이 요구하는 가장 가까운 "내장"방식 일 것입니다 :
var bits = new BitArray(BitConverter.GetBytes(value));
for ( int index = 0; index < bits.Length; index++ )
if ( bits[index] )
BitPowers.Add(index);
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다