Обратный ИЛИ Алгоритм? - PullRequest
Новая
       10

Обратный ИЛИ Алгоритм?

2 голосов
/ 14 октября 2011

Позвольте мне сначала описать мою ситуацию.

У меня есть список шестнадцатеричных значений, которые называются BaseID. Они выбираются таким образом, чтобы логическое ИЛИ между любым их числом давало вам уникальный идентификатор , который называется FinalID. То есть мои значения BaseID следующие:

BaseID = {0x01, 0x02, 0x04, 0x08, 0x10, ...}

Критическим моментом является то, что я не знаю, сколько BaseIDs у меня будет до запуска программы (я получаю список BaseID после запуска программы, когда она читается из файл), или сколько из общего числа BaseID будет использовано для создания FinalID . Это решается на основе других частей моей программы. Например, ниже приведены два FinalID, которые могут быть в моей программе.

FinalID = (0x01 | 0x04) = 0x05

FinalID = (0x02 | 0x04 | 0x10) = 0x16

Теперь, использование операции OR для любого количества BaseIDs является легкой частью. Моя проблема заключается в том, что мне нужно извлечь из FinalID BaseID, используемые для создания этого FinalID. Поскольку я выбрал BaseID так, чтобы они, после использования операции OR, ВСЕГДА давали мне уникальный FinalID, я знаю, что любой данный FinalID создается с использованием определенного набора BaseID. Обратите внимание, что FinalID может быть создан с использованием только одного BaseID, что эквивалентно FinalID = (BaseID | 0x00).

Я знаю, что мне нужно сделать, чтобы извлечь BaseID, используемые для создания любого конкретного FinalID; Мне нужно получить полный список задействованных BaseID, а затем использовать оператор ИЛИ для каждого сочетания элементов, чтобы выяснить, дает ли какая комбинация конкретный FinalID.

Однако мне трудно преобразовать эту логику в программу. Я использую C # с .NET 3.5 Framework. Любые предложения / идеи будут очень цениться. Пример кода высоко ценится.

Заранее спасибо!

Ответы [ 5 ]

7 голосов
/ 14 октября 2011

Итак, у вас есть битовая маска ... все, что вам нужно сделать, это "И" ваш FinalID с каждым возможным BaseID - если результат не равен нулю, этот BaseID внесен в FinalID: 

// Or just go from 0... count and use 1 << x
foreach (int baseId in BaseIDs)
{
    if ((baseId & finalId) != 0)
    {
        ...
    }
}

Я бы также предположил, что вы можете использовать для этого перечисление «flags», которое упростит вашу жизнь с точки зрения языковой интеграции.

3 голосов
/ 14 октября 2011

Вот мое предложение: 

        uint mask = 0x1;

        do
        {
            if ((finalId & mask) == mask)
            {
                // Base-ID found
            }
            mask <<= 1;
        }
        while (mask < finalId);
2 голосов
/ 14 октября 2011

Если у вас есть список всех BaseID, то выполнение И с FinalID должно сказать вам, использовалось оно или нет.

Логика 

Assume allBaseIds are sorted from lower to higher
For each (var baseId in allBaseIds)
{
   // FinalId will always be greater then consisting baseIds
   if(finalId < baseId)
     break;

   // As each base id represents a different bit, so its AND should result in baseId itself.
   if((finalId AND baseId) == baseId)
   {
      // This base id was used to make this final id.
   }
   else
   {
     // this base id was not used to make this final id
   }
}
2 голосов
/ 14 октября 2011

Позвольте мне попробовать ... 

foreach(Id baseID in baseIDs)
{
    if(baseID & finalID != 0)
        results.Add(candidate);
}

Должен делать хорошо.

2 голосов
/ 14 октября 2011 
var baseId = new int[] { 0x01, 0x02, 0x04, 0x08, 0x10 };
var finalId = 0x01|0x02|0x10;

foreach (var b in baseId)
{
    if ((finalId & b) == b)
    {
        Console.WriteLine(b);
    }
}

Я добавлю, что с помощью int вы можете иметь до 32 baseId, а с помощью long вы можете иметь до 64 baseId. Теоретически, используя класс BigInteger, вы можете подняться так высоко, как захотите.

...