Unexpected results of C / C ++ bitwise shift operators
I think I'm going to go crazy.
I have a piece of code that needs to create an (unsigned) integer with N
consecutive bits set to 1. More precisely, I have a bitmask and in some situations I would like to set it to a solid rnage.
I have the following function:
void MaskAddRange(UINT& mask, UINT first, UINT count)
{
mask |= ((1 << count) - 1) << first;
}
In simple words: 1 << count
in binary representation 100...000
(the number of zeros is count
), subtracting 1 from that number gives 011...111
, and then we just shift it left by first
.
The above should produce the correct result when the following obvious constraints are met:
first + count <= sizeof(UINT)*8 = 32
Note that it also works correctly for "extreme" cases.
- if
count = 0
we have(1 << count) = 1
and therefore((1 << count) - 1) = 0
. - if
count = 32
we have(1 << count) = 0
, since the initial bit overflow and according to the rules of C / C ++ bitwise shift operations are not circular . Then((1 << count) - 1) = -1
(all bits are set).
However, as it turns out, the count = 32
formula doesn't work as expected. As discovered:
UINT n = 32;
UINT x = 1 << n;
// the value of x is 1
Also, I am using MSVC2005 environment. When I evaluate the above expression in the debugger, the result is 0. However, when I step through the above line, it x
gets the value 1. Lokking through the disassembler we see the following:
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
There is no magic, the compiler just used the instruction shl
. Then it seems that shl
it does not do what I expected from it. Either CPU chooses to ignore this instruction, or the shift is being processed modulo 32, or something is not.
My questions:
- What is the correct behavior of the
shl
/ instructionsshr
? - Is there a cpu flag that controls the instructions for the voltage battle?
- Is this according to the C / C ++ standard?
Thank you in advance
Edit:
Thanks for answers. I figured out that (1) shl
/ shr
does handle the modulo 32 operand (or both 0x1F) and (2) the C / C ++ standard treats shifting more than 31 bits as undefined behavior.
Then I have one more question. How can I rewrite my "escaping" expression to cover this edge case. It must be without branching ( if
, ?
). What would be the simplest expression?
source to share
1U << 32
is undefined behavior in C and in C ++ when the type unsigned int
is 32-bit wide.
(C11, 6.5.7p3) "If the value of the correct operand is negative or greater than or equal to the width of the promoted left operand, the behavior is undefined."
(C ++ 11, 5.8p1) "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.
source to share
The shift is in number or more bits than the integer type you are shifting is undefined in C and C ++. On x86 and x86_64, the shift value of the shift instructions is actually processed modulo 32 (or regardless of the size of the operand). However, you cannot rely on this modulo behavior to be generated by your compiler from C or C ++ >>
/ operations <<
unless your compiler explicitly guarantees it in its documentation.
source to share
I think the expression is the 1 << 32
same as 1 << 0
. The IA-32 instruction set manual says that the offset instruction counter operand is masked to 5 bits.
A link to the IA-32 architecture instruction set can be found here .
To fix the "extreme" case, I can only think of the following code (maybe buggy), which might be a little awkward:
void MaskAddRange(UINT *mask, UINT first, UINT count) {
int count2 = ((count & 0x20) >> 5);
int count1 = count - count2;
*mask |= (((1 << count1) << count2) - 1) << first;
}
The basic idea is to split the shift operation so that each shift does not exceed 31. Apparently, the above code assumes that the counter is in the range 0..32, so it is not very reliable.
source to share
If I understood the requirements, do you want an unsigned int with the top N bits set?
There are several ways to get the result (I think) you want. Edit: I am worried that this is not very reliable and won't work for 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];
}
This should be pretty fast since it's only 132 bytes of data.
To make it robust, I'll either expand for all values to 63 or make them conditional, in which case it can be done with a version of your original masking of the + bits in the case of 32. That is.
source to share
My 32 cents:
#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);
}
List 1.
A safe version with a dummy / semi-circular result could be:
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);
}
List 2.
Doing this without branching or local variables could be something like:
return n | (~0u >> ((INT_BIT - c) % INT_BIT)) << (f % INT_BIT);
List 3.
List 2 and List 3 This will give the "correct" result if from
less INT_BIT
and> = 0. Ie:
./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
source to share
You can avoid undefined behavior by splitting the shift operation in two steps, the first bit by bit (count - 1) and the second by one bit. Special care is required if the number is zero:
void MaskAddRange(UINT& mask, UINT first, UINT count)
{
if (count == 0) return;
mask |= ((1 << (count - 1) << 1) - 1) << first;
}
source to share