CODEWITHSUNDEEP
pythonc
b3nj4m1n
b3nj4m1n

Reputation: 524

Bitwise rotation function in c

I need to translate a python function to c. All the bitwise operators seem to be the same in c, so I thought I could pretty much just copy the code and add a semicolon. Here is the python code:

def ROTR(x, n, w=32):
    return ((x >> n) | (x << w - n)) & ((1 << w) - 1)

This works as it should, running it on the number 5, with a shift of 1 and w=32 yields 2147483650.

Here is my c function:

int ROTR(int x, int n, int w) {
    return ((x >> n) | (x << w - n)) & ((1 << w) - 1);
}

This yields 0, with the same parameters.

I tried taking the function apart, but I can't figure out what causes this mistake.

Upvotes: 3

Views: 340

Answers (1)

Eric Postpischil
Eric Postpischil

Reputation: 223264

In C, left shifts of int and other signed integers are undefined when overflow occurs, and right shifts of negative values are implementation-defined. Therefore, shifting 5 left by w - n = 32 − 1 = 31 bits with a 32-bit int has undefined behavior.

To avoid this, use an unsigned integer type for shifting. While you can use unsigned int, it may be preferable to include <stdint.h> and use a type with a specific width, such as uint32_t:

uint32_t ROTR(uint32_t x, int n, int w)
{
    return x >> n | x << w-n;
}

Additionally, shifting by an amount greater than or equal to the width of the left operand is undefined, so 1 << w is undefined when w is 32 and int is 32 bits. This attempt at masking with ((1 << w) - 1) may also be unnecessary; when left operand of a shift and/or the function return type is an unsigned integer type, evaluations will automatically be performed as if masked. (If you want the function to support narrower words than its nominal type, then a mask could be useful. However, you must either construct it carefully to avoid undefined behavior or you must apply it conditionally, not in the case that w is the width of the nominal type.)

Upvotes: 4

Related Questions