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

В соответствии с wiki сдвиги могут использоваться для вычисления степеней 2:

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

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

Ответы

Ответ 1

"yep base-10 is what I mean"

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

Одна идея состоит в том, что &, | и т.д. такие же, как выполнение арифметического mod-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 дополнение), например, неграфические калькуляторы, хотя мы просто используем * и +, а не & и ^ при написании уравнений. Первый, по-видимому, также используется в некоторых старых шифрах.

Ответ 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.

Ответ 3

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

В то время как вы можете перекручивать биты десятичного числа (в конце концов, у них есть свои собственные биты), это не обязательно приведет к тому же результату, что и скручивание битов целочисленного числа. См. Единая точность и Двойная точность для описания бит в десятичные числа. См. Быстрый обратный квадратный корень для примера преимущественного использования десятичных чисел бит-скругления.

ИЗМЕНИТЬ

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

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}

И так далее.

Ответ 4

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

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

Ответ 6

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

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

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

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

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

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

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

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

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

становится:

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

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

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

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

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

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