2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 16:37 


22/07/12
560
Операция побитового сдвига и представление целых чисел в
компьютере. Операция X <<Y или X >> Y, когда X < 0.
А) Получим ли мы одинаковый результат, если будем
- применять сдвиг к дополнительному коду отрицательного числа
или
- применять сдвиг к |X| (модулю Х) и потом брать отрицание (т.е. переводить полученное
число в дополнительный код)? Ответ обосновать.
Б) Изменится ли что-нибудь, если сдвиг числа |X| приводит к выходу значящих битов за
пределы 8-битовой ячейки памяти? Ответ обосновать.

A) Практическим путём(побитово выводил числа) убедился, что для чисел -1 и нескольких других чисел X << Y даёт одинаковый результат, а вот для X >> Y не всегда одинаковый, как мне это обосновать?

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 17:19 
Заслуженный участник


11/05/08
32166
Сдвиг влево неотрицательного числа -- это деление нацело на 2, и при последующем отрицании получится число неположительное. Просто же сдвиг влево отрицательного числа, наоборот, даёт всегда положительный результат, поскольку очищает старший (знаковый) бит.

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

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 17:42 


22/07/12
560
Мне кажется Вы слегка перепутали).....побитовый сдвиг влево это умножение, а не деление числа на 2, ну а вправо соответственно деление нацело.

Но все равно спасибо, вы натолкнули меня на хорошую мысль.

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 18:16 
Заслуженный участник


04/05/09
4587
ewert в сообщении #639989 писал(а):
Просто же сдвиг влево отрицательного числа, наоборот, даёт всегда положительный результат, поскольку очищает старший (знаковый) бит.
После исправления "влево" на "вправо" всё равно неправильно. Эта операция зависит от языка. В ассемблере 86 две разные инструкции - сохраняющая знак, и обнуляющая знаковый бит. Во многих ЯВУ сдвиг вправо знакового числа тоже сохраняет знак.

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 19:14 
Заслуженный участник


11/05/08
32166
venco в сообщении #640003 писал(а):
В ассемблере 86 две разные инструкции - сохраняющая знак, и обнуляющая знаковый бит.

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

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


01/08/06
3131
Уфа
Но и это — лишь три четверти правды :D
4 операции как раз в ассемблере: SAR, SHR, SAL и SHL. А в процессоре 3, т.к. мнемоники SAL и SHL относятся к одной и той же команде процессора: логический и арифметический сдвиг влево — одна и та же операция, с одним и тем же кодом.

Ой, я ещё про циклические сдвиги забыл (rol/rcr всякие там). Начинаю склоняться к гипотезе, что всей правды не знает никто :-)

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 01:05 
Заслуженный участник
Аватара пользователя


30/01/06
72407
ewert в сообщении #640026 писал(а):
Именно поэтому по умолчанию понимается сдвиг логический, а не арифметический или циклический.

В каком-нибудь поганом не заслуживающем упоминания Си (в котором как раз и введены обозначения X<<Y и X>>Y, употреблённые топикстартером) по умолчанию понимается как раз сдвиг арифметический. Точнее, для signed типов арифметический, а для unsigned типов - логический, который для них совпадает с арифметическим (потому что старший бит не знаковый, а значащий).

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 11:15 


22/07/12
560
В данном случае именно Си и рассматривается)

Пусть у нас имеется число $(-X)$, где $ X > 0$, это число отрицательное.

Вот мои рассуждения, по поводу 1 вопроса:

Применив к этому числу побитовый сдвиг влево на Y позиций, мы фактически умножим его на $ 2^Y$, т. е. получим число $-X\cdot2^Y$.
Если же сначала взять модуль, $ X$, потом сдвинуть, $X\cdot2^Y$, и взять отрицание $-X\cdot2^Y$, получим то же самое число.
Теперь рассмотрим побитовый сдвиг вправо. Сдвинем на Y позиций, получим $\lfloor -X/2^Y \rfloor$. Если же сначала взять модуль, $ X$, потом сдвинуть, $\lfloor X/2^Y \rfloor$, и взять отрицание, получим число $ -\lfloor X/2^Y \rfloor$. Числа $\lfloor -X/2^Y \rfloor$ и $ -\lfloor X/2^Y \rfloor$ равны тогда и только тогда, когда $X$ делится нацело на $2^Y$, в противном случае первое число будет на 1 меньше второго.
Если есть ошибки в моих рассуждениях, просьба указать на них.

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 12:52 


22/07/12
560
А вот как быть со 2 вопросом?

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 15:19 
Аватара пользователя


27/01/09
814
Уфа
sar
10000000 -128 10101010 -86
11000000 -64 11010101 -43
11100000 -32 11101010 -22
11110000 -16 11110101 -11
11111000 -8 11111010 -6
11111100 -4 11111101 -3
11111110 -2 11111110 -2
11111111 -1 11111111 -1
sal
11111111 -1 10101010 -86
11111110 -2 01010100 84 of
11111100 -4 10101000 -88 of
11111000 -8 01010000 80 of
11110000 -16 10100000 -96 of
11100000 -32 01000000 64 of
11000000 -64 10000000 -128 of
10000000 -128 00000000 0 of
00000000 0 of

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 15:34 


22/07/12
560
Chifu в сообщении #640309 писал(а):
sar
10000000 -128 10101010 -86
11000000 -64 11010101 -43
11100000 -32 11101010 -22
11110000 -16 11110101 -11
11111000 -8 11111010 -6
11111100 -4 11111101 -3
11111110 -2 11111110 -2
11111111 -1 11111111 -1
sal
11111111 -1 10101010 -86
11111110 -2 01010100 84 of
11111100 -4 10101000 -88 of
11111000 -8 01010000 80 of
11110000 -16 10100000 -96 of
11100000 -32 01000000 64 of
11000000 -64 10000000 -128 of
10000000 -128 00000000 0 of
00000000 0 of


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

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 16:00 
Аватара пользователя


27/01/09
814
Уфа
По-моему я наглядно показал, как работают арифметические сдвиги для байта. Смотрите и думайте. Числа без знака на один бит длиннее и sal не сохраняет знак, отсюда и разница будет. Какие у вас регистры? Не указали. Видно же, что sar не дают переполнения, а качество результата sal зависит от количества значащих битов, точнее когда знак изменится. Откуда я знаю почему у вас на 1 различаются, из ваших объяснений это вовсе не следует, может вы дополнительный код отрицательного числа не умеете получать?

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 19:13 
Аватара пользователя


27/01/09
814
Уфа
модуль дополнительный код sar
01111111 127 10000001 -127 10000001 -127
00111111 63 11000001 -63 11000000 -64
00011111 31 11100001 -31 11100000 -32
00001111 15 11110001 -15 11110000 -16
00000111 7 11111001 -7 11111000 -8
00000011 3 11111101 -3 11111100 -4
00000001 1 11111111 -1 11111110 -2
00000000 0 00000000 0 11111111 -1
отсюда видно различие между преобразованием и логической командой

модуль дополнительный код sal
00000001 1 11111111 -1 идентичен
00000010 2 11111110 -2
00000100 4 11111100 -4
00001000 8 11111000 -8
00010000 16 11110000 -16
00100000 32 11100000 -32
01000000 64 11000000 -64
10000000 128 10000000 -128
00000000 0 00000000 0

01010110 86 10101010 -86 идентичен
10101100 -84 of 01010100 84
01011000 88 of 10101000 -88
10110000 -80 of 01010000 80
01100000 96 of 10100000 -96
11000000 -64 of 01000000 64
10000000 -128 of 10000000 -128
00000000 0 of 00000000 0

 Профиль  
                  
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 19:26 


22/07/12
560
Chifu в сообщении #640328 писал(а):
По-моему я наглядно показал, как работают арифметические сдвиги для байта. Смотрите и думайте. Числа без знака на один бит длиннее и sal не сохраняет знак, отсюда и разница будет. Какие у вас регистры? Не указали. Видно же, что sar не дают переполнения, а качество результата sal зависит от количества значащих битов, точнее когда знак изменится. Откуда я знаю почему у вас на 1 различаются, из ваших объяснений это вовсе не следует, может вы дополнительный код отрицательного числа не умеете получать?


Как работает арифметический сдвиг, я знаю и знал, задолго до того, как создал эту тему.
Вы в вопрос вчитывались?......Я не спрашиваю, как работает операция сдвига, ещё раз повторяю, меня интересует:
Изменится ли что-нибудь, если сдвиг числа |X| приводит к выходу значащих битов за
пределы 8-битовой ячейки памяти? Когда тут спрашивают, изменится ли что-нибудь, имеется ввиду, числа будут по-прежнему в таком же отношении эквивалентности, как и в первом вопросе или нет. Ответ обосновать.

Это одно число, оно знаковое, в одном случае мы применяем сдвиг, а в другом случае берём модуль, затем сдвиг, а потом отрицание, и тут не спрашивается, будут ли числа правильно посчтаны или нет, тут спрашивается, будут ли они ОДИНАКОВЫ. И зачем вы мне пишите, что беззнаковое число на 1 бит больше, оно не больше, оно занимает столько же бит, различие лишь в том, что старший бит у знакового отводится под знак. А регистры то здесь причём??? :facepalm: Да, и ещё, поконкретнее скажите, что из чего не следует в моих объяснениях?

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


30/01/06
72407
main.c в сообщении #640403 писал(а):
Изменится ли что-нибудь, если сдвиг числа |X| приводит к выходу значащих битов за пределы 8-битовой ячейки памяти?

Если вы сидите в Си, и число ваше имеет целочисленный тип в Си, то ему по барабану 8-битовые ячейки. Точнее, вам по барабану. Результат сдвига будет гарантированно такой, как будто число - непрерывная ячейка памяти из скольки-то-надцати бит. Как язык этого добьётся - это его проблемы.

Если вы делаете что-то в ассемблере, то там сдвиги совершаются тоже удобно, по размерам операндов команд сдвига. И только если вы хотите эмулировать работу с данными слишком большой или нестандартной длины, вам придётся реализовывать команды сдвига самому, и следить за переходом между границами ячеек памяти. Но даже и в этом случае, базовый размер ячейки памяти может быть выбран более удобным, чем 8 бит, например, 32 бита.

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

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



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

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


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

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