Зачем использовать только младшие пять битов операнда сдвига при сдвиге 32-битного значения? (например, (UInt32) 1 << 33 == 2) - PullRequest
Новая
       13

Зачем использовать только младшие пять битов операнда сдвига при сдвиге 32-битного значения? (например, (UInt32) 1 << 33 == 2)

14 голосов
/ 14 марта 2009

Рассмотрим следующий код: 

UInt32 val = 1;
UInt32 shift31 = val << 31;                    // shift31  == 0x80000000
UInt32 shift32 = val << 32;                    // shift32  == 0x00000001
UInt32 shift33 = val << 33;                    // shift33  == 0x00000002
UInt32 shift33a = (UInt32)((UInt64)val << 33); // shift33a == 0x00000000

Он не генерирует предупреждение (об использовании смещения больше 32), поэтому это должно быть ожидаемое поведение.

Код, который фактически выводится в сгенерированную сборку (или, по крайней мере, интерпретация кода в Reflector): 

 uint val = 1;
 uint shift31 = val << 0x1f;
 uint shift32 = val;
 uint shift33 = val << 1;
 uint shift33a = val << 0x21;

IL (опять же, с помощью Reflector) равен 

L_0000: nop 
L_0001: ldc.i4.1 
L_0002: stloc.0 
L_0003: ldloc.0 
L_0004: ldc.i4.s 0x1f
L_0006: shl 
L_0007: stloc.1 
L_0008: ldloc.0 
L_0009: stloc.2 
L_000a: ldloc.0 
L_000b: ldc.i4.1 
L_000c: shl 
L_000d: stloc.3 
L_000e: ldloc.0 
L_000f: conv.u8 
L_0010: ldc.i4.s 0x21
L_0012: shl 
L_0013: conv.u4 
L_0014: stloc.s shift33a

Я понимаю , что происходит (это описано в MSDN ); когда код компилируется, при сдвиге 32-битного значения используются только младшие 5 битов ... Мне любопытно узнать, почему это происходит.

(Выход shift33a также заставляет меня думать, что с Reflector что-то не так, поскольку их представление IL на c # будет компилироваться во что-то другое)

Вопрос (ы):

  • Почему используются только младшие 5 битов "значения для сдвига"?
  • Если «не имеет смысла сдвигать более 31 бита», почему нет предупреждения?
  • Это вещь с обратной совместимостью (то есть это то, что программисты "ожидают", чтобы это произошло)?
  • Правильно ли, что базовый IL может сдвигать более чем на 31 бит (как в L_0010: ldc.i4.s 0x21), но компилятор обрезает значения?

Ответы [ 3 ]

9 голосов
/ 14 марта 2009

В основном все сводится к тому, как x86 обрабатывает коды операций арифметического сдвига: он использует только нижние 5 битов счетчика сдвигов. См., Например, руководство по программированию 80386 . В C / C ++ это технически неопределенное поведение - сдвигать бит более чем на 31 бит (для 32-битного целого), придерживаясь философии C: «вы не платите за то, что вам не нужно». Из раздела 6.5.7, параграфа 3 стандарта C99:

Целочисленные продвижения выполняются для каждого из операндов. Тип результата - тип повышенного левого операнда. Если значение правого операнда отрицательно или больше или равно ширине повышенного левого операнда, поведение не определено.

Это позволяет компиляторам пропускать односменную инструкцию на x86 для смен. 64-битные сдвиги не могут быть выполнены в одной инструкции на x86. Они используют инструкции SHLD / SHRD и некоторую дополнительную логику. На x86_64 64-битные сдвиги могут быть выполнены в одной инструкции.

Например, gcc 3.4.4 выдает следующую сборку для 64-разрядного сдвига влево на произвольную величину (скомпилировано с -O3 -fomit-frame-pointer): 

uint64_t lshift(uint64_t x, int r)
{
  return x << r;
}

_lshift:
    movl    12(%esp), %ecx
    movl    4(%esp), %eax
    movl    8(%esp), %edx
    shldl   %cl,%eax, %edx
    sall    %cl, %eax
    testb   $32, %cl
    je      L5
    movl    %eax, %edx
    xorl    %eax, %eax
L5:
    ret

Теперь я не очень знаком с C #, но, полагаю, у него схожая философия - спроектировать язык, чтобы он мог быть реализован максимально эффективно. Указывая, что операции сдвига используют только младшие 5/6 битов счетчика сдвигов, это позволяет компилятору JIT компилировать сдвиги как можно более оптимально. 32-битные сдвиги, а также 64-битные сдвиги в 64-битных системах могут компилировать JIT в один код операции.

Если бы C # был перенесен на платформу, которая по-разному реагировала на собственные коды операций сдвига, то это фактически повлекло бы за собой дополнительное снижение производительности - JIT-компилятор должен был бы обеспечить соблюдение стандарта, поэтому он должен был бы добавить дополнительная логика, позволяющая убедиться, что использовались только младшие 5/6 битов числа сдвигов.

3 голосов
/ 14 марта 2009

Unit32 переполняется при 32 битах, что определено в спецификации. Что вы ожидаете?

CLR не определяет сдвиг влево с помощью оператора обнаружения переполнения (1). Если вам нужно такое оборудование, вы должны проверить сами.

(1) Компилятор C # может привести его к long, но я не уверен.

1 голос
/ 14 марта 2009

Я написал этот простой тест на C (gcc, linux) и получил похожие результаты. Что интересно, так это то, что константы, определяющие избыточное смещение, обернулись в ноль, а не оборачивались Он предупреждал о них, так что, по крайней мере, было определенное признание того, что это «неправильная» вещь. 

#include <stdio.h>

unsigned int is0 = 1 << 31;
unsigned int is1 = 1 << 32;
unsigned int is2 = 1 << 33;

int main()
{
   unsigned int loopy = 0;
   int x = 0;
   printf("0x%08X\n", is0);
   printf("0x%08X\n", is1);
   printf("0x%08X\n", is2);


   for (x = 0; x < 35; ++x)
   {
      loopy = 1 << x;
      printf("%02d 0x%08X\n", x,loopy);
   }

   return 0;
}

Вот результаты: 

0x80000000
0x00000000
0x00000000
00 0x00000001
01 0x00000002
02 0x00000004
03 0x00000008
04 0x00000010
05 0x00000020
06 0x00000040
07 0x00000080
08 0x00000100
09 0x00000200
10 0x00000400
11 0x00000800
12 0x00001000
13 0x00002000
14 0x00004000
15 0x00008000
16 0x00010000
17 0x00020000
18 0x00040000
19 0x00080000
20 0x00100000
21 0x00200000
22 0x00400000
23 0x00800000
24 0x01000000
25 0x02000000
26 0x04000000
27 0x08000000
28 0x10000000
29 0x20000000
30 0x40000000
31 0x80000000
32 0x00000001
33 0x00000002
34 0x00000004
...