Сдвиг вправо и сдвиг влево

[alhimikoff]

Корректно ли такое название операций?
Что двигается вправо и влево? Электроны в памяти, цифры на экране?
Ну переверните монитор, и получите из сдвига вправо сдвиг влево.

[worm2]

Ну, числа принято записывать так, как их принято записывать.
$234$, например — это $2\times 10^2 + 3\times 10 + 4$. А не наоборот.
И тут, даже если я напишу так: $\rotatebox[c]{180}{234}$, с полным правом можно сказать, что 3 стоит слева от 4 и справа от 2.
В двоичной системе счисления то же самое:
$10111_2 = 1\times 2^4 + 1\times 2^2 + 1\times 2 + 1$. Вот эти двоичные циферки и сдвигаются.

[arseniiv]

Неверно, неверно! Надо их звать «сдвиг вмлад» и «сдвиг встар», разумеется!

[bondkim137]

вмлад есть два сдвига - знаковый и беззнаковый!
а еще настроение портят большой и маленький endian-ы.

[warlock66613]

bondkim137 в сообщении #1190420 писал(а):

а еще настроение портят большой и маленький endian-ы

Непонятно, с чего бы это. В случае big endian порядок битов один и тот же в математической записи и в реальном расположении в памяти, так что тут всё логично. А к little endian все привыкли, так что с ним всё привычно. В конце-концов какое отношение это имеет к сдвигам, когда эти самые сдвиги (да и все остальные битовые и числовые операции) никак не зависят от endian'а.

[bondkim137]

warlock66613
Это так, только если нет более точной адресации, чем адрес числа, и битовый формат хранения этих чисел не принципиален.

Хочется Вам, например, сдвинуть байтовую строку на один байт на 64-х разрядной машине, используя логические операции в оптимизационных целях (работая с большими словами) - придется учитывать, какой у Вас endian.

Или если работаете с готовой битовой структурой, endian которой не совпадает с Вашим - придется тоже учитывать. Хотя бы на самом простом уровне - влоб всегда разворачивать числа при чтении и записи, чтобы со сдвигами ничего не шаманить (что иногда тоже не очень просто/быстро - например когда 64-битное число, стоит по смещению 43-ого бита).

[realeugene]

bondkim137 в сообщении #1190420 писал(а):

вмлад есть два сдвига - знаковый и беззнаковый!

Возможно, вы удивитесь, но встречаются языки, в которых по две разных операции сдвига целого со знаком как вправо, так и влево. И это даже ещё не говоря про циклические сдвиги.

[bondkim137]

realeugene в сообщении #1190966 писал(а):

Возможно, вы удивитесь

Любопытно. Можно пример знакового сдвига встар? и чем оно от беззнакового отличается.
Если конечно речь не об иных представлениях знаково числа, нежели Two's complement.
Цикличиские сдвиги (включая сдвиги через флаг(и) переноса) - отдельная тема.

[realeugene]

bondkim137 в сообщении #1190973 писал(а):

Можно пример знакового сдвига встар? и чем оно от беззнакового отличается.

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

Речь идёт про VHDL.

[bondkim137]

Понятно, спасибо.
Подобных экзотических операций в нативном исполнении еще не встречал. Впрочем, имел дело только с 'попсовыми' процессорами. Обычно арифметический сдвиг ВСТАР идентичен логическому - т.е. младшая часть всегда заполняется нулями.

[realeugene]

bondkim137 в сообщении #1190976 писал(а):

Обычно арифметический сдвиг ВСТАР идентичен логическому - т.е. младшая часть заполняется нулями.

У большинства процессоров - да. Но VHDL очень интересный язык в части реализации системы типов. С одной стороны, он отнаследовал от Ада строгую типизацию. С другой стороны, это язык описания логики железа, поэтому, в нём очень важны именно разнообразные низкоуровневые битовые операции над битовыми векторами произвольной длины. Поэтому, в нём целые типов integer присутствуют без подразумеваемого битового представления и операций сдвига, но со знаковой арифметикой и диапазонами значений. Кроме того, есть битовые массивы без семантики чисел, для которых определены упомянутые ранее операции сдвига, но не определены арифметические операции. И есть ещё различные типы знаковых и беззнаковых битовых векторов задаваемой с точностью до бита длины как представлений целых чисел в двоичном дополнительном коде, для которых определены одновременно как битовые, так и арифметические операции, включая по 6 упомянутых операций сдвига. И между всем этим зоопарком (описанным мною крайне схематично) нет встроенных в язык неявных преобразований, от одного представления к другому при необходимости нужно преобразовывать значения явно.

[oleg_2]

Прошу ответить на вопрос.
Язык СИ, формула округления целых чисел. Пусть, например, нужно вычислить
$y = 0.3 \cdot x$
где x и y целые числа. И все вычисления чтоб были целочисленными. Умножаю 0.3 на степень двойки, например, на 16.
$y = ((0.3 \cdot16) \cdot x) / 16 = (5x)/16$
Формула, заменяющая деление на 16 и дающая правильное приближение, а не такое, как при операции деления целых чисел:
y = ((5 * x) + 8) >> 4;
Я написал тест. На моём компьютере, видимо, дополнительный код для отрицательных чисел.

Используется синтаксис C

int main()
{
    int a[]={ 6, 7, 8, 9, 10, 14, 15, 16, 17, 18,
             -6,-7,-8,-9,-10,-14,-15,-16,-17,-18};
    int x, y, i;

    for(i=0; i<(sizeof(a)/sizeof(a[0])); i++){
        x = a[i];
        y = (x + 8) >> 4; // y=x/16
        printf("%3d/16=%2d\n", x, y);
    }
    exit(0);
}

Распечатка.
  6/16= 0
  7/16= 0
  8/16= 1
  9/16= 1
 10/16= 1
 14/16= 1
 15/16= 1
 16/16= 1
 17/16= 1
 18/16= 1
 -6/16= 0
 -7/16= 0
 -8/16= 0
 -9/16=-1
-10/16=-1
-14/16=-1
-15/16=-1
-16/16=-1
-17/16=-1
-18/16=-1
 

Пример работы формулы y = (x + 8) >> 4; для x=-9 и x=-10 в дополнительном коде.
  Пример y = ((-9) + 8) >> 4
              8 = |0|0|0|0|1|0|0|0|
             -9 = |1|1|1|1|0|1|1|1|
       8 + (-9) = |1|1|1|1|1|1|1|1| = -1
  8 + (-9) >> 4 = |1|1|1|1|1|1|1|1| = -1

  Пример y = ((-10) + 8) >> 4
               8 = |0|0|0|0|1|0|0|0|
             -10 = |1|1|1|1|0|1|1|0|
       8 + (-10) = |1|1|1|1|1|1|1|0| = -2
(8 + (-10)) >> 4 = |1|1|1|1|1|1|1|1| = -1

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

Используется синтаксис C

    double sum;
    int s;

    if(sum >= 0) sum += 0.5;
    else sum -= 0.5;
    s = (int)sum;

[bondkim137]

oleg_2
Вроде бы в стандарте C целые типы - Two's complement.

oleg_2 в сообщении #1191135 писал(а):

Используется синтаксис C

8/16= 1
-8/16= 0

А это Вас не смущает?

Перед делением на 16 сдвигом вниз, сдвиньте знаковый бит на место восьмерки, обрежте его маской и прибавьте в делимому. Можно просто написать

Используется синтаксис C

/16

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

[oleg_2]

bondkim137 в сообщении #1191159 писал(а):

в стандарте C целые типы - Two's complement.

Я по-английски плохо, но, как я Вас понял, формула будет работать всюду. Спасибо.
Нет, не смущает. Это всё же много лучше, чем просто деление целых. И множитель умножают обычно не на 16, а больше, на 256. Погрешность маленькая получается, всё равно ведь вычисления приближённые.

[Xaositect]

bondkim137 в сообщении #1191159 писал(а):

в стандарте C целые типы - Two's complement.

Нет. В частности, сдвиг вправо отрицательного числа - implementation-defined. И я не знаю, может где-то используется неарифметический сдвиг.

bondkim137 в сообщении #1191159 писал(а):

А это Вас не смущает?

Все хорошо, округление вверх.