2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Сдвиг вправо и сдвиг влево
Сообщение18.01.2017, 17:57 


27/11/15

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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение18.01.2017, 18:21 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Ну, числа принято записывать так, как их принято записывать.
$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$. Вот эти двоичные циферки и сдвигаются.

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение18.01.2017, 21:28 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение07.02.2017, 03:13 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение08.02.2017, 10:24 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение08.02.2017, 15:27 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение09.02.2017, 00:51 


27/08/16
9426
bondkim137 в сообщении #1190420 писал(а):
вмлад есть два сдвига - знаковый и беззнаковый!
Возможно, вы удивитесь, но встречаются языки, в которых по две разных операции сдвига целого со знаком как вправо, так и влево. И это даже ещё не говоря про циклические сдвиги.

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение09.02.2017, 01:24 
Аватара пользователя


07/02/12
1403
Питер
realeugene в сообщении #1190966 писал(а):
Возможно, вы удивитесь

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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение09.02.2017, 01:57 


27/08/16
9426
bondkim137 в сообщении #1190973 писал(а):
Можно пример знакового сдвига встар? и чем оно от беззнакового отличается.
Арифметический сдвиг влево, в отличие от логического, размножает младший бит. Зачем он такой нужен, не знаю. Возможно, для полноты и симметрии набора битовых операций.

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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение09.02.2017, 02:35 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение09.02.2017, 03:03 


27/08/16
9426
bondkim137 в сообщении #1190976 писал(а):
Обычно арифметический сдвиг ВСТАР идентичен логическому - т.е. младшая часть заполняется нулями.
У большинства процессоров - да. Но VHDL очень интересный язык в части реализации системы типов. С одной стороны, он отнаследовал от Ада строгую типизацию. С другой стороны, это язык описания логики железа, поэтому, в нём очень важны именно разнообразные низкоуровневые битовые операции над битовыми векторами произвольной длины. Поэтому, в нём целые типов integer присутствуют без подразумеваемого битового представления и операций сдвига, но со знаковой арифметикой и диапазонами значений. Кроме того, есть битовые массивы без семантики чисел, для которых определены упомянутые ранее операции сдвига, но не определены арифметические операции. И есть ещё различные типы знаковых и беззнаковых битовых векторов задаваемой с точностью до бита длины как представлений целых чисел в двоичном дополнительном коде, для которых определены одновременно как битовые, так и арифметические операции, включая по 6 упомянутых операций сдвига. И между всем этим зоопарком (описанным мною крайне схематично) нет встроенных в язык неявных преобразований, от одного представления к другому при необходимости нужно преобразовывать значения явно.

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение09.02.2017, 14:53 


02/10/12
300
Прошу ответить на вопрос.
Язык СИ, формула округления целых чисел. Пусть, например, нужно вычислить
$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;

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение09.02.2017, 15:44 
Аватара пользователя


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

oleg_2 в сообщении #1191135 писал(а):
Используется синтаксис C
8/16= 1
-8/16= 0

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

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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение09.02.2017, 15:57 


02/10/12
300
bondkim137 в сообщении #1191159 писал(а):
в стандарте C целые типы - Two's complement.

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

 Профиль  
                  
 
 Re: Сдвиг вправо и сдвиг влево
Сообщение09.02.2017, 16:00 
Заслуженный участник
Аватара пользователя


06/10/08
6422
bondkim137 в сообщении #1191159 писал(а):
в стандарте C целые типы - Two's complement.
Нет. В частности, сдвиг вправо отрицательного числа - implementation-defined. И я не знаю, может где-то используется неарифметический сдвиг.

bondkim137 в сообщении #1191159 писал(а):
А это Вас не смущает?
Все хорошо, округление вверх.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group