(Редактировать - предисловие: я реализую итерацию через все подмножества заданного размера. Для получения следующей комбинации я использую хак Госпера, чтобы быстро получить вектор 0/1 лексикографически следующей комбинации. Теперь мне нужно быстро сопоставить вектор комбинации с массивом элементов из моего набора. К счастью, элементы такие же, как и мощности отдельных битов, и мне интересно, нет ли в С# быстрого сокращения для этого.)
Если я получаю K-е подмножество (в лексикографическом порядке) чисел от 0 до (N-1), биты в двоичном представлении K говорят мне, какие элементы я должен выбрать. Каков самый элегантный способ проверить, какие биты установлены, и создать подмножество (массив) на их основе?
Что-то вроде:
var BitPowers = new List<int>();
for(int i = 0; i<N; ++i)
{
if ((K & (1<<i)) != 0)
{
BitPowers.Add(i);
}
}
return BitPowers.ToArray();
вероятно, будет достаточно, но лучший ли это способ? Я предполагаю, что битовые операции выполняются быстро, но поскольку количество возможных наборов экспоненциально, оптимизация этой функции настолько, насколько я могу, была бы идеальной.
Насколько я знаю, для этого нет встроенного API .NET.
Магия Линка
Вы можете написать этот компактный код за одно задание, но менее оптимизированный по скорости:
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);
Довольно круто, работает в 2 раза быстрее. (Проверено на 1 000 000 случайных чисел, 200 раз)
Ничего встроенного, но вы можете написать свой собственный и отправить его на проверку кода, чтобы узнать, могут ли люди улучшить его. - Кстати: чтобы «оптимизировать», вам нужно решить, для чего оптимизировать: скорость, пространство, элегантность, ремонтопригодность...? - Также: _ количество возможных наборов экспоненциально_ не уверен, что это значит..?