Рубрики

Копировать установленные биты в диапазоне

Даны два числа x и y и диапазон [l, r], где 1 Вход: x = 10, y = 13, l = 2, r = 3 Выход: x = 14 Двоичное представление 10 равно 1 01 0 и y равен 1 10 1. В 3-й позиции (в данном диапазоне) имеется один установленный бит в y. После того, как мы скопируем этот бит в x, x становится 1 11 0, который является двоичным представлением 14. Вход: x = 8, y = 7, l = 1, r = 2 Выход: x = 11

Источник: DE Shaw Интервью

Метод 1 (Один за другим копировать биты)
Мы можем один за другим найти установленные биты y, пройдя заданный диапазон. Для каждого установленного бита мы ИЛИ обращаемся к нему с существующим битом x, чтобы он стал установленным в x, если он не был установлен. Ниже приведена реализация C ++.

// C ++ программа для перестановки массива поочередно
// C ++ программа для копирования набора битов в заданном
// диапазон [l, r] от y до x.
#include <bits/stdc++.h>

using namespace std;

  
// Копировать установленные биты в диапазоне [l, r] из y в x.
// Обратите внимание, что x передается по ссылке и изменяется
// по этой функции.

void copySetBits(unsigned &x, unsigned y,

                 unsigned l, unsigned r)

{

   // l и r должны быть от 1 до 32

   // (предполагается, что целые хранятся с использованием

   // 32 бита)

   if (l < 1 || r > 32)

      return ;

  

   // Траверс в заданном диапазоне

   for (int i=l; i<=r; i++)

   {

       // Найти маску (число, чье

       // только установленный бит находится в i-й позиции)

       int mask = 1 << (i-1);

  

       // Если i бит установлен в y, установить i

       // бит в х тоже.

       if (y & mask)

          x = x | mask;

   }

}

  
// Код драйвера

int main()

{

   unsigned x = 10, y = 13, l = 2, r = 3;

   copySetBits(x, y, l, r);

   cout << "Modified x is " << x;

   return 0; 

}

Выход :

Modified x is 14

Способ 2 (Скопировать все биты, используя одну битовую маску)

// C ++ программа для копирования набора битов в заданном
// диапазон [l, r] от y до x.
#include <bits/stdc++.h>

using namespace std;

  
// Копировать установленные биты в диапазоне [l, r] из y в x.
// Обратите внимание, что x передается по ссылке и изменяется
// по этой функции.

void copySetBits(unsigned &x, unsigned y,

                 unsigned l, unsigned r)

{

    // l и r должны быть от 1 до 32

    if (l < 1 || r > 32)

        return ;

  

    // получаем длину маски

    int maskLength = (1<<(r-l+1)) - 1;

  

    // смещаем маску в нужное положение

    // "&" с y, чтобы получить биты между

    // l ad r in y

    int mask = ((maskLength)<<(l-1)) & y ;

    x = x | mask;

}

  
// Код драйвера

int main()

{

   unsigned x = 10, y = 13, l = 2, r = 3;

   copySetBits(x, y, l, r);

   cout << "Modified x is " << x;

   return 0;

}

Выход :

Modified x is 14

Спасибо Ашишу Рати за предложение об этом решении в комментарии.

Эта статья предоставлена Риши . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Копировать установленные биты в диапазоне

0.00 (0%) 0 votes