Проверка валидности битовой маски

Опубликовано Nov 25, 2011 в Манипуляция битами | 26 коммент.

, , ,

32-х битная “маска” считается действительной, если ее двоичное представление содержит непрерывный ряд “1″ и следующий за ним ряд “0″.

Пример правильных битовых масок:              Пример неправильных битовых масок:

11110000000000000000000000000000              10110000000000000000000000001000
11111000000000000000000000000000              01111100000000000000001000000001
11111111111100000000000000000000

Задача – разработать функцию проверки правильности битовой маски.

С++:                                       C#
bool isValidBitMask(DWORD mask)            bool isValidBitMask(System.Int32 mask)
{                                          {
    // ваш код                                   // ваш код
}                                          }

Для энтузиастов можно усложнить задачу, добавив требование о запрете на использование цикла.

Критерии оценки FulcrumWeb:

Кандидат должен продемонстрировать навыки работы с битовым представлением чисел, а также умение придумать и реализовать нужный алгоритм.

Ожидаемые вопросы:

  1. Будет ли валидной битовая маска 00111111111100000000000000000000? То есть, обязана ли валидная битовая маска начинаться с единицы (и заканчиваться нулем)?
  2. Я вижу в этой задачи эффективный способ использования хардкода. Есть ли ограничения на это?

Оценка результатов:

Никаких особых знаний, приобретаемых с опытом, для задачи не нужно. Изюминкой является видение варианта с введением хардкода при положительном ответе на первый вопрос и понимание того, что в данной задаче этот "нехороший" прием может быть оправданным.
Так же существует "идеальное" решение данной задачи, содержащие всего три простых битовых операции и одну операцию сравнения, но это уже ближе к постановке задач на олимпиадах.


26 Коммент. : “Проверка валидности битовой маски”

  1. Будет ли валидной битовая маска 00111111111100000000000000000000? То есть обязана ли валидная битовая маска начинаться с единицы?
    Если да – то этих масок имеется всего 31. Их можно просто захардкодить – 2^31, 2^31+2^30, 2^31 + 2^30 + 2^29, … 2^31+2^30, 2^31 + 2^30 + 2^29 +…+ 2^2 + 2^1. Будет ли это решением без циклов?

    • Да, с 1 начинается. Ряд 1 и потом 0, лидирующие 0 не упомянуты.
      Так очевидно что их 32, при 64 битах 64 и т.д.

      Захардкодить 32 варианта можно = решение (32 такта на сравнение + 32 такта на сумму для процессора )
      Можно в цикле сдвигать – больше тактов меньше кода
      Можно просто в 3 простых битовых операции + одно сравнение сделать = нужно подумать

      Я допишу что без цикла в менее 10-ти тактов процессора.

  2. Дмитрий says:

    Я не программист, но стало интересно.
    Мне кажется тут нужно сделать инверсию, сдвиг на 1 бит и применить исключающее ИЛИ. То есть, если в результате исключающего ИЛИ для Маски и сдвинутой на 1 бит инвертированой маски получается 1, то маска правильная… Так?

    • Дмитрий says:

      нет, не так )

      • Дмитрий says:

        побитное исключающее ИЛИ для маски, и маски сдвинутой на 1 бит должно дать две единицы (остальные нули) в результате для правильной маски. но это даст только гарантию одной непрерывной серии “1″ в маске… которая может быть в середине, например…

        • Дмитрий says:

          Не совсем так, но что то вырисовывается.
          “Правильная” маска даст одну единицу (остальные нули) при
          mask ^ (mask >> 1).
          А вот как определить что там только одна “1″ пока не придумал ;-) .

  3. Vladimir says:

    Решил на скорость по логике, в любом случае это из разряда “есть один оптимальный алгоритм” как с копированием строк в С и т.п.

    bool isValidBitMask(DWORD mask) {
        int nBitCount = 8 * sizeof(DWORD);
        DWORD uShift = 1 < 0 && bRet; i--) {
            uShift >>= 1;
     
            if (mask & uShift) {
                if (bFindZero)
                    bRet = false;
            } else {
                bFindZero = true;
            }
        }
     
        return bRet;
    }
  4. Trusov Denis says:

    А я б такой вариант предложил для обеих озвученных задач.

    bool isValidBitMask(dword mask)
    {
    return ((((mask + 1) & mask) == 0));//&&((mask&0x80000001)==1));
    }

    bool isValidBitMask2 (dword mask)
    {
    return isValidBitMask(~(~mask&-mask));
    }

  5. Ну, на первый взгляд, должен сработать следующий алгоритм:
    (X>>1|X)<<1==X.

  6. Да и на второй взгляд тоже ))
    То, что в случае валидной маски результатом будет true – довольно очевидно, а вот что true не всплывет внезапно в других случаях нужно доказать.
    Вот такое придумал доказательство -
    Легко заметить, что маска является невалидной тогда и только тогда, когда в ней есть пара 01. (рядом стоящие 0 и 1)
    а если в числе X есть пара 01 где либо, то код (X>>1|X)<<1 в этой паре меняет ноль на единицу. В этих случаях сравнение с исходным X выдаст false.

  7. Олег says:

    Исключительно для первого случая получилось проверку уместить в одну строку:
    bool test_mask1(unsigned int mask)
    {
    return (!(mask&1))?(((((mask>>1)^mask)<<1)|mask)==mask):(mask==0xFFFFFFFF);
    }
    другое дело что поддерживать такую строку кода я бы сам не хотел.

    Второй случай немного сложнее.

  8. Олег says:

    Юрий, опередили ) только проверка нулевого бита нужна, потому что при сдвиге вправо выскочит 0, и если изначально там была единица, то равенства не получится.
    А, хотя возможно что битовая маска из всех единиц тоже не является валидной, тогда дополнительная проверка не нужна.

    • Да. Точно!
      Протупил…с маской со всеми единицами не сработает.
      Но, подумав, нашел другое решение. Тоже три операции и, похоже, оно покрывает все случаи:
      (X<<1)&X==X<<1
      Подобно прошлой формуле это равенство обеспечивает чтобы за нулем не шла единица. Разница в том, что тут теряем старший бит, а он-то как раз для нас значения не имеет – он может быть любым.

    • Или еще элегантнее ))
      еще раз – битовая маска А1….Аn валидна тогда и только тогда, когда для всех k=2..n Аk-1==0 => Ak=0
      Преобразуем импликацию Аk-1==0 => Ak=0 и получим, что для выполнения условия валидности необходимо выполнение условия ~Ak-1&Ak==0 разумеется для всех k=2..n
      Отсюда другая формула:
      ~X&(X<<1)==0

      • Олег says:

        Браво! Чем еще хорошо это решение, так это тем, что мы получаем 1 в тех позициях, где в исходной битовой маске нули окруженные единицами. Эта новая “маска” может иметь применение в какой либо конкретной задаче.

        • Олег says:

          Хотя нет, поспешил. Если больше одного нуля подряд то не получится такой маски.

  9. (x<<1)|==x
    тоже подходит.

  10. Способы, приведенные выше, конечно же эффективны. Однако они сложны для понимания на мой взгляд. Поэтому показываю своё “пионерское” творение:

    bool IsValidBitMask(int mask)
    {
    	if(mask == 0)
    	{
    		return false;
    	}
    	int prevSymbol = (mask & 1);	// get the first right symbol
    	int curSymbol;
    	mask = mask >> 1;
    	while(mask != 0)
    	{
    		curSymbol = (mask & 1);
    		if((prevSymbol == 1) && (curSymbol == 0))
    		{
    			return false;
    		}
    		prevSymbol = curSymbol;
    		mask = mask >> 1;
    	}
    	return true;
    }

    Способ работает при наличии незначащих нулей слева.
    Ну и на всякий случай код, которым я это дело тестировал.

    #include <vector>
    #include <cmath>
    #include <string>
    #include <iostream>
    using namespace std;
    static const int BITS_PER_BYTE = 8;
    int BitStrToInt(string bitStr)
    {
    	int intNumber = 0;
    	for(int symbIdx = bitStr.length()-1, num = 0; symbIdx >= 0; symbIdx--, num++)
    	{
    		if(bitStr[symbIdx] == '1')
    		{
    			intNumber += pow(static_cast<double>(2), num);
    		}
    	}
    	return intNumber;
    }
    int main()
    {
    	cout << "Please, enter a bit mask and I'll validate it." << endl
    		<< "To stop input enter the \"0\" string:" << endl;
    	string strMask;
    	vector<string> strContainer;
    	do
    	{
    		getline(cin, strMask);
    		strContainer.push_back(strMask);
    	}while(strMask != "0");
    	strContainer.pop_back();	// exclude the last meaningless "0"
    	int curIntMask;
    	for(int i = 0; i < strContainer.size(); i++)
    	{
    		curIntMask = BitStrToInt(strContainer[i]);
    		if(IsValidBitMask(curIntMask))
    		{
    			cout << "Bit mask " + strContainer[i] + " is valid" << endl;
    		}
    		else
    		{
    			cout << "Bit mask " + strContainer[i] + " is not valid" << endl;
    		}
    	}
    	cin.get();
    	return 0;
    }
  11. Три простых битовых операции и одна операция сравнения:

    bool isValidBitMask(DWORD mask)
    {
    	if((mask&((mask)^(mask>>1))) == 0x80000000)
    		return true;
    	return false;
    }
  12. Операций больше, но должно работать.

    bool isValid(__int32 a) {
        __int32 msk = (a >> 1) & (~a);
        return !(msk & (msk - 1));
    }
    • Получилось решение с тремя битовыми операциями и одной арифметической.
      bool isValid2(__int32 a) {
      //обнуляем младший бит и сдвигаем маску
      __int32 nl = (a & (a – 1)) >> 1;
      return (nl & a) == nl;
      }

Оставить комментарий

Ваш адрес email не будет опубликован.


*