Не зная брода, не лезь в воду. Часть третья

    Сдвиги
    Продолжу рассказы о том, как программисты ходят по краю, даже не подозревая об этом. Поговорим об операциях сдвига <<, >>. Принципы работы операторов сдвига очевидны и многие программисты даже не знают, что их использование согласно стандарту Си/Си++ может приводить к неопределенному или к неуточненному поведению (undefined behaviour/unspecified behavior).


    Предыдущие статьи доступны здесь: [1], [2].

    Исторический экскурс


    В начале немного истории. Необходимость операций сдвига битов очевидна любому программисту. Рано или поздно каждый сталкивается с необходимостью работать с отдельными битами и битовыми масками. Тем не менее, операции сдвига намного более популярны, чем должны были быть. Причина в том, что используя сдвиги можно умножать и делить числа на степень двойки. Например, операция «X << 3» умножит X на 8. Преимущество такого способа умножения и деления заключалось в скорости их работы в прошлом.

    Сейчас я достал с пыльной полки книжку с описанием ассемблерных команд для процессоров, начиная с 8086 и заканчивая 80486. И нашёл таблицу о количестве тактов, необходимых для выполнения различных инструкций.

    Умножение 16-битного регистра на ячейку памяти с использованием инструкции MUL на процессоре 8086 требует порядка 124-139 тактов!

    Сдвиг 16-битного регистра на N позиций с использованием инструкции SHL на процессоре 8086 требует 8+4*N тактов. То есть в худшем случае получается 72 такта.

    Можно было получить существенное ускорение при вычислении арифметических выражений используя различные трюки при работе с битовыми операциями. Это и стало причиной массового использования сдвигов, в начале, на языке ассемблер, потом в языках Си и Си++. Первые компиляторы Си/Си++ были просты. Человек мог получить выигрыш в скорости, явно подсказав компилятору, что здесь следует использовать сдвиг, а не инструкции умножения или деления.

    С развитием процессоров польза от использования сдвигов долгое время сохранялась. В 80486 процессоре умножение стало занимать около 26 тактов. Вроде намного лучше. Однако сдвиг стал занимать всего 3 такта и вновь, был более привлекателен, чем умножение.

    К счастью эти вынужденные оптимизации в большинстве своём канули в небытие. Во-первых, компиляторы стали умны и используют оптимальный набор инструкций для вычисления арифметических выражений. Во-вторых, процессоры также колоссально изменились. Появились конвейеры, предсказание переходов, переименование регистров и много чего ещё. Поэтому сказать, сколько времени займет выполнение той или иной инструкции обыкновенный программист уже не в состоянии. Но ясно, что если код местами будет не идеален, этого можно даже не заметить. Процессор разобьет инструкции на микроинструкции и начнет выполнять их параллельно. Если честно, то я уже не разбираюсь, как сейчас там всё происходит. Я понял, что разбираться в тонкостях бессмысленно, начиная с процессора Intel Pentium. И сделал вывод, что не стоит думать, что ты лучше знаешь, как нужно писать оптимизирующий код, использовать сдвиги и битовые операции, где только можно. Далеко не факт, что в результате код будет быстрее, чем сделает это оптимизатор в компиляторе. Зато точно можно сказать, что программа станет запутанной и сложной для понимания.

    Примечание. Вышесказанное не значит, что использование битовых операций больше не может приносить выгоды. Есть много интересных и полезных трюков [3]. Главное не увлекаться.

    Неопределенное поведение


    Началось всё с того, что я решил увеличить в анализаторе PVS-Studio количество предупреждений связанных с undefined behaviour [4] и unspecified behavior [5]. Достаточно быстро и просто было реализовано правило, выявляющее некорректное использование операций сдвига. После этого мне пришлось остановиться и задуматься.

    Оказалось, что программисты очень любят сдвиги. И используют их всевозможнейшим способом, приводящим часто с точки зрения стандарта к неопределенному поведению. Но одно дело теория, а другое практика. Есть ли смысл ругаться на код, который верой и правдой служил десятилетия и пережил уже не один компилятор? Сложный вопрос. Не смотря на то, что код некорректен, компиляторы следуют некому негласному соглашению и обрабатывают его единообразным способом.

    После долгих раздумий, я всё-таки решил оставить данное диагностическое правило в PVS-Studio, не делая из него исключений. Если будет слишком много жалоб от пользователей, то возможно я изменю своё мнение. Впрочем, возможно пользователи удовлетворятся возможностью выключить эту диагностику или используют другие методы подавления предупреждений.

    Кстати, именно эти душевные терзания и побудили меня написать статью. Надеюсь информация, которую я покажу, будет интересна и полезна.

    Итак, посмотрим, что написано в стандарте C++11 по поводу операторов сдвига:

    The shift operators << and >> group left-to-right.

    shift-expression << additive-expression

    shift-expression >> additive-expression

    The operands shall be of integral or unscoped enumeration type and integral promotions are performed.

    1. The type of the result is that of the promoted left operand. The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

    2. The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 * 2^E2, reduced modulo one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1*2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

    3. The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

    Читать подобные тексты грустно и печально. Но не волнуйтесь. Сейчас мы рассмотрим различные некорректные ситуации на примерах.

    Самый простой случай приводящий к неопределенному поведению, это когда правый операнд имеет отрицательное значение. Пример:
    int A = 10;
    int B = A << -5;

    Так, слава богу, никто не делает. По крайней мере, проанализировав более 70 open-source проектов, мы не встретили подобных ошибок.

    Следующий случай гораздо интереснее. Это сдвиг на N бит, где N, большее, чем количество бит в левом операнде. Простейший пример:
    int A = 10;
    int B = A << 100;

    Посмотрим, как такая ошибка может выглядеть на практике. Следующий фрагмент кода был обнаружен нами в библиотеке Lib7z:
    SZ_RESULT
    SafeReadDirectUInt64(ISzInStream *inStream, UInt64 *value)
    {
      int i;
      *value = 0;
      for (i = 0; i < 8; i++)
      {
        Byte b;
        RINOK(SafeReadDirectByte(inStream, &b));
        *value |= ((UInt32)b << (8 * i));
      }
      return SZ_OK;
    }

    Диагностическое сообщение PVS-Studio: V610 Undefined behavior. Check the shift operator '<<. The right operand ('(8 * i)' = [0..56]) is greater than or equal to the length in bits of the promoted left operand. lib7z 7zin.c 233

    Функция пытается побайтно прочитать 64-битное значение. К сожалению, у неё это не получится, если число было больше 0x00000000FFFFFFFF. Обратите внимание на сдвиг "(UInt32)b << (8 * i)". Размер левого операнда составляет 32 бита. При этом сдвиг происходит от 0 до 56 бит. На практике это приведёт к тому, что старшая часть 64-битного значения останется заполнена нулями. Теоретически здесь вообще имеет место неопределенное поведение и результат непредсказуем.

    Корректный код должен выглядеть так:
    *value |= ((UInt64)b << (8 * i));

    У читателя может возникнуть вопрос, а корректен ли код приведенный ниже?
    char A = 1;
    int B = A << 20;

    Да, корректен. Слева от оператора << находится переменная A, состоящая только из 8 бит. Но перед началом операции сдвига, левая часть будет расширена до типа int. Соответственно, значение типа 'int' можно сдвинуть на 20 бит.

    А теперь самый интересный момент. Это сдвиг отрицательных значений. Простейший пример:
    int A = -1 << 5; // undefined behaviour
    int B = -1 >> 5; // unspecified behavior

    В этом коде имеет место неопределённое и неуточненное поведение. С практической точки зрения разницы нет. Вывод один — так писать нельзя.

    На этом можно было бы поставить точку и привести пару примеров. К сожалению, есть два нюанса, которые портят идеальную картину мира.

    Нюансы, которые портят идеальную картину мира


    Нюанс N1. В старом стандарте языка Си++ от 1998 года ситуации с неопределенным поведением обходятся стороной. Сказано, как ведет себя оператор << при сдвиге беззнаковых значений. А про знаковые значения ничего не сказано. В общем, тот самый случай, когда чтение стандарта не прибавляет ясности. Не рассматривается такой случай и всё.

    Итак, с точки зрения Си++ от 1998 года, конструкция "-1 << 5" не приводит к неопределенному поведению. Впрочем, как она должна работать, тоже не описывается.

    Нюанс N2. Программисты смело во многих программах сдвигают отрицательные значения. И спорить с ними будет сложно, ведь код работает.

    Попробуем разобраться, следует ли из-за названных нюансов отказаться от новой диагностики. Мы думаем, что нет.

    В старом стандарте Си++ и не сказано про неопределенное поведение. В новом сказано. Получается, что старый стандарт просто был недостаточно точен. Кстати, в новом стандарте языка Си (я смотрел черновик от 25 июня 2010), также сказано, что сдвиги отрицательных значений приводят к неопределенному поведению. Вывод — следует избавиться от некорректного кода.

    Теперь по поводу повсеместного использования опасных сдвигов. Их действительно много. Например, в библиотеке JPEG необходимо заполнить массив следующими значениями:
    11111111111111111111111111111111b
    11111111111111111111111111111101b
    11111111111111111111111111111001b
    11111111111111111111111111110001b
    ...

    Это записано так:
    /* entry n is (-1 << n) + 1 */
    static const int extend_offset[16] = { 0,
      ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1,
      ((-1)<<4) + 1, ((-1)<<5) + 1, ((-1)<<6) + 1,
      ((-1)<<7) + 1, ((-1)<<8) + 1, ((-1)<<9) + 1,
      ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
      ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1
    };

    Сложно назвать библиотеку JPEG плохой. И этот код проверен временем и разными компиляторами.

    С точки зрения стандарта его теперь следует переписать так:
    static const int extend_offset[16] =
    { 0,
      ((~0u)<<1) | 1, ((~0u)<<2) | 1, ((~0u)<<3) | 1,
      ((~0u)<<4) | 1, ((~0u)<<5) | 1, ((~0u)<<6) | 1,
      ((~0u)<<7) | 1, ((~0u)<<8) | 1, ((~0u)<<9) | 1,
      ((~0u)<<10) | 1, ((~0u)<<11) | 1, ((~0u)<<12) | 1,
      ((~0u)<<13) | 1, ((~0u)<<14) | 1, ((~0u)<<15) | 1
    };

    Но стоит ли вносить такие правки решать вам. Я могу только дать совет всё-таки это сделать. Неизвестно когда и как, это может себя проявить.

    Можно привести другие примеры сдвигов отрицательных значений в разных программах. Но они все однотипны, так что читать про них будет не интересно.

    Выводы


    1. Раньше использование битовых операций и сдвигов было признаком мастерства программиста и позволяло писать быстрый код. Сейчас это почти не актуально. Намного важнее, чтобы код был понятным. Используйте игры с битами только в случае реальной необходимости.
    2. Выражения вида "-1 << N" теперь объявлены некорректными и производящими к неопределенному поведению.
    3. Выражения вида "-1 << N" давно и часто используются. Поэтому сложно привести реальные аргументы против использования таких конструкций. Аргументом являются только новые стандарты языков Си и Си++.
    4. Решайте сами, исправить сдвиг отрицательных значений или нет. Но я рекомендую исправить. Хотя бы на всякий случай.
    5. Диагностические сообщения, касающиеся опасных сдвигов будут доступны в PVS-Studio начиная с версии 4.60, которая скоро выйдет.


    Дополнительные ресурсы


    1. Не зная брода, не лезь в воду. Часть первая. http://habrahabr.ru/post/137039/
    2. Не зная брода, не лезь в воду. Часть вторая. http://habrahabr.ru/post/137411/
    3. Sean Eron Anderson. Bit Twiddling Hacks. http://www.viva64.com/go.php?url=837
    4. Wikipedia. Неопределённое поведение. http://www.viva64.com/go.php?url=663
    5. Wikipedia. Неуточняемое поведение. http://www.viva64.com/go.php?url=738
    6. Алёна C++. Разница между unspecified behavior и undefined behavior. http://www.viva64.com/go.php?url=739
    PVS-Studio
    Static Code Analysis for C, C++, C# and Java

    Comments 121

      0
      >> www.viva64.com/go.php?url=738
      А-та-та редирект ссылок использовать.
        +11
          –1
          Да я читал вашу статью.
          Я просто хотел напомнить, что на Хабре исторически не любят, когда не понятно куда ведёт ссылка. А за реферал ссылки минусуют по самое небалуйся.
          Хотя в остальных местах ваш подход преемлем.
            +15
            SEO-параноики могут обминусоваться. :) Мне всё равно. Мы делаем интересные статьи для людей и поддерживаем ссылки. Программисты читающие наши статьи не ждут от нас, что по ссылке «методы» они попадут на порносайт рассказывающий про методы…
            +2
            А как ваши редиректы помогут в случае пропажи контента по ссылке?
              0
              Тем, что мы время от времени мы отлавливаем такие ссылки. Вручную находим новое место со статьей и меняем в базе редирект.
                0
                Собственно для этого эта система и сделана. Почитайте статью.
                  +9
                  Имхо лучше бы было бы иметь ссылки такие: www.viva64.com/go/alenacpp.blogspot.com/2005/08/unspecified-behavior-undefined.html

                  Во-первых я понимаю куда меня редиректят и могу в случае недоверия руками скопипастить урл, второй момент я понимаю что и где искать, если вдруг ваша редиректилка перестанет работать (что вполне возможно).
                    0
                    А что делать, когда ссылка уедет? Оставить как есть (старый вариант)? Тогда зачем он…
                      +1
                      Показывать страничку со словами «Контент с данной страницы был удален, но присутствует здесь: %URL%. Перейти?».
              +3
              Bit twiddling hacks точно никуда не денется. Ожидал по ссылке [3] именно его, и очень удивился, обнаружив, что ссылка ведет на viva64.com.
            –2
            К чему приведёт?
            ((int)1) << 100

            Кроме 0 не может быть никаких других значений

            А в коде
            (UInt32)b << (8 * i)

            Вы уверены, что там именно 64 битное надо получить на выходе, а не 32? Может по алгоритму именно 32 надо.
              +1
              Хотя, похоже на то, что таки 64 надо.
                +2
                К чему приведёт? ((int)1) << 100

                Теоретически это приведёт к неопределенному поведению программы. Практически это приведёт к нулевому значению. Поэтому и шатко правило, выявляющее подобные участки кода. Решил написать статью. Быть может, кто-то остановит меня и аргументированно отговорит делать соответствующее диагностическое правило.
                  0
                  Результат зависит от платформы и опций компилятора. Можно и 0 получить и ненулевое значение.
                    0
                    А на практике это кто-то может показать? Конкретный компилятор, конкретную платформу.
                      +3
                      #include <stdio.h>
                      
                      int main()
                      {
                        volatile int i = 1;
                        printf("%d\n", (i << 100));
                      }
                      

                      msvc из SDK 7.1, 64 bit. Компилировать с -O2 и без оптимизации.
                        0
                        Нет под рукой. Прошу озвучить результат.
                          +5
                          без оптимизации: 16, с оптимизацией — 0;
                            0
                            Отлично. Спасибо.

                            Теперь бы ещё пример разного поведения для (-1)<<1 найти.
                              0
                              А почему оно разное? Где в Стандарте это написано?
                              Нельзя сдвигать влево на величины, большие или равные количеству бит, а на один бит — пожалуйста.
                                0
                                В статье приведён соответствующий фрагмент из стандарта:… Otherwise, if E1 has a signed type and non-negative value, and E1*2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
                                  +1
                                  А да, верно всё.
                                    0
                                    Можно попробовать сдвинуть до нуля, и ловить компилятор на оптимизациях, когда он считает значение всегда меньшим нуля. Ну и собственно, различные оптимизации и будут теми неприятными ситуациями, когда такие вещи выстрелят так, что расхлебывать будешь очень долго, имхо.
                                  +1
                                  нужна просто платформа, где отрицательные числа хранятся не в обратно-дополнительном коде. именно там -1 !== ~0
                                    –1
                                    Поправка: не в дополнительном коде.

                                    Уже обратный код дает -1 << 1 равным -3.
                                    Прямой код даст вообще 2 или -2 в зависимости от тонкостей реализации.
                      0
                      С чего это вдруг?
                        +1
                        Кроме 0 не может быть никаких других значений


                        Наивный компилятор, действуя по стандарту вполне мог бы сделать так:
                            mov cl, 100
                            mov eax, 1
                            shl eax, cl
                        

                        что было бы эквивалентно сдвигу влево на (100 % 32) = 4 с результатом 16.
                          0
                          Что-то мне ход мысли непонятен. Почему на 100%32?
                            0
                            А зачем в процессоре делать поддержку сдвига на «любое число»? Обычно железяка анализирует только последние 7 бит, игнорируя остальные. Это эквивалентно сдвигу на (N%32).
                              +1
                              Вы не имете в виду циклический побитовый сдвиг влево, а просто побитовый влево?
                              sar eax,100
                              действительно даст 16
                                0
                                Хотел написать sal eax, 100
                                  +3
                                  Смотрим Intel Manual:
                                  The destination operand can be a register or a memory location. The count operand
                                  can be an immediate value or the CL register. The count is masked to 5 bits (or 6 bits
                                  if in 64-bit mode and REX.W is used). The count range is limited to 0 to 31 (or 63 if
                                  64-bit mode and REX.W is used). A special opcode encoding is provided for a count
                                  of 1.
                                  То есть если вы напишете 100, это будет 0x64, после взятия младших 5 бит получится 4. 1<<4==16.
                                    +1
                                    И даже более того, на 8086 получится таки наверно 0 (цитата из той же книжки):
                                    The 8086 does not mask the shift count. However, all other IA-32 processors
                                    (starting with the Intel 286 processor) do mask the shift count to 5 bits, resulting in
                                    a maximum count of 31. This masking is done in all operating modes (including the
                                    virtual-8086 mode) to reduce the maximum execution time of the instructions.
                                    
                                      0
                                      Хе. Добавил себе ещё одно правило держать в голове)
                                      Хоть и ни разу больше, чем на 28 свдигать не приходилось
                                        –1
                                        Предлагаю приобрести PVS-Studio. :)
                                        Он будет помогать избегать таких пакостей и многих других, о которых можно даже не догадываться. Причём он будет делать это без устали и регулярно. Да ещё поможет новичкам, или тем, кто такие статьи не читает. Одно дело следить только за собой, а другое дело за всеми. :)
                                          0
                                          Вот сегодня, например, пакость.
                                          Имеется shared_ptr с контенером this. После выхода за область видимости он удаляется, при чём два раза, что вызывает, конечно segfault. Целый день долбался с этой проблемой.
                                            0
                                            А как так могло получиться?
                            –11
                            int A = -1 << 5; // undefined behaviour
                            int B = -1 >> 5; // unspecified behavior
                            >> Вывод один — так писать нельзя.
                            Глупость какая.
                            Если человек пишет такое, значит он рассчитывает на определённое поведение на целевых машинах.
                            Это может быть формирование масок или расширение знака в регистр для какого-нибудь abs(int):
                            sign= (x>>(sizeof(int)*8-1));
                            abs = (x^sign) — sign;

                            Все вменяемые современные CPU работают одинаково.
                              +2
                              1) Тогда прошу ответить на вопрос. Как следует относиться к следующему коду, рассчитанный на определённое поведение на целевых машинах? :-)
                              int A = 1;
                              int B = A++ + ++A;

                              2) Не понял про CPU. Речь о том, что компилятор для неопределенных и неуточненных случаев может построить код, вычисляющий мусорный результат.
                                0
                                >>int B = A++ + ++A;
                                Это говно, а не код. Умышленно запутанная конструкция.

                                int B = A >> 5; работает понятно и определённо.
                                Рассчитывать на странное поведение >> это всё равно что рассчитывать на 5-битные байты

                                >> Речь о том, что компилятор для неопределенных и неуточненных случаев может построить код, вычисляющий мусорный результат.

                                Назовите какой компилятор и какой CPU так делает. Или это теоретические рассуждения?

                                Логический сдвиг влево работает одинаково для всех значений и знаковых и беззнаковых.
                                Арифметический сдвиг вправо реплицирует старший бит.
                                Это работает одинаково на всех мне известных системах везде от 8биток до супекомпьютеров.

                                  +10
                                  Виталий, я рассчитываю, что через 2 дня будет готов новый рендер травы.
                                    –1
                                    ок ;-)
                                    +7
                                    Логический сдвиг влево работает одинаково для всех значений и знаковых и беззнаковых.


                                    Только что выше человек привёл пример, где (i << 100) даёт разный результат. :-)

                                    Аккуратнее, аккуратнее :-)
                                    Я вот очень аккуратен в исследованиях, вопросах и заметках. Я уже давно понял, что вообще не понимаю как писать на Си++ и как работают программы. :-)
                                      +1
                                      Если не доходить до безумия вроде (i << 100), где i это int32, то писать просто.
                                      Почему так получается? Потому что не думаю, что кому-то понравилась бы лишняя инструкция проверки длины операнда со стороны компилятора =)

                                      MSVC, допустим, без оптимизации, если всё выражение в конечном итоге константа, то он сразу режет эту ситуацию в ноль.
                                        0
                                        Не могу понять, как (a >> 5) превратилось в (i << 100)
                                        т.е. заведомо некорректный пример выхода за пределы разрядной сетки

                                        Также и второй вопрос остался без ответа.
                                        Так какой же компилятор и в каком режиме преобразует a>>5 в некорректный код.
                                        +7
                                        А Вам не приходит в голову, что стандарт пишется не роботами, а людьми? и раз там есть упоминание такой ситуации и это названо неопределенным поведением, значит это поведение действительно отличается где-то. Или нет никакой уверенности, что поведение не изменится. Стандарт составляется коммитетом, чей суммарный запас знаний о процессорах явно превышает Ваш.
                                          –2
                                          >>значит это поведение действительно отличается где-то
                                          на ламповом чуде 50-лохматого года работающем прямом коде?

                                          Утверждение уважаемого человека о том, что что-то делать нельзя только потому что возможно где-то нет арифметического сдвига вправо, очень странно слышать в свете ориентации его тулзы на современные платформы.

                                          Это понятно, что верификатор должен предупредить о несоответствии стандарту и т.п.
                                          Но от этого код, корректный для современных платформ, не станет вдруг некорректным.

                                            +1
                                            А вы пишите и запускаете тесты на целевых машинах, чтобы узнать являются ли они целевыми?
                                              –1
                                              целевые машины это те, на которых должен выйти продукт
                                                +1
                                                Вот именно. Вы всегда знаете, что это за машины?
                                      +1
                                      Вы неправы.
                                        –2
                                        Аргументированно.
                                        С чем конкретно вы не согласны? И какие рекомендуете принять меры.
                                        Как вы именно вы напишете хотя бы тот же abs(int) без бранчей и без сдвигов
                                          +6
                                          Я его не буду писать. Т.к. на тех платформах, где такой abs нужен, он уже написан и в виде intrinsic в компилятор встроен.
                                            –1
                                            Платформозависимый интринсик в VC?
                                            Вы слышали о GCC?
                                              +1
                                              1. intrinsic — всегда платформно-зависим.
                                              2. да.
                                                –1
                                                Мало того что платформо-, но и компиляторо-зависим.
                                                Какой интринсик мне написать, если код рассчитан под 4 различных аппаратных платформы?
                                                abs() это простейший пример.
                                                Вы на каждый случай будете требовать специальный интринсик от всех в мире разработчиков компиляторов, на которых вдруг запустят ваш код?

                                                  +3
                                                  Мне кажется, у вас какие-то превратные представления о том, как пишется код «рассчитанный на 4 различные архитектуры».

                                                  Кроме того, ваша реализация abs содержит ошибку — это лучшая демонстрация того, как делать не надо.
                                                    0
                                                    Т.е. если я хочу иметь портабельную эффективно работающую функцию это значит у меня какие-то превратные представления? =)
                                                    Использование интринсика для VC это, несомненно правильный путь.

                                                    >>Кроме того, ваша реализация abs содержит ошибку — это лучшая демонстрация того, как делать не надо.

                                                    За деревьями не видно леса?
                                                    abs это пример полезного использования сдвига

                                                    Какая ошибка? Переполнение?
                                                    Ну так просвятите, какой должен быть результат -0x80000000
                                                    в 32 битах
                                                +1
                                                cc -O0 21.c -o 22_0
                                                21.c: In function ‘main’:
                                                21.c:6:5: warning: left shift count >= width of type [enabled by default]
                                                holmes@darkstar:/home/projects/mc.old$ ./22_0
                                                16

                                                cc -O1 21.c -o 22_1
                                                21.c: In function ‘main’:
                                                21.c:6:5: warning: left shift count >= width of type [enabled by default]
                                                holmes@darkstar:/home/projects/mc.old$ ./22_1
                                                0

                                                  +2

                                                  1 #include <stdio.h>
                                                  2
                                                  3 int main()
                                                  4 {
                                                  5 int i = 1;
                                                  6 printf("%d\n", (i << 100));
                                                  7 }
                                                    –2
                                                    Уважаемый, вы на что отвечаете?
                                                    Мы обсуждали платформонезависимый abs, в частности реализованный через арифметический сдвиг руками _вправо_, ровно как и в «православном, платформозависимом интринсике VC»

                                                    что должен значить в данном контексте (i<<100)?
                                                      +1
                                                      что оно собрано под gcc
                                            +5
                                            Все, да не все…

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

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

                                            Иными словами, если сдвигать влево на 1 бит число
                                            1010 1010 1010 1010b

                                            то может получиться как
                                            0101 0101 0101 0100b

                                            так и
                                            1101 0101 0101 0100b.

                                            Язык C является многоплатформенным, и потому его создателям пришлось выбирать между неопределенным поведением и сложной реализацией операции знакового сдвига влево. Насколько я понимаю ситуацию, плюсы и минусы обоих решений выглядят так:

                                            Неопределенное поведение:
                                            +: операция << всегда компилируется в одну инструкцию,
                                            -: непереносимый код.

                                            Сложная реализация:
                                            +: переносимый код,
                                            -: операция << для знаковых чисел компилируется в несколько инструкций.

                                            При этом минус сложной реализации проявляется всегда, а минус неопределенного поведения — как правило, только если есть переполнение (иными словами, -1 << 1 всегда будет 2, за исключением совсем уж эзотерических процессоров). Именно потому неопределенное поведение и прописано в стандарте.
                                              0
                                              UPD: совсем забыл (хорошо хоть romy4 напомнил) что -1 << 1 равно -2 только для платформ, использующих дополнительный код
                                                –3
                                                >> Все, да не все…
                                                Обратите внимание на то что я написал
                                                «Все вменяемые современные CPU работают одинаково. „

                                                >>к сожалению, быстрое гугление не помогло мне вспомнить их названия
                                                О том и речь. Никто в этой теме не смог ни указать название процессора, ни компилятора,
                                                который сгенерит некорректный код.
                                                Я подожду, назовите пожалуйста модель современного процессора, который не поддерживает арифметический сдвиг вправо в дополнительном коде.

                                                А уж вопрос о том, пойдёт ли PVS-Studio на такой машине, я думаю и не стоит
                                                    –1
                                                    Tracker: Bugs
                                                      0
                                                      > Non-discrepant; no change will be implemented.
                                                        –1
                                                        To clarify: the right shift operator SHOULD be logical, but in mspgcc an
                                                        arithmetic shift is used.

                                                        Т.е. ваш баг как раз подтверждает моё утверждение
                                                        в т.ч. арифметический сдвиг вправо работает одинаково
                                                        MSP430 это к тому же не процессор общего назначения, а 16битный DSP

                                                          +1
                                                          MSP430 это general-purpose 16тибитный контролер с малым энергопотреблением, а никак не DSP. То, что в наборе инструкций присутствует MAC-операции его не делает DSP.
                                                            +1
                                                            Хорошо.
                                                            Но это опять же не отменяет того факта, что «хороший и правильный» логический сдвиг вправо на нём _не работает_, а «нехороший и нестандартный» сдвиг знакового числа _работает_.

                                                            Правду минусами не победишь =)
                                                              +2
                                                              То, что баг-репортер ожидал такого поведения не значит, что это баг.

                                                              В стандарте, процитированном выше, сказано, что если сдвиг вправо применен к отрицательному числу, то результат зависит от имплементации.

                                                              Стоит также помнить, что у разных процессоров разный набор инструкций. И довольно часто присутствуют и логический, и арифметический сдвиги вправо (старший бит расширяется вправо). Иногда ещё присутствуют до двух видов кольцевых сдвигов (в одном направлении). И в языке C используется только один вариант сдвига, остальные — недоступны.
                                                                –1
                                                                Я, похоже, не совсем догоняю смысл этого багрепорта.
                                                                К какому типу был применён арифметический сдвиг?
                                                                Если к знаковому, то RRA работает точно так же как и на любых других современных процессорах.
                                                                Я уж не знаю что хотел сказать gribozavr этой ссылкой.

                                                                PS: смотрите профайл

                                                                  –2
                                                                  >> В стандарте, процитированном выше, сказано, что если сдвиг вправо применен к отрицательному числу, то результат зависит от имплементации.
                                                                  В теории мы бы уже жили при полном коммунизме.

                                                                  Вот я и спрашиваю, в КАКОЙ имплементации он работает НЕ ТАК как у всех?
                                                                  За вопросы тут минусуют на них не отвечая, а я это очень хочу, наконец, узнать.

                                                                  >>И в языке C используется только один вариант сдвига, остальные — недоступны.
                                                                  Недоступны кому?
                                                                  -1 >> 5
                                                                  1 >> 5

                                                                  ГДЕ они оба недоступны? Назовите компилятор, пожалуйста
                                                                    +1
                                                                    Вам привели пример — mspgcc.
                                                                      +1
                                                                      Недоступны разработчику. Поясню, что имею ввиду. На многих контроллерах есть следующие инструкции сдвига вправо: логический, арифметический, циклический. Плюс эти же с участием бита в флаге переноса.

                                                                      Из C с помощью операции >> доступен только один. В библиотеках компиляторов для таких архитектур, как правило, есть макросы, содержащие ассемблерные вставки для доступа.

                                                                      И это нормально. Это — непереносимая часть, поэтому она не входит в состав С, разработанного, как низкоуровневый переносимый язык.
                                                          0
                                                          rla dst; arithmetic shift left emulated
                                                          rra src; arithmetic shift right

                                                          Arithmetic shift inserts zeroes for left shifts but the most significant bit, which
                                                          carries the sign, is replicated for right shifts.
                                                      +2
                                                      sign= (x>>(sizeof(int)*8-1));
                                                      abs = (x^sign) — sign;


                                                      Что выдаст ваш код, если x равняется INT_MIN?
                                                        –1
                                                        Некорректный результат.
                                                        Вас не смущает что INT_MIN*2 приводит к переполнению?
                                                          +5
                                                          То есть самописная функция abs, которая возвращает отрицательные значения вам кажется нормальной?

                                                          Ну, ок.
                                                            0
                                                            Компьютерная целочисленная арифметика работает с конечной разрядной сеткой.
                                                            В этом нет ничего удивительного.
                                                            Не хватает 32 бит, используйте 64.
                                                            Любая функция в т.ч. не самописная не сможет в 32битах представить положительный результат от предельного отридцательного числа.
                                                            И какое это имеет отношение к обсуждаемому сдвигу?
                                                      +1
                                                      Да как-то некрасиво вы со ссылками поступаете. Уж на википедию можно прямую ссылку давать неглядя да и вообще, ощущение что проблема высосана из пальца и «да мы же о вас заботимся!» смотрится как оправдание.
                                                        0
                                                        Прочитайте статью «Д'Артаньян и интернет, или работа над проблемой битых ссылок».
                                                          0
                                                          На Wikipedia ссылки плавают. Что-то удаляют, что-то объединяют, что-то переименовывают.
                                                          0
                                                          А не мог бы автор объяснить это утверждение:
                                                          int A = -1 << 5; // undefined behaviour
                                                          • UFO just landed and posted this here
                                                              0
                                                              Не, мне цитату из Стандарта надо.
                                                                0
                                                                Чуть выше подсказали уже, спасибо.
                                                              0
                                                              С точки зрения стандарта его теперь следует переписать так:
                                                              static const int extend_offset[16] =
                                                              { 0,
                                                              ((~0u)<<1) | 1, ((~0u)<<2) | 1, ((~0u)<<3) | 1,
                                                              ((~0u)<<4) | 1, ((~0u)<<5) | 1, ((~0u)<<6) | 1,
                                                              ((~0u)<<7) | 1, ((~0u)<<8) | 1, ((~0u)<<9) | 1,
                                                              ((~0u)<<10) | 1, ((~0u)<<11) | 1, ((~0u)<<12) | 1,
                                                              ((~0u)<<13) | 1, ((~0u)<<14) | 1, ((~0u)<<15) | 1
                                                              };


                                                              А разве int всегда 32-битный? Опыть стандарты поменяли пока я спал? Или JPEG под микроконтроллеры уже не можно компилировать? :(
                                                                0
                                                                А причем тут размер int? Здесь нигде 32 бита не вспоминается.
                                                                P.S. Мой код тоже не идеал, но по крайней мере нет сдвига отрицательных чисел. Сейчас думаю, что ещё бы неплохо было сам массив extend_offset сделать unsigned.
                                                                  0
                                                                  Литеральный конструктор «0u»? Что обозначает буковка «u»?
                                                                    0
                                                                    unsigned int
                                                                      –1
                                                                      Да. Соответственно, при этом и размер int. На мой профессиональный взгляд, приведенный код будет компилироваться некорректно, если размер «int» отличается от 32 бит — embedded всякий и прочая бесовщина, для которой JPEG регулярно компилируется. Вот я интересуюсь — это код неправильный или я что-то проспал?
                                                                        –1
                                                                        int в С/С++ — от 16 битов и выше.
                                                                          +1
                                                                          Соответственно, при этом и размер int

                                                                          Загадочное предложение. Что при этом размер int?

                                                                          unsigned может быть добавлен к любому целочисленному типу, это не повлияет на размер типа. C99 об этом говорит следующее (6.2.5:6):

                                                                          For each of the signed integer types, there is a corresponding (but different) unsigned
                                                                          integer type (designated with the keyword unsigned) that uses the same amount of
                                                                          storage (including sign information) and has the same alignment requirements.
                                                                          

                                                                          На мой взгляд приведённый код будет отлично компилироваться, с теми же результатами, что и оригинальный код.
                                                                            0
                                                                            Компилируем под эмбеддед, int 16 бит. Конструкция "~0u" превращается в двоичное «1111111111111111b», правильно? А в условиях задачи нужно получить «11111111111111111111111111111111b». То что код компилируется — это, конечно, хорошо — но, ИМХО, неплохо было бы чтобы он еще и работал :).
                                                                              0
                                                                              А, вон вы о чём. Да хз откуда эти условия в таком виде у автора. А вот код скомпилируется одинаково.
                                                                                +1
                                                                                Нет, получить в случае 16-битного int нужно будет как раз 1111111111111111b, что собственно и произойдет. Я написал 11111111111111111111111111111111b для примера, имея в виду 32-битный int. Если бы я написал, скажем, 12 единичек (бывают 12-битные int), вопросов было гораздо больше. :)
                                                                                  0
                                                                                  бывают 12-битные int

                                                                                  Это где так?
                                                                                    0
                                                                                    http://en.wikipedia.org/wiki/12-bit:
                                                                                    Possibly the best-known 12-bit CPU is the PDP-8 and its relatives, produced in various incarnations from August 1963 to mid-1990. Many ADCs (analog to digital converters) have a 12-bit resolution. Some PIC microcontrollers use a 12-bit word size.

                                                                                      0
                                                                                      То есть вы утверждаете, что:
                                                                                      1. на нем есть ANSI C,
                                                                                      2. SHRT_MAX на этой платформе меньше 32767.

                                                                                      Так?
                                                                                        +1
                                                                                        Я не знаю. :)
                                                                                          0
                                                                                          Я к тому, что Стандарт ANSI C _требует_ чтобы тип int содержал как минимум 16 бит. Поэтому очень странно выглядит утверждение о 12-битном int'е.

                                                                                          Возможно, вы его с «машинным словом» путаете.
                                                                                            0
                                                                                            Да, действительно. Как то не подумал. Возможно там нет Си.
                                                                                              +1
                                                                                              Вы не могли бы указать, какой пункт стандарта это требует, а то я не смог с ходу найти?
                                                                                                +1
                                                                                                Во-первых, я не туда ответил, а во вторых, я сам нашёл: С99 пункт 5.2.4.2.1 Sizes of integer types
                                                                                      0
                                                                                      Это хорошо, значит у меня еще не съехала крыша :).
                                                                        +7
                                                                        Как же я хочу пожать вам руку за этот текст!
                                                                        Я уже устал объяснять «закаленным в тяжелых боях» сишникам, что их код, наполненный сдвигами, чарпойнтерами и прочим гавном мамонта не дает никакой реальной выгоды, по сравнению с любым современным высокоуровневым API (говорю сейчас, в частности, про мобильные ОС). Эти люди, на пафосе, рассуждают о быстродействии, но код, в результате, невозможно прочитать и невозможно поддерживать.

                                                                        Если говорить о современных мобильных ОС, то везде есть классы, для работы с битами. И на эти классы, по крайней мере, можно положиться в плане надёжности. В плане быстродействия, наверное, можно написать магический код, который будет работать чуть-чуть быстрее. Но понять этот код будет практически невозможно никому, кроме его автора. Да и сам автор через две недели будет несколько часов задумчиво чесать затылок, глядя на такой шедевр…

                                                                          +3
                                                                          Подтверждаю. Читать код со сдвигами и побитовыми операциями очень трудно. Вдобавок там часто используются макросы. Это тяжёлое наследие. Но печальнее, что и сейчас продолжают так писать.
                                                                            +9
                                                                            Вы не берёте во внимание хотя бы работу с железом в драйвере, где нет «то везде есть классы, для работы с битами» и «любым современным высокоуровневым API», в том числе и в ваших любимых мобильных ОС. Потому ваш взгляд довольно однобок и не затрагивает всех аспектов. Далеко не все железячники соглашаются не экономить биты в адресном пространстве своей железки — у них оно не резиновое и свопов нет, а ещё и может быть ограничено пропускной способностью шины или другими железками в цепочке.

                                                                            Вообще наблюдаю картину, что многие программисты уже забывают, что есть и нижний уровень программ, где многие обплёвываемые ими, якобы устаревшие методы, вполне в ходу, т.к. огромные неповоротливые «высокоуровневые API» и «классы для работы с битами» либо просто не существуют (и не будут существовать), либо не могут обеспечить достаточной скорости. Зато когда доходит до дела и надо железку заставить работать, то вдруг выясняется, что и методы не такие уж и плохие и высокоуровневые плюшки не так уж хороши.
                                                                              +7
                                                                              Автор как раз и говорит, что использовать эти инструменты без необходимости, в современных условиях, не просто плохой тон, а, практически, преступление.

                                                                              Там, где это необходимо — вопросов быть не может. Любой инструмент надо уметь применять. Но когда человек начитался махровых книг 90х годов по С/C++, в которых было написано, что с помощью сдвига можно в 100 ускорить умножение на степень двойки и теперь лепит такой код на каждом шагу, осложняя жизнь окружающим людям… Это уже клиника. И лечится очень тяжело.
                                                                              +1
                                                                              Плюс есть большое количество разнообразных процессоров, микроконтроллеров и DSP, оптимизация в компиляторах которых хромает (и сдвиговые операции часто быстрее и удобнее, чем умножение/деление). И, естественно, для них нет высокоуровневых API, виртуальных машин.
                                                                                0
                                                                                Сдвиги всегда быстрее чем деление. Умножение может быть однотактовым, но обычно занимает 2 и более тактов.
                                                                                  +1
                                                                                  И то, и то может исполняться за 1 такт. Это уже не быстрее.

                                                                                  На суперскалярных архитектурах они вообще не сравнимы: что быстрее зависит от занятости модулей АЛУ и умножителей, зависимостей кода и других факторов. Дисциплин планирования исполнения микрокода, например.
                                                                                –1
                                                                                Ерунда. У меня не было таких проблем, хотя я написал довольно много кода для работы с битовыми потоками. Ни с написанием, ни с последующим чтением кода.
                                                                                А эти ваши замечательные классы (которые зачастую даже нумерацию бит используют не в соответствии с весами разрядов 2^n, а с начиная дибильной единицы), как правило говно такое, которое на чистом си написать невозможно никакими способами, хотя говнокода на си довольно много, как верно вами замечено.
                                                                                –4
                                                                                Зачастую программистам приходится идти на компромиссы и пользоваться недокументированными возможностями, мир не идеален. И это касается не только ужасного говна мамонта, которым «современные» програмисты любят называть код, содержащий менее 9000 уровней абстракции, не говоря уж о (фу какая гаадость) чистом си, в котором даже сложениие выполняется просто оператором a+b, а не какимнить AdditionAbstractFactory. Пусть -1 << n это недокументированная возможность, но код более чем предсказуемо выливается в обычную команду sar, чем во многих случаях можно и стоит воспользоваться.
                                                                                  –2
                                                                                  -1 >> 1 в команду sar, а -1 << n в команду sal (которая эквивалентна shl), если быть точнее -_-

                                                                                Only users with full accounts can post comments. Log in, please.