Битовые манипуляции

Ниже приведены наиболее часто используемые битовые операторы:

1. &

Оператор & (И) сравнивает два бита, и если два бита равны 1, возвращается 1, в противном случае возвращается 0. Вот несколько примеров:
1 & 1 = 1
0 & 1 = 0
0 & 0 = 0
0011
0001 &
0001 =

2. |

Оператор | (ИЛИ) сравнивает два бита, и если два бита равны 0, возвращается 0, в противном случае - 1. Вот несколько примеров:
1 | 1 = 1
0 | 1 = 1
0 | 0 = 0
0011
0001 |
0011 =

3. ^

Оператор ^ (XOR) сравнивает два бита, и если два бита различны, он возвращает 1, в противном случае возвращает 0. Вот примеры:
1 ^ 1 = 0
0 ^ 1 = 1
0 ^ 0 = 0
0011
0001 ^
0010 =

4. ~

Оператор ~ (НЕ) изменит битовое значение на обратное. Это означает, что 1 будет 0, а 0 будет 1. Вот несколько примеров.
~ 1 = 0
~ 0 = 1
~ 0011 = 1100

5. ›› и ‹----------------

‹Если мы сдвинем 6 вправо на 1 бит, 0110 ›› 1 = 0011, результат будет 3.
Что будет 1100 ›› 1 быть? После сдвига это будет 1110, поэтому старший бит равен 1. Это связано с тем, что ›› и ‹

После сдвига влево свободный LSB заполняется 0. После сдвига вправо свободный MSB заполняется значением предыдущего MSB.
Для получения более подробной информации об арифметическом и логическом сдвиге вы можете увидеть ссылку внизу этого блога.

Мы всегда используем ‹<, чтобы вставить элемент в массив в Ruby, но когда мы используем его для числа, это будет оператор сдвига влево.

Число, отрицательное число и сложение

Все данные и коды в компьютерах хранятся в двоичной форме. Итак, наши числа в компьютерах - это тоже двоичные данные. Давайте рассмотрим несколько примеров.
Двоичное образование 8 - это 1000, а двоичное образование 9 - 1001. Как мы можем их получить? Вот способ получить двоичное значение.

Алгоритм находит последний бит и добавляет его в строку, а затем возвращает обратную сторону строки. Ruby предоставляет функцию для получения двоичных данных из числа. Вот код.

9.to_s(2)
"1001"

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

30.to_s(16)
"1e"

Мы говорили о положительном числе, но как получить представление отрицательного числа? Мы будем использовать первый бит для знака. Вот пример. Предположим, что у числа 32 бита:
1000 0000 0000 0000 0000 0000 0000 0001 - это число для -1, но проблема все еще есть. Давайте подумаем об операции сложения. Если мы хотим сложить 2 и 3, процесс будет таким, как показано ниже:
0010
0011+
0101 =
Результат 5, сейчас мы делаем 1 плюс -1. Мы знаем, что результат будет нулевым, но когда мы перечисляем уравнение ниже:

1000 0000 0000 0000 0000 0000 0000 0001
0000 0000 0000 0000 0000 0000 0000 0001+
1000 0000 0000 0000 0000 0000 0000 0010=

Результат - -2! Чтобы решить эту проблему, мы используем дополнение до 2, представляющее отрицательное число. Здесь мы будем использовать 1, чтобы получить двоичное образование -1.
Сначала мы получаем ~ 1 (~ - это операция НЕ), а затем получаем двоичные данные:

1111 1111 1111 1111 1111 1111 1111 1110

А потом к этому числу прибавим 1, и получится:

1111 1111 1111 1111 1111 1111 1111 1111

Это двоичное образование для -1. Сейчас давайте попробуем сложить 1 и -1. Вот уравнение:

0000 0000 0000 0000 0000 0000 0000 0001
1111 1111 1111 1111 1111 1111 1111 1111+
0000 0000 0000 0000 0000 0000 0000 0000=

Результат - 0. Дополнение до 2 удобно для сложения, вычитания, умножения, деления и других арифметических операций, поэтому мы используем дополнение до 2 для представления отрицательных чисел.

Примеры манипуляции с битами

Итак, у нас есть базовые знания о битовых операторах и представлении чисел, мы можем делать некоторые интересные битовые манипуляции:

1. Число умноженное на 2 или разделенное на 2

Общий подход к этому:

Здесь мы можем использовать операцию сдвига для этого:

Когда мы сдвигаем число влево на 1 бит, это то же самое, что и умножение на 2. Правый сдвиг предназначен для делений. Далее, мы можем умножить число, являющееся степенью двойки, с помощью сдвига:

10 сдвигов, оставшихся на 3 бита, равны 10 умноженным на 2 степени 3. То есть 10 умноженным на 8, что равно 80.

2.Проверьте, является ли число степень двойки или нет

Как мы знаем, если число является степенью 2, это означает, что число имеет только один бит единицы. Остальные биты - 0. Например, 2 равно 10, 4 равно 100, 8 равно 1000 и так далее.
Менее изощренное решение этой проблемы состоит в том, что мы сдвигаем число вправо, а затем подсчитываем биты, которые равны 1. Вот код.

def powerOfTwo?( number )
  return false if number == 0
  count = 0
  while( number > 0 )
    count += (number & 1)
    number >>= 1
  end
  return count == 1
end
powerOfTwo?(16)
true
powerOfTwo?(14)
false

Но есть ли более эффективное решение? Вот и вся магия битовых манипуляций. Мы знаем, что в числе есть только один бит, равный степени 2. В данном примере мы используем 16.
Мы будем использовать 16 для вычитания 1.
10000
00001-
01111 =
Мы видим, что все биты за битом 1 становятся 0. Что будет, если использовать в & 16? Да, он станет 0, поэтому решение будет показано ниже:

def powerOfTwo?( number )
  number && ( ( number & ( number - 1 ) ) == 0 )
end
powerOfTwo?(16)
true
powerOfTwo?(14)
false

Круто, однострочный код! Вы можете попробовать это сами.

3. Поменять местами два числа

Мы можем поменять местами два числа через временную переменную.

a = 10
b = 20
temp = a
a = b
b = temp
puts a, b
20 10

Но если мы не можем использовать временную переменную, как мы можем решить эту проблему? В операции ^ (XOR) есть важная особенность. Если мы ^ (XOR) одно и то же число два раза, оно станет исходным числом.

a = 10
a = a ^ 88
puts a
82
a = a ^ 88
puts a
10

Используя эту функцию, мы можем изменять числа без использования временной переменной.

a = 10
b = 20
a = a ^ b
b = a ^ b
a = a ^ b
puts a, b
20, 10

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

4. Представление данных

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

Мы знаем, что в колоде 52 карты, 13 типов карт и 4 типа мастей. Мы можем использовать 4 старших бита для представления чисел и 4 младших бита для представления мастей.

В предыдущие годы компьютерной памяти было мало. Поэтому программисты всегда устанавливают данные для каждого бита, чтобы уменьшить использование памяти. Предположим, что целое число имеет ширину 4 байта, поэтому оно имеет 32 бита. Если диапазон нашего числа составляет 0000 ~ 1111 (0 ~ 15, ширина 4 бита), это означает, что мы можем преобразовать 8 чисел в одно целое.

Заключение

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

Источники

Блог о битовых манипуляциях
Вики по битовым манипуляциям
Арифметический сдвиг
Логический сдвиг вики
Логический против. Арифметический сдвиг
2 в Википедии