Имеют ли побитовые операторы (кроме сдвигов) математический смысл в base-10?

Question

Согласно вики сдвиги могут использоваться для расчета степеней 2:

Арифметический сдвиг влево на n равен эквивалентно умножению на 2 ^ n (при условии, что значение не переполнение), в то время как правильная арифметика сдвиг на п значения дополнения до двух эквивалентно делению на 2 ^ n и округление до отрицательной бесконечности.

Мне всегда было интересно, имеют ли какой-либо другой побитовый оператор (~, |, &, ^) какой-либо математический смысл применительно к base-10? Я понимаю, как они работают, но можно ли использовать результаты таких операций для вычисления чего-нибудь полезного в десятичном мире?

Answer 1

"yep base-10 is what I mean"

В этом случае, да, они могут быть расширены до base-10 несколькими способами, хотя они не так полезны, как в двоичном.

Одна идея состоит в том, что &,| и т. Д. Аналогичны арифметическому модулю 2 для отдельных двоичных цифр.Если a и b представляют собой однозначные двоичные цифры, то

a & b = a * b (mod 2)
a ^ b = a + b (mod 2)
   ~a = 1-a   (mod 2)
a | b = ~(~a & ~b) = 1 - (1-a)*(1-b) (mod 2)

Эквивалентами в базе 10 будут (обратите внимание, что они применяются к цифре, а не ко всему числу)

a & b = a * b (mod 10)
a ^ b = a + b (mod 10)
   ~a = 9-a   (mod 10)
a | b = ~(~a & ~b) = 9 - (9-a)*(9-b) (mod 10)

Первые три полезны при разработке схем, в которых используется BCD (~a является дополнением 9 ), например, неграфические калькуляторы, хотя мы просто используем * и + вместо & и ^ при написании уравнений.Первый также, по-видимому, используется в некоторых старых шифрах .

Answer 2

Интересный трюк для замены двух целых чисел без временной переменной с помощью побитового XOR:

void swap(int &a, int &b) {
   a = a ^ b;
   b = b ^ a; //b now = a
   a = a ^ b; //knocks out the original a
}

Это работает, потому что XOR является коммутативным, поэтому a ^ b ^ b = a.

Answer 3

На каждом языке, который я использовал (по общему признанию, почти исключительно C и C-производные), побитовые операторы являются исключительно целочисленными операциями (если, конечно, вы не переопределяете операцию).

Пока вы может сдвигать биты десятичного числа (в конце концов, они имеют свои собственные биты), это не обязательно даст вам тот же результат, что и перестановка битов целого числа.См. Single Precision и Double Precision для описания битов в десятичных числах.См. Fast Inverse Square Root для примера преимущественного использования битовых десятичных чисел с переворотом.

EDIT

Для целых чисел побитовые операции всегда выполняютсясмысл.Битовые операции предназначены для целых чисел.

n << 1 == n * 2
n << 2 == n * 4
n << 3 == n * 8

n >> 1 == n / 2
n >> 2 == n / 4
n >> 3 == n / 8

n & 1 == {0, 1}       // Set containing 0 and 1
n & 2 == {0, 2}       // Set containing 0 and 2
n & 3 == {0, 1, 2, 3} // Set containing 0, 1, 2, and 3

n | 1 == {1, n, n+1}
n | 2 == {2, n, n+2}
n | 3 == {3, n, n+1, n+2, n+3}

и т. Д.

Answer 4

Да, есть и другие полезные операции, но они, как правило, ориентированы на операции, включающие степени 2 (по понятным причинам), например проверка на нечетность / четность, проверка на степень 2, округление вверх / вниз до ближайшей степени 2 и т. д.

См. Восторг Хакера Генри С. Уоррена.

Answer 5

Вы можете вычислить логарифмы, используя только побитовые операторы ...

Нахождение показателя n = 2 ** x, используя побитовые операции [логарифм в базе 2 из n]

Answer 6

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

if ((a < 0) && (b < 0)
{
  do something
{

В C это может быть заменено на:

if ((a & b) < 0)
{
  do something
{

Это работает, потому что один бит в целом числе используется как бит знака (1 указываетотрицательный).Операция and (a & b) будет бессмысленным числом, но ее знак будет побитовым и со знаками чисел, и, следовательно, проверка знака результата будет работать.

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

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

Аналогично, ~ |и ^ можно использовать аналогичным образом, если все условия (x <0).Для условий сравнения вы обычно можете использовать вычитание: </p>

if ((a < b) | (b < c))
{
}

становится:

if (((a-b) | (b-c)) < 0)
{
}

, потому что ab будет отрицательным, только если a меньше b.С этим могут быть проблемы, если вы получаете в пределах 2 от max int - т.е. арифметическое переполнение, поэтому будьте осторожны.

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

ПРИМЕР: В качестве примера, скажем, вы хотите предпринять действия в зависимости от порядка a, b, c.Вы можете сделать некоторые вложенные конструкции if / else, или вы можете сделать это:

x = ((a < b) << 2) | ((b < c) << 1) | (c < a);
switch (x):

Я использовал это в коде с 9 условиями, а также использовал упомянутые выше вычитания с дополнительной логикой, чтобы изолировать знакбиты вместо менее чем.Это быстрее, чем эквивалент ветвления.Однако вам больше не нужно выполнять вычитание и извлечение знаковых битов, потому что стандарт давно обновлен, и в нем задано значение true, равное 1, а с условными перемещениями и т. Д. Фактическое значение «меньше» может быть весьма эффективным в наши дни.