It's one of the newbie HackerRank problems, where it asks to flip bits of a long represented by 32 bits, and return the value.

e.g.:

1 is represented as: 00000000 00000000 00000000 00000001

~ operator flips its bits.

so ~1 = 11111111 11111111 11111111 11111110

When I do ~1 on a long, it returns -2, not 4294967294 despite both are represented equally in 32 bit binary form.

I implemented the code below:

long flippingBits(long n) {
    unsigned long m = n;
    unsigned long x = ~n;
    return x;
}

I got -2 as result. I tried with just "long", but got same result. I tried casting too with unsigned long x = (unsigned long)~n; but got same results again.

So then I just used XOR operation and it worked:

long flippingBits(long n) {
    unsigned long m = n;
    unsigned long x = n ^ 4294967295;
    return x;
}

Why ~ operation of 1 not represented as 4294967294 but -2 in C? What do I need to do to make ~ operator return 4294967294 and not -2 (if it's possible)?

CodePudding user response：

~ is applied on an operand n which is of type signed long. Assuming 32 bit long then binary it will become 11111111 11111111 11111111 11111110 indeed. But in decimal representation that means -2 since the vast majority of real-world computers use two's complement.

When converted to unsigned long it does become 4294967294 however, because that's how signed to unsigned conversion works.

I got -2 as result.

Upon return you convert back to signed again. This conversion is implementation-defined but likely you'll end up with -2 again on all mainstream system. Similarly, if you would attempt to print an unsigned long using printf("%ld", my_unsigned_long) then it will likely display the signed decimal representation of what's stored inside the unsigned long.

So then I just used XOR operation and it worked

In case of a 32 bit system, then one operand of n ^ 4294967295, namely the 4294967295 constant, is of type long long - because it can't fit in any smaller type. When the compiler tries to determine what type it will use for 4294967295, it will ask itself: Does it fit inside an int? No. Does it fit inside a long? No. Does it fit inside a long long? Yes.

Therefore 1 ^ 4294967295 gives 4294967294 as expected, since the calculation is carried out on type long long and nothing affects the sign bit.

CodePudding user response：

On some platforms, sizeof long == sizeof int.

The standard defines the maximum value for an object of a long int to be LONG_MAX, where LONG_MAX must be at least 2,147,483,647.

Thus, 4,294,967,294 can't be represented by a long.

Fix:

• Always do bitwise operations on unsigned types.
• Change the return type of the function from long to unsigned.
• Use types like int32_t and int64_t defined in stdint.h header file, which are guaranteed to have 32 and 64 bits respectively.

CodePudding user response：

Before using bitwise operators, you must consider several things :

1. Some combinations of padding bits might generate trap representations. N1256 footnote
2. Two's complement is not the only way to encode a integer. N1256 6.2.6.2

To satisfy above requirments, we use uintN_t instead of long. intN_t doesn't have padding bits. And uintN_t is two's complement representation. N stands for width. For example, int8_t denotes a signed integer type with a width of exactly 8 bits. The only problem is uintN_t is optional. N1256 7.18.1.1

Why ~ operation of 1 not represented as 4294967294 but -2 in C? What do I need to do to make ~ operator return 4294967294 and not -2 (if it's possible)?

4294967294 is equal to UINT32_MAX - 1. So we choose uint32_t.

uint32_t flippingBits(uint32_t n)
{
    return ~n;
}