Низкоуровневая техника для решения проблем

Решайте проблемы программирования с помощью одной из самых популярных низкоуровневых техник


Манипулирование битами и побитовые операторы

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

Есть очень впечатляющий трюк, который может помочь вам в решении проблем 😎


Что такое побитовые операторы?

  1. Оператор & (побитовое AND) в C или C++ принимает два числа в качестве операндов и выполняет AND над каждым битом двух чисел. Результат AND равен 1, только если оба бита равны 1.
  2. | (побитовое ИЛИ) в C или C++ принимает два числа в качестве операндов и выполняет ИЛИ над каждым битом двух чисел. Результат OR равен 1, если любой из двух битов равен 1.
  3. ^ (побитовое XOR) в C или C++ принимает два числа в качестве операндов и выполняет XOR над каждым битом двух чисел. Результат XOR равен 1, если два бита различны.
  4. << (сдвиг влево) в C или C++ принимает два числа, сдвигает влево биты первого операнда, а второй операнд определяет количество мест для сдвига.
  5. >> (правый сдвиг) в C или C++ принимает два числа, правый сдвигает биты первого операнда, а второй операнд определяет количество мест для сдвига.
  6. ~ (побитовое НЕ) в C или C++ берет одно число и инвертирует все его биты.

Давайте узнаем, как это работает, на примере

Представьте себе, что каждое число, с которым вы будете иметь дело, будет переведено в двоичную систему счисления
и если вы знакомы с цифровыми схемами, вам будет очень легко понять, как они работают.

Пример №1


int main(){
        // a = 5(00000101), b = 9(00001001)
    int a = 5, b = 9;
    // The result is 00000001
    cout<<"a = " << a <<","<< " b = " << b <<endl;
    cout << "a & b = " << (a & b) << endl;

}
Вход в полноэкранный режим Выход из полноэкранного режима
  • введем пример правила 0 ложно1 истинно каждое число при печати будет снова преобразовано в десятичную дробь.

Пояснение #1

Оператор & работает так, что если два случая равны 1, он вернет 1
так что
1&1 = 1
1&0 = 0
0&1 = 0
0&0 = 0

Пример №1

a = 5, в двоичном исчислении это будет 00000101

b = 9, в двоичном виде это будет 00001001

поэтому мы берем каждую цифру и применяем наше правило &.

1 & 1 = 1, и так далее…

поэтому результат будет a & b = 00000001.


Пример #2

// The result is 00001101
    cout << "a | b = " << (a | b) << endl;
Вход в полноэкранный режим Выход из полноэкранного режима

Пояснение #2

Оператор | работает, если один из случаев равен 1, он вернет 1
1|1 = 1
1|0 = 1
0|1 = 1
0|0 = 0

Пример №2

a = 5, в двоичном исчислении это будет 00000101

b = 9, в двоичном виде это будет 00001001

Поэтому мы берем каждую цифру и применяем наше правило

1 | 1 = 1, и так далее…

в результате получим a | b = 00001101.


Пример #3

// The result is 00001100
    cout << "a ^ b = " << (a ^ b) << endl;
Вход в полноэкранный режим Выход из полноэкранного режима

Пояснение #3

Оператор ^ немного запутанный, он работает, если два числа разные, то возвращает 1
1^1 = 0
1^0 = 1
0^1 = 1
0^0 = 0

Пример #3

a = 5, в двоичном исчислении это будет 00000101

b = 9, в двоичном виде это будет 00001001

берем каждую цифру и применяем наше правило ^.

1 ^ 1 = 0, и так далее…

Таким образом, результат будет a ^ b = 00001100 = 12 в десятичной системе.


Пример #4

// The result is 11111010
    cout << "~a = " << (~a) << endl;
Вход в полноэкранный режим Выход из полноэкранного режима

Объяснение #4

Оператор ~ получает противоположное число, поэтому,
~1 = 0
~0 = 1

Пример #4

a = 5, в двоичном виде это будет 00000101

поэтому мы берем каждую цифру и применяем наше правило ~.

~1 = 0, и так далее…

Таким образом, результат будет ~a = 11111010 = -6 в десятичной системе счисления слишком сложно преобразовать его в десятичную систему с помощью основных правил, поэтому ищите дополнение 2, дополнение 1 и знаковая величина

имейте в виду — последняя левая цифра представляет положительное = 0 или отрицательное = 1, когда вы применяете этот оператор, вы должны добавить +1 к результату, если вы хотите получить отрицательное значение числа.


Пример #5

// b=9 (00001001)
// The result is 00010010
    cout<<"b << 1" <<" = "<< (b << 1) <<endl;

    // The result is 00000100
    cout<<"b >> 1 "<<"= " << (b >> 1 )<<endl;
Вход в полноэкранный режим Выход из полноэкранного режима

Пояснение #5

Оператор << сдвигает битовый шаблон на n раз влево, что в нашем случае n=1, и добавляет 0 в конец числа, сдвиг влево эквивалентен умножению битового шаблона на $2^n$.
 (если мы сдвигаем n битов).
1 = 00000001
1 << 1 = 00000010 = 2 = $(1*2^1)$ и так далее …
в примере
9 << 1 = 00010010 = $(9 * 2^1)$ = 18


Оператор >> сдвигает битовый шаблон на n раз вправо, что в нашем случае n=1, и добавляет 1 в конец числа, сдвиг влево эквивалентен делению битового шаблона на $2^n$.
 (если мы сдвигаем n бит). Помните, что двоичная система счисления не имеет плавающих точек в этом случае
4 = 00000100
4 >> 1 = 00000010 = 2 = $(4/2^1)$

5 = 00000101
6 >> 1 = 00000010 = 2 = $(5/2^1)$ в десятичной системе и так далее …

в примере

9 >> 1 = 00000100 = 4 = $( 9/2^n )$ в десятичной системе счисления.


Давайте узнаем, как работает манипуляция битами на примере

и почему это так полезно для оптимизированного решения, это работает как волшебство 🪄

Начнем с простого примера

мы хотим узнать, является ли x степенью 2

реализация

bool isPowerOfTwo(int x)
    {
        if(x == 0)
            return false;
        else
        {
            while(x % 2 == 0) x /= 2;
            return (x == 1);
            }
    }
Вход в полноэкранный режим Выйти из полноэкранного режима

Приведенный выше код имеет временную сложность O(log N).


Существует ли оптимальный подход?

Ту же задачу можно решить с помощью манипуляций с битами.

Рассмотрим число x, которое нужно проверить на то, что оно является показателем степени 2.

Теперь подумайте о двоичном представлении (x-1).

В (x-1) все биты такие же, как и в x, за исключением крайней правой 1 в x и всех битов справа от крайней правой 1.

Пусть, x = 4 = (100)2 x — 1 = 3 = (011)2

Пусть, x = 6 = (110)2 x — 1 = 5 = (101)2

Эти примеры могут показаться неочевидными, но двоичное представление (x-1) можно получить, просто перевернув все биты справа от крайней правой 1 в x, а также включая крайнюю правую 1.

Теперь подумайте о x & (x-1).

x & (x-1) будет иметь все биты, равные x, за исключением самой правой 1 в x.

Пусть, x = 4 = (100)2 x — 1 = 3 = (011)2 x & (x-1) = 4 & 3 = (100)2 & (011)2 = (000)2

Пусть, x = 6 = (110)2 x — 1 = 5 = (101)2 x & (x-1) = 6 & 5 = (110)2 & (101)2 = (100)2

в x = 6, 6 не является степенью 2, поэтому, когда x & (x-1) = (100)2, это означает, что это не то, что мы хотим.

Свойство чисел, являющихся степенью 2, состоит в том, что в их двоичном представлении установлен один и только один бит.

Если число не является ни нулем, ни степенью двойки, оно будет иметь 1 в более чем одном месте. Так, если x — степень 2, то x & (x-1) будет 0.

Реализация:

bool isPowerOfTwo(int x)
    {
        // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
        return (x && !(x & (x - 1)));
    }
Вход в полноэкранный режим Выход из полноэкранного режима

и приведенный выше код имеет временную сложность O(1).


Еще один сложный пример, чтобы увидеть, насколько мощным является манипулирование битами

Учитывая строковый массив words
, верните максимальное значение
 length(word[i]) * length(word[j])
 где два слова не имеют общих букв
. Если таких двух слов не существует, возвращается 0.


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

Объяснение битовой маски

-Допустим, у нас есть три строки «abc», «def» и «abde», соответствующие битмаски этих строк будут «111», «111000» и «11011». как?

Для каждого символа нам нужно найти индекс, в котором нужно установить 1 в нашей битовой маске. Так, для символа «a» индекс будет 0, для «b» — 1, для «c» — 2 и так далее.

Индекс можно легко найти, вычитая каждый символ на ‘a’ Ex.

'a' - 'a' = 0
'b' - 'a' = 1
'c' - 'a' = 2
Войти в полноэкранный режим Выход из полноэкранного режима

Следующий шаг — сдвиг влево на 1 на значение индекса.

for 'a', index will be 0
1 << 0 = 1

'b', index will be 1
1 << 1 = 10

'c', index will be 2
1 << 2 = 100

Вход в полноэкранный режим Выход из полноэкранного режима

После сдвига последним шагом будет ИЛИ сдвинутого значения текущего символа с битовой маской текущей строки. Так, если мы выполним ИЛИ сдвинутых значений символов «a», «b» и «c».

001 | 010 | 100 = 111

Проверка наличия общих символов — Если две строки s1 и s2 имеют общие символы, то они будут иметь 1 в одном и том же индексе в битовой маске, и если мы выполним AND битовых масок s1 и s2, то в результате получим значение больше 0.

bitmask[s1] & bitmask[s2] = 0, if no common characters
                            >0, otherwise

Ex. bitmask of "abc" and "def" is 111 and 111000, respectively.

111 & 111000 = 0, hence no common characters

bitmask of "abc" and "abde" is 111 and 11011, respectively.

111 & 11011 = 00011 > 0, hence common characters found

Вход в полноэкранный режим Выход из полноэкранного режима

Наконец, код —

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] bitmask = new int[n];
        int max = 0;

        for(int i=0; i<n; i++) {
            // Calculate bitmask for current word
            for(int j=0; j<words[i].length(); j++) {
                // index will be - for a -> 0, b -> 1, c -> 2 and so on
                int index = words[i].charAt(j) - 'a';

                // left shift 1 by index and OR it with the current bitmask
                bitmask[i] |= (1 << index);
            }

            // Compare bitmask of current string with previous strings bitmask
            for(int j=0; j<i; j++) {
                /* If there is a 1 at the same index of current string {i} and {j},
                then bitmask of i and j string will result in a number greater than 0,
                else it will result in 0 */
                if( (bitmask[i] & bitmask[j]) == 0 )
                    max = Math.max(max, words[i].length()*words[j].length());
            }
        }

        return max;
    }
}

Вход в полноэкранный режим Выход из полноэкранного режима

Временная сложность = O(n.(k+n))

Оцените статью
Procodings.ru
Добавить комментарий