беззнаковый символ поворота

Question

Я немного смущен тем, что такое беззнаковый символ. Знаковый символ - это представление символа в битовой форме, верно? В типовой задаче мы поворачиваем вправо на n битных позиций, битов беззнакового символа с помощью этого решения:

unsigned char rotate(unsigned char x, int n) {
    unsigned char temp = x << 8 - n;
    x = x >> n;
    return (x | temp);
}

Если бы кто-нибудь мог объяснить с помощью примеров символов и их соответствующих битов, это было бы очень признательно. Большое спасибо.

Answer 1

signed char, char и unsigned char - все целочисленные типы.Для простоты я предполагаю, что CHAR_BIT равен 8, а подписанные типы являются дополнением 2.Итак:

• signed char это число от -128 до + 127
• unsigned char это число от 0 до 255
• char либотот же диапазон, что и signed char, или тот же диапазон, что и unsigned char, в зависимости от вашей реализации на языке C.

Что касается C, то символ - это просто число в пределах диапазонаchar тип (хотя различные символьные функции, такие как tolower, требуют приведения значения к типу без знака при входе, даже если char подписано).

Итак, signed char и unsigned char являются оба представление символа в битовой форме.Для чисел в диапазоне от 0 до +127 они оба используют одно и то же представление (есть только один способ представить положительные числа в двоичном виде).Для чисел вне этого диапазона подписанное представление отрицательного числа n - это те же биты, что и беззнаковое представление n + 256 (определение дополнения к 2).

Причина, по которой этот код использует unsigned char, заключается в том, чтоэтот сдвиг вправо с отрицательным знаком имеет результат, определенный реализацией.Сдвиг влево с отрицательным знаком имеет неопределенное поведение .Обычно сдвиг влево ведет себя так же, как и для значений без знака, что нормально, но сдвиг вправо вставляет биты слева со значением 1, так называемый «арифметический сдвиг», что здесь не так.Беззнаковые значения всегда смещаются в нули, и именно смещение нуля позволяет этому коду построить две части повернутого результата и / или их вместе.

Итак, предполагая, что входное значение x = 254 (11111110) и n = 1, мы получим:

x << 7 is 0111111100000000
x >> 1 is         01111111
|      is 0111111101111111
convert to unsigned char to return is 01111111

Если бы мы использовали тип со знаком вместо unsigned char, мы вполне могли бы получить:

x is -2                           11111110
x << 7 is 11111111111111111111111100000000 (assuming 32-bit int, since
           smaller types are always promoted to int for arithmetic ops)
x >> 1 is implementation-defined, possibly 
          11111111111111111111111111111111
| is      11111111111111111111111111111111
convert to signed char to return is -1

Так чтобитовая манипуляция с беззнаковым символом приводит к правильному ответу, повернутому на 1 бит, чтобы переместить 0 от конца к началу.Битовая манипуляция со знаком со знаком, возможно, дает неправильный результат, может дать правильный результат, если отрицательные знаковые значения делают логический сдвиг вправо, но в действительно необычных реализациях может делать что угодно.

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

Answer 2

Объявление переменной как unsigned char указывает компилятору обрабатывать базовый битовый шаблон как число от 0 (00000000) до 255 (11111111).Объявление char указывает компилятору применить дополнение к двум к базовому битовому шаблону и рассматривать его как число от -128 (10000000) до 127 (01111111).

3-х битное число.Если он не подписан, у вас есть:

000 = 0
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7

Если он подписан, у вас есть:

100 = -4
101 = -3
110 = -2
111 = -1
000 =  0
001 =  1
010 =  2
011 =  3

В отношении арифметики (как упоминается в этой ссылке) важно, что выне должны обрабатывать двоичные числа со знаком иначе, чем беззнаковые.Вы просто делаете реальную двоичную математику безотносительно к подписанному или неподписанному.Но вы должны применить интерпретацию со знаком / без знака к входам и к выходу.

В области со знаком вы можете иметь:

2 + (-3) = 010 + 101 = 111 = -1

Но в области без знака это:

2 + 5 = 010 + 101 = 111 = 7

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

Answer 3

беззнаковый символ - это просто 8-разрядный целочисленный тип, который может принимать значения от 0 до 255, а знаковый символ может принимать значения от -127 до 128. В реальном машинном коде нет реальной разницы, кроме единицы: Вы делаете сдвиг вправо для типа со знаком, используя >> (будь то char, short или int), это выполняется как арифметическое смещение, означающее, что для отрицательных значений (для которых MSB равен 1), вместо 1 сдвигается 1 0 и приведенный выше код не будут работать должным образом.

РЕДАКТИРОВАТЬ: В приведенном выше примере кода вращение беззнакового символа на 3 бита для подписанного и без знака:

00110101 повернуто без знака и подписано 10100110.

, но для числа с 1 спереди вы получаете арифметическое смещение и, таким образом,

11010001 повернуто без знака является 00111010.
11010001 повернуто, подписано - 11111010.