Операция побитового сдвига и представление целых чисел

[main.c]

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

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

[ewert]

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

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

[main.c]

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

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

[venco]

ewert в сообщении #639989 писал(а):

Просто же сдвиг влево отрицательного числа, наоборот, даёт всегда положительный результат, поскольку очищает старший (знаковый) бит.

После исправления "влево" на "вправо" всё равно неправильно. Эта операция зависит от языка. В ассемблере 86 две разные инструкции - сохраняющая знак, и обнуляющая знаковый бит. Во многих ЯВУ сдвиг вправо знакового числа тоже сохраняет знак.

[ewert]

venco в сообщении #640003 писал(а):

В ассемблере 86 две разные инструкции - сохраняющая знак, и обнуляющая знаковый бит.

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

[worm2]

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

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

[Munin]

ewert в сообщении #640026 писал(а):

Именно поэтому по умолчанию понимается сдвиг логический, а не арифметический или циклический.

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

[main.c]

В данном случае именно Си и рассматривается)

Пусть у нас имеется число $(-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 меньше второго.
Если есть ошибки в моих рассуждениях, просьба указать на них.

[main.c]

А вот как быть со 2 вопросом?

[Chifu]

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

[main.c]

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-го вопроса. Вот здесь уже возникают трудности.

[Chifu]

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

[Chifu]

модуль дополнительный код 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

[main.c]

Chifu в сообщении #640328 писал(а):

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

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

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

[Munin]

main.c в сообщении #640403 писал(а):

Изменится ли что-нибудь, если сдвиг числа |X| приводит к выходу значащих битов за пределы 8-битовой ячейки памяти?

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

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