Неожиданный результат C / C ++ побитовых операторов сдвига

Question

Я думаю, что схожу с ума от этого.

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

У меня есть следующая функция:

void MaskAddRange(UINT& mask, UINT first, UINT count)
{
    mask |= ((1 << count) - 1) << first;
}

Простыми словами: 1 << count в двоичном представлении100...000 (число нулей равно count), вычитая 1 из такого числа, получаем 011...111, а затем мы просто сдвигаем его влево на first.

Вышеприведенное должно дать правильный результат,когда соблюдается следующее очевидное ограничение:

first + count <= sizeof(UINT)*8 = 32

Обратите внимание , что оно должно также корректно работать в «экстремальных» случаях.

• если count = 0, у нас есть (1 << count) = 1, и, следовательно, ((1 << count) - 1) = 0.
• , если count = 32, у нас есть (1 << count) = 0, так как старший бит переполняется, и в соответствии сПравила C / C ++ для операций побитового сдвига не циклические .Затем ((1 << count) - 1) = -1 (все биты установлены).

Однако, как оказалось, для count = 32 формула не работает должным образом.Как обнаружилось:

UINT n = 32;
UINT x = 1 << n;
// the value of x is 1

Более того, я использую MSVC2005 IDE.Когда я вычисляю вышеприведенное выражение в отладчике, результат равен 0. Однако когда я перешагиваю через вышеприведенную строку, x получает значение 1. При просмотре через дизассемблер мы видим следующее:

mov eax,1 
mov ecx,dword ptr [ebp-0Ch] // ecx = n
shl eax,cl                  // eax <<= LOBYTE(ecx)
mov dword ptr [ebp-18h],eax // n = ecx

В этом нет никакой магии, компилятор просто использовал shl инструкцию.Тогда кажется, что shl не делает то, что ожидал.Либо ЦП решает игнорировать эту инструкцию, либо сдвиг обрабатывается по модулю 32, или не знаю.

Мои вопросы:

• Какое правильное поведение shl / shr инструкции?
• Есть ли флаг CPU, управляющий инструкциями по сдвигу битов?
• Соответствует ли это стандарту C / C ++?

Заранее спасибо

Редактировать:

Спасибо за ответы.Я понял, что (1) shl / shr действительно обрабатывает операнд по модулю 32 (или & 0x1F) и (2) стандарт C / C ++ рассматривает сдвиг более чем на 31 бит как неопределенное поведение.

Тогда у меня есть еще один вопрос.Как я могу переписать свое «маскирующее» выражение, чтобы охватить и этот крайний случай.Должно быть без разветвления (if, ?).Какое самое простое выражение?

Answer 1

1U << 32 - неопределенное поведение в C и C ++, когда тип unsigned int имеет ширину 32 бита.

(C11, 6.5.7p3) "Если значение правого операнда отрицательно или больше или равно ширине повышенного левого операнда, поведение не определено"

(C ++ 11, 5.8p1) "Поведение не определено, если правый операнд отрицательный или больше или равен длине в битах повышенного левого операнда."

Answer 2

Сдвиг на столько или больше битов, чем в целочисленном типе, который вы сдвигаете, равен undefined в C и C ++.В x86 и x86_64 величина сдвига команд сдвига действительно обрабатывается по модулю 32 (или независимо от размера операнда).Однако вы не можете полагаться на то, что это поведение по модулю генерируется вашим компилятором из операций C или C ++ >> / <<, если только ваш компилятор явно не гарантирует это в своей документации.

Answer 3

Я думаю, что выражение 1 << 32 такое же, как 1 << 0.Ссылка на набор команд IA-32 говорит, что операнд подсчета команд сдвига маскируется до 5 битов.

Ссылка на набор команд для архитектур IA-32 может быть найдена здесь .

Чтобы исправить «экстремальный» случай, я могу придумать только следующий код (возможно, с ошибками), который может быть немного неловким:

void MaskAddRange(UINT *mask, UINT first, UINT count) {
    int count2 = ((count & 0x20) >> 5);
    int count1 = count - count2;
    *mask |= (((1 << count1) << count2) - 1) << first;
}

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

Answer 4

Мои 32 цента:

#include <limits.h>

#define INT_BIT     (CHAR_BIT * sizeof(int))

unsigned int set_bit_range(unsigned int n, int frm, int cnt)
{
        return n | ((~0u >> (INT_BIT - cnt)) << frm);
}

^{Список 1.}

Безопасная версия с поддельным / полукруглым результатом может быть:

unsigned int set_bit_range(unsigned int n, int f, int c)
{
        return n | (~0u >> (c > INT_BIT ? 0 : INT_BIT - c)) << (f % INT_BIT);
}

^{Список 2.}

Выполнение этого без ветвления или локальных переменных может выглядеть примерно так:

return n | (~0u >> ((INT_BIT - c) % INT_BIT)) << (f % INT_BIT);

^{Список 3.}

Список 2 и Список 3 Это даст "правильный" результат, если from меньше INT_BIT и> = 0. I.e.:

./bs 1761 26 810
Setting bits from 26 count 810 in 1761 -- of 32 bits
Trying to set bits out of range, set bits from 26 to 836 in 32 sized range
x = ~0u       =  1111 1111 1111 1111 1111 1111 1111 1111

Unsafe version:
x = x >> -778 =  0000 0000 0000 0000 0000 0011 1111 1111
x = x <<  26  =  1111 1100 0000 0000 0000 0000 0000 0000
x v1 Result   =  1111 1100 0000 0000 0000 0110 1110 0001
Original:        0000 0000 0000 0000 0000 0110 1110 0001    

Safe version, branching:
x = x >>   0  =  1111 1111 1111 1111 1111 1111 1111 1111
x = x <<  26  =  1111 1100 0000 0000 0000 0000 0000 0000
x v2 Result   =  1111 1100 0000 0000 0000 0110 1110 0001
Original:        0000 0000 0000 0000 0000 0110 1110 0001    

Safe version, modulo:
x = x >>  22  =  0000 0000 0000 0000 0000 0011 1111 1111
x = x <<  26  =  1111 1100 0000 0000 0000 0000 0000 0000
x v3 Result   =  1111 1100 0000 0000 0000 0110 1110 0001
Original:        0000 0000 0000 0000 0000 0110 1110 0001

Answer 5

Если я понял требования, вы хотите беззнаковое целое с установленными старшими N битами?

Есть несколько способов получить желаемый результат (я думаю).Изменить: я беспокоюсь, что это не очень надежный, и не получится при n> 32:

uint32_t set_top_n(uint32 n)
{
    static uint32_t value[33] = { ~0xFFFFFFFF, ~0x7FFFFFFF, ~0x3FFFFFFF, ~0x1FFFFFFF,
                                  ~0x0FFFFFFF, ~0x07FFFFFF, ~0x03FFFFFF, ~0x01FFFFFF,
                                  ~0x00FFFFFF, ~0x007FFFFF, ~0x003FFFFF, ~0x001FFFFF,
                                  // you get the idea
                                  0xFFFFFFFF
                                  };
    return value[n & 0x3f];
}

Это должно быть довольно быстро, так как это всего 132 байта данных.

Чтобы сделать его более устойчивым, я бы либо расширил его для всех значений до 63, либо сделал бы его условным, в этом случае это можно сделать с помощью версии вашей исходной битовой маскировки + случая 32.Т.е.

Answer 6

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

void MaskAddRange(UINT& mask, UINT first, UINT count)
{
  if (count == 0) return;
  mask |= ((1 << (count - 1) << 1) - 1) << first;
}