2014 dxdy logo

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

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




На страницу 1, 2, 3  След.
 
 Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 16:37 
Операция побитового сдвига и представление целых чисел в
компьютере. Операция X <<Y или X >> Y, когда X < 0.
А) Получим ли мы одинаковый результат, если будем
- применять сдвиг к дополнительному коду отрицательного числа
или
- применять сдвиг к |X| (модулю Х) и потом брать отрицание (т.е. переводить полученное
число в дополнительный код)? Ответ обосновать.
Б) Изменится ли что-нибудь, если сдвиг числа |X| приводит к выходу значящих битов за
пределы 8-битовой ячейки памяти? Ответ обосновать.

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

 
 
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 17:19 
Сдвиг влево неотрицательного числа -- это деление нацело на 2, и при последующем отрицании получится число неположительное. Просто же сдвиг влево отрицательного числа, наоборот, даёт всегда положительный результат, поскольку очищает старший (знаковый) бит.

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

 
 
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 17:42 
Мне кажется Вы слегка перепутали).....побитовый сдвиг влево это умножение, а не деление числа на 2, ну а вправо соответственно деление нацело.

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

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

 
 
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 19:14 
venco в сообщении #640003 писал(а):
В ассемблере 86 две разные инструкции - сохраняющая знак, и обнуляющая знаковый бит.

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

 
 
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение04.11.2012, 21:14 
Аватара пользователя
Но и это — лишь три четверти правды :D
4 операции как раз в ассемблере: SAR, SHR, SAL и SHL. А в процессоре 3, т.к. мнемоники SAL и SHL относятся к одной и той же команде процессора: логический и арифметический сдвиг влево — одна и та же операция, с одним и тем же кодом.

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

 
 
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 01:05 
Аватара пользователя
ewert в сообщении #640026 писал(а):
Именно поэтому по умолчанию понимается сдвиг логический, а не арифметический или циклический.

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

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

Пусть у нас имеется число $(-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 
А вот как быть со 2 вопросом?

 
 
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 15:19 
Аватара пользователя
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 
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 
Аватара пользователя
По-моему я наглядно показал, как работают арифметические сдвиги для байта. Смотрите и думайте. Числа без знака на один бит длиннее и sal не сохраняет знак, отсюда и разница будет. Какие у вас регистры? Не указали. Видно же, что sar не дают переполнения, а качество результата sal зависит от количества значащих битов, точнее когда знак изменится. Откуда я знаю почему у вас на 1 различаются, из ваших объяснений это вовсе не следует, может вы дополнительный код отрицательного числа не умеете получать?

 
 
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 19:13 
Аватара пользователя
модуль дополнительный код 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 
Chifu в сообщении #640328 писал(а):
По-моему я наглядно показал, как работают арифметические сдвиги для байта. Смотрите и думайте. Числа без знака на один бит длиннее и sal не сохраняет знак, отсюда и разница будет. Какие у вас регистры? Не указали. Видно же, что sar не дают переполнения, а качество результата sal зависит от количества значащих битов, точнее когда знак изменится. Откуда я знаю почему у вас на 1 различаются, из ваших объяснений это вовсе не следует, может вы дополнительный код отрицательного числа не умеете получать?


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

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

 
 
 
 Re: Операция побитового сдвига и представление целых чисел
Сообщение05.11.2012, 20:00 
Аватара пользователя
main.c в сообщении #640403 писал(а):
Изменится ли что-нибудь, если сдвиг числа |X| приводит к выходу значащих битов за пределы 8-битовой ячейки памяти?

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

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

 
 
 [ Сообщений: 39 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group