Как убедиться, что по крайней мере m из n бит включены?

Мне дано n наборов, и я должен убедиться, что выбрано не менее m наборов. Я планирую разобраться с битами.
Мой подход:

for i in [0,(2^n)-1]
convert i to binary
if number of 1s are greater than or equal to m
{ Some calculations requiring which bits are on }

Теперь, есть ли другой способ убедиться, что число битов по крайней мере м? В моем подходе, приведенном выше, я буду тратить время на преобразование чисел в двоичное, а затем проверять, нет ли. из битов> = m. Есть ли способ обрезать петлю? (Я имею дело с C ++)

2

Решение

Я думаю, вам нужно сгенерировать битовые маски, чтобы выбрать подмножество по крайней мере «m» элементов из набора «n» элементов.
Это легко сделать, если у нас есть алгоритм для генерации всех битовых масок, имеющих именно так биты «m» установлены.

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

// Given "n" and "r", generate all the possible nCr subsets of an array of size "n"
typedef unsigned long long ULL;

// Generate the lowest number bigger than "num" having exactly "r" set bits
// Algorithm (From Cracking The Coding Interview, 5th Edition) -:
//  1.  Find the position of the rightmost "non-trailing" zero (such that there is atleast one '1' on its right).
//          Let this position be 'p'
//          If there does not exist such a zero, the input is already the largest number possible.
//  2.  Flip the bit at 'p' to 1 from 0.
//  3.  Count the number of zeroes and ones to the right of 'p'.
//          Let that number be c0 and c1 respectively.
//  4.  Set all the bits to the right of 'p' to 0.
//  5.  Set the first (c1-1) bits (starting from the right) to 1.
ULL NextBigger( ULL num )
{
ULL numBak = num;

// Compute c0 and c1
// c0 = Number of zeroes to the right of the rightmost non-trailing zero
size_t c0 = 0;
// c1 = Number of ones to the right of the rightmost non-trailing zero
size_t c1 = 0;
while ( numBak && ( ( numBak & 1 ) == 0 ) )
{
c0++;
numBak >>= 1;
}
while ( ( numBak & 1 ) == 1 )
{
c1++;
numBak >>= 1;
}

// If the input is either 0,
// or of the form "1111..00000",
// then there is no bigger number possible
// Note that for this to work, num should be unsigned
if ( c0 + c1 == 0 || c0 + c1 == ( sizeof( num ) * 8 ) )
{
return 0;
}

// Position of the rightmost non-trailing zero ( starting from the right )
const size_t p = c0 + c1;

// Flip the rightmost non-trailing zero
num |= 1 << p;
// Clear all bits to the right of p
num &= ~( ( 1 << p ) - 1 );
// Insert (c1-1) ones on the right of p
num |= ( 1 << ( c1 - 1 ) ) - 1;

return num;
}

vector<ULL> GenerateSubsets( const size_t& n, const size_t& r )
{
assert( n > 0 );
assert( r > 0 );
assert( n >= r );

vector<ULL> subsets;

// The smallest number having exactly "r" bits set
ULL lowest = ( 1ULL << r ) - 1;
// The biggest number having exactly "r" bits set
ULL highest = lowest << ( n - r );

// The set bits in the binary of "bitMask" denote the positions of the set included in the subset
// This loop should run exactly nCr times
for ( ULL bitMask = lowest; bitMask <= highest; bitMask = NextBigger( bitMask ) )
{
subsets.push_back( bitMask );
}

return subsets;
}

// Extracts the subset indices from the bitmask
vector<size_t> DecodeMask( ULL bitMask )
{
vector<size_t> positions;

size_t i = 0;

while ( bitMask )
{
if ( bitMask & 1 )
{
positions.push_back( i );
}
bitMask >>= 1;
i++;
}

return positions;
}

int main()
{
size_t n = 5;
size_t r = 2;

cout << "Generating subsets of size " << r << "\n";

auto vec = GenerateSubsets( n, r );
cout << "Number of subsets = " << vec.size() << "\n";

// Print the subset indices
for ( size_t i = 0; i < vec.size(); i++ )
{
auto decode = DecodeMask( vec[i] );
for ( size_t j = 0; j < decode.size(); j++ )
{
cout << decode[j] << " ";
}
cout << "\n";
}
}

Теперь мы можем легко изменить это, чтобы генерировать все битовые маски, имеющие по крайней мере «m» биты устанавливаются путем применения вышеуказанного алгоритма с увеличением «m» до «n».

// Rest of the code same as above

int main()
{
size_t n = 5;
size_t m = 2;

for ( size_t r = m; r <= n; r++ )
{
cout << "Generating subsets of size " << r << "\n";
auto vec = GenerateSubsets( n, r );
cout << "Number of subsets = " << vec.size() << "\n";

// Print the subset indices
for ( size_t i = 0; i < vec.size(); i++ )
{
auto decode = DecodeMask( vec[i] );
for ( size_t j = 0; j < decode.size(); j++ )
{
cout << decode[j] << " ";
}
cout << "\n";
}
cout << "\n";
}
}
3

Другие решения


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector