Search code examples
cbit-shift

Getting unexpected results when shifting a 32-bit integer more than 32 times

I would like clarification on why some bit shifting is doing something I wouldn't expect.

I developed a function, setBitsVersion1 that sets bits to 1 in an array of 32 bit integers using the regular int primitive type. So this means that bit positions [0, 31] are for the first integer in the array, bit positions [32, 63] are for the second integer in the array etc. For example, position 10 is position 10 at the first integer, but position 35 is really position 3 in the second integer. So, if bitPosition were 35, then line 4 would become a[1] = a[1] | one << 3 thus setting the bit at position 3. This function behaves as expected, and you can see in the output when it prints the integers, the integer that prints is correct since the bit for the binary 2^3 position was set.

However, the next part is where I'm confused. I wrote a second implementation, setBitsVersion2, that gets rid of line line 3 so the original bitPosition is never modified to be the correct bit position at a particular index. So, using 35 again the line would become a[1] = a[1] | one << 35. It's my understanding that left shifting 32 bits or more is undefined behavior. I'm not exactly sure what I would expect to print, but I definitely wouldn't of expected it to set the bit at position 3 because 1 << 35 is not 1 << 3 and shifting by 35 times is undefined behavior. Maybe I would've expected the integer to be zero, since in the past when I've shifted integers 32 times or more, it just ends up being 0. Regardless, I'm just confused as to why doing 1 << 35 produces the same results 1 << 3 since I would've expected it not to work and would like an explanation.

And in case the kind of machine/compiler I'm using is relevant, then I'm on a Windows computer using Microsoft Visual Studio 2019. Though, I also tested it out on Linux using gcc and got the same results.

CODE

#include <stdio.h>

void setBitVersion1(int* a, int bitPosition);
void setBitVersion2(int* a, int bitPosition);
void printArray(int* a, int size);

int main(int argc, char* argv[]) {
    printf("Correct implementation - setBitsVersion1 - results are correct and what is expected\n");
    int a1[5] = { 0 };
    int a1Size = sizeof(a1) / sizeof(*a1);
    setBitVersion1(a1, 35);
    setBitVersion2(a1, 67);
    printArray(a1, a1Size);
    printf("\n\n");

    printf("Incorrect version - setBitsVersion2 - still produces the same results?\n");
    int a2[5] = { 0 };
    int a2Size = sizeof(a2) / sizeof(*a2);
    setBitVersion1(a2, 35);
    setBitVersion2(a2, 67);
    printArray(a2, a2Size);

    return 0;
}

void setBitVersion1(int* a, int bitPosition) {
    int one = 1;                                // line 1
    int index = bitPosition / 32;               // line 2
    bitPosition = bitPosition % 32;             // line 3
    a[index] = a[index] | one << bitPosition;   // line 4
}

void setBitVersion2(int* a, int bitPosition) {
    int one = 1;
    int index = bitPosition / 32;
    a[index] = a[index] | one << bitPosition;
}

void printArray(int* a, int size) {
    for (int i = 0; i < size; i++)
        printf("%d\n", a[i]);
}

OUTPUT

Correct implementation - setBitsVersion1 - results are correct and what is expected
0
8
8
0
0


Incorrect version - setBitsVersion2 - still produces the same results?????
0
8
8
0
0
Solution

  • 1 << 35 can produce 1 << 3 because the machine instruction for shifting a 32-bit value has only five bits in the field for the shift amount. When 35 (binary 100011) is used, the processor sees only five bits (00011), which is 3, so it shifts by 3 bits. Of course, other behaviors are possible; the compiler might calculate the shift itself using more complicated software while compiling or might use a different instruction with different behavior.

    It's my understanding that left shifting 32 bits or more is undefined behavior. I'm not exactly sure what I would expect to print, but I definitely wouldn't [have] expected it to set the bit at position 3 because 1 << 35 is not 1 << 3 and shifting by 35 times is undefined behavior.

    Of course you “wouldn't have expected” it to set the bit at position 3 or do anything else in particular, because the C standard does not give you any expectation. To have an expectation, you must have some grounds for expecting, such as statements in the C standard about how it should behave or familiarity with how compilers are written or knowledge of processor instructions. Be on guard for expecting certain things to occur—or even for expecting certain things not to occur—when you do not have grounds for it.