Рубрики

Побитовые хаки для конкурентного программирования

Рекомендуется ссылаться на Интересные факты о побитовых операторах в качестве предварительного условия.

1. Как установить бит в число «num»:

Если мы хотим установить бит в n-й позиции числа «num», это можно сделать с помощью оператора «ИЛИ» (|).

  • Сначала мы сместили «1» в положение n через (1 << n)
  • Затем используйте оператор «ИЛИ» для установки бита в этой позиции. Используется оператор «ИЛИ», потому что он будет устанавливать бит, даже если бит был ранее не установлен в двоичном представлении числа «num».

#include<iostream>

using namespace std;

// num это число, а pos это позиция
// на котором мы хотим установить бит.

void set(int & num,int pos)

{

     // Первый шаг - сдвиг '1', второй

     // шаг побитовый ИЛИ

     num |= (1 << pos);

}

int main()

{

     int num = 4, pos = 1;

     set(num, pos);

     cout << (int)(num) << endl;

     return 0;

}

Выход:

6

Мы передали параметр «вызов по ссылке», чтобы внести постоянные изменения в номер.

2. Как убрать / очистить бит на n-й позиции в числе 'num':

Предположим, что мы хотим сбросить бит в n-й позиции числа num, тогда мы должны сделать это с помощью оператора AND (&).

  • Сначала мы оставили смещение «1» на позицию n с помощью (1 << n), а затем использовали побитовый оператор NOT «~», чтобы сбросить это смещенное «1».
  • Теперь, после очистки этого левого смещения «1», т. Е. Сделав его «0», мы получим «И» (&) с номером «num», который будет сбрасывать бит в n-й позиции.

#include <iostream>

using namespace std;

// Первый шаг - получить число, которое имеет все 1, кроме заданной позиции.

void unset(int &num,int pos)

{

    // Второй шаг - побитовое и это число с заданным номером

    num &= (~(1 << pos));

}

int main()

{

    int num = 7;

    int  pos = 1;

    unset(num, pos);

    cout << num << endl;

    return 0;

}

Выход:

5

3. Немного переключиться на n-ю позицию:

Переключение означает включение бита «вкл.» (1), если он был «выключен» (0), и отключение «выключения» (0), если он был «вкл.» (1) ранее. Здесь мы будем использовать оператор «XOR», который это '^'. Причина оператора 'XOR' заключается в его свойствах.

  • Свойства оператора XOR.
    • 1 ^ 1 = 0
    • 0 ^ 0 = 0
    • 1 ^ 0 = 1
    • 0 ^ 1 = 1
  • Если два бита различны, то оператор «XOR» возвращает установленный бит (1), иначе он возвращает неустановленный бит (0).

#include <iostream>

using namespace std;

// Первый шаг - сдвиг 1, Второй шаг - XOR с заданным номером

void toggle(int &num,int pos)

{

    num ^= (1 << pos);

}

int main()

{

    int num = 4;

    int pos = 1;

    toggle(num, pos);

    cout << num << endl;

    return 0;

}

Выход:

6

4. Проверка, установлен ли бит в n-й позиции или не установлен:

Это довольно легко сделать с помощью оператора «И».

  • Сдвиньте «1» влево на заданную позицию, а затем «И» («&»).

#include <iostream>

using namespace std;

  

bool at_position(int num,int pos)

{

    bool bit = num & (1<<pos);

    return bit;

}

  

int main()

{

    int num = 5;

    int pos = 0;

    bool bit = at_position(num, pos);

    cout << bit << endl;

    return 0;

}

Выход:

 1 

Заметьте, что мы сначала сместили влево «1», а затем использовали оператор «И», чтобы получить бит в этой позиции. Таким образом, если в позиции 'pos' в 'num' есть '1', то после 'AND' наша переменная 'bit' будет хранить '1', если в позиции 'pos' в числе 'num' есть '0' чем после 'И' наш бит переменной будет хранить '0'.

Еще несколько быстрых хаков:

  • Инвертирование каждого бита числа / 1 дополнения:

    Если мы хотим инвертировать каждый бит числа, т.е. заменить бит «0» на «1», а бит «1» на «0». Мы можем сделать это с помощью оператора «~». Например: если число равно num = 00101100 (двоичное представление), то «~ num» будет «11010011».

Это также 1-е дополнение числа.

#include <iostream>

using namespace std;

int main()

{

    int num = 4;

  

    // инвертируем каждый бит числа num

    cout << (~num);

    return 0;

}

Output:
 -5
  • Дополнение числа к двум: дополнение числа к 2 — это дополнение к 1 + 1.

Таким образом, формально мы можем получить дополнение 2, найдя дополнение 1 и добавив 1 к результату, т.е. (~ num + 1), или что еще мы можем сделать, это использовать оператор «-».

#include <iostream>

using namespace std;

int main()

{

    int num = 4;

    int twos_complement = -num;

    cout << "This is two's complement " << twos_complement << endl;

    cout << "This is also two's complement " << (~num+1) << endl;

    return 0;

}

Выход:

This is two's complement -4
This is also two's complement -4
  • Снятие младшего установленного бита:

Во многих ситуациях мы хотим убрать младший установленный бит, например, в структуре данных дерева с двоичным индексом, считая количество установленных бит в числе.

Мы делаем что-то вроде этого:

 X = X & (X-1) 

Но как это вообще работает?

Давайте посмотрим на это на примере, пусть X = 1100.

(X-1) инвертирует все биты до тех пор, пока не встретит младший набор «1», а также инвертирует этот младший набор «1».

X-1 становится 1011. После 'ANDing' X с X-1 мы получаем самый низкий установленный бит.

#include <iostream>

using namespace std;

void strip_last_set_bit(int &num)

{

    num = num & (num-1);

}

int main()

{

    int num = 7;

    strip_last_set_bit(num);

    cout << num << endl;

    return 0;

}

Выход:

6
  • Получение младшего установленного бита числа:

Это делается с помощью выражения 'X & (- X)'. Рассмотрим это на примере: пусть X = 00101100. Таким образом, ~ X (дополнение 1) будет '11010011', а дополнение 2 будет (~ X + 1 или -X) то есть '11010100'. Так что, если мы 'И' имеем исходное число 'X' с дополнением к его двум, которое является '-X', мы получим младший установленный бит.

00101100
& 11010100
-----------
00000100

#include <iostream>

using namespace std;

int lowest_set_bit(int num)

{

    int ret = num & (-num);

    return ret;

}

int main()

{

    int num = 10;

    int ans = lowest_set_bit(num);

    cout << ans << endl;

    return 0;

}

Выход:

2

Битовые хитрости для конкурентного программирования

Обратитесь к статьям операторов BitWise для получения дополнительных статей о бит-хаки.

Эта статья предоставлена Панкаджем Мишрой . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Побитовые хаки для конкурентного программирования

0.00 (0%) 0 votes