When I do bitwise flip operation in C on integer 1, I get -2 and not 4294967294, how can I get 4294967294?

huangapple go评论68阅读模式
英文:

When I do bitwise flip operation in C on integer 1, I get -2 and not 4294967294, how can I get 4294967294?

问题

这是一个新手级别的HackerRank问题,要求翻转由32位表示的长整数的位,并返回结果。

例如:

1 被表示为:00000000 00000000 00000000 00000001

~ 运算符翻转位。

所以 ~1 = 11111111 11111111 11111111 11111110

当我在长整数上执行 ~1 时,它返回的是 -2,而不是 4294967294,尽管它们在32位二进制形式中表示相同。

我实现了以下代码:

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

我得到了 -2 作为结果。我尝试了只使用 "long",但得到了相同的结果。我还尝试了使用强制类型转换 unsigned long x = (unsigned long)~n;,但结果仍然相同。

所以后来我只是使用了异或操作,它起作用了:

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

为什么在C中 ~ 操作符对于 1 不会表示为 4294967294 而是 -2 呢?如果可能的话,我需要做什么来让 ~ 运算符返回 4294967294 而不是 -2?

英文:

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)?

答案1

得分: 1

在一些平台上,sizeof long == sizeof int

标准定义了long int对象的最大值为LONG_MAX,其中LONG_MAX必须至少为2,147,483,647

因此,4,294,967,294不能由long表示。

修复:

  • 始终对unsigned类型执行位操作。
  • 将函数的返回类型从long更改为unsigned
  • 使用stdint.h头文件中定义的int32_tint64_t等类型,这些类型分别保证具有32位和64位。
英文:

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.

答案2

得分: 1

~ 应用于一个类型为有符号 long 的操作数 n。假设长整型为32位,那么它的二进制表示将变为 11111111 11111111 11111111 11111110。但在十进制表示中,这意味着 -2,因为绝大多数实际计算机使用的是 二进制补码

当转换为 unsigned long 时,它确实变为 4294967294,因为这是有符号到无符号的转换方式。

> 我得到了 -2 作为结果。

返回时,你再次将其转换为有符号数。这种转换是与实现相关的,但在所有主流系统上,你很可能会再次得到 -2。类似地,如果你尝试使用 printf(""%ld"", my_unsigned_long) 打印一个 unsigned long,那么它很可能会显示存储在 unsigned long 中的带符号十进制表示。

> 所以我只是使用了异或操作,它起作用了

在32位系统的情况下,n ^ 4294967295 的操作数之一,即常数 4294967295,是类型为 long long 的,因为它不能适应任何较小的类型。当编译器尝试确定要用于 4294967295 的类型时,它会自问:它能适应一个 int 吗?不能。它能适应一个 long 吗?不能。它能适应一个 long long 吗?能。

因此,1 ^ 4294967295 得到了预期的 4294967294,因为计算是在类型 long long 上进行的,没有任何影响到符号位。

英文:

~ 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.

答案3

得分: 0

在使用位运算符之前,您必须考虑以下几个方面:

  1. 一些填充位的组合可能会生成陷阱表示。N1256脚注
  2. 二进制补码不是唯一编码整数的方式。N1256 6.2.6.2

为了满足上述要求,我们使用uintN_t而不是longintN_t没有填充位,而uintN_t是二进制补码表示法。这里的N表示宽度。例如,int8_t表示具有精确宽度为8位的有符号整数类型。唯一的问题是uintN_t是可选的。N1256 7.18.1.1

> 为什么C中的1的~操作不表示为4294967294而表示为-2?如果可能的话,我需要做什么才能使~运算符返回4294967294而不是-2?

4294967294等于UINT32_MAX - 1。因此,我们选择了uint32_t

uint32_t flippingBits(uint32_t n)
{
    return ~n;
}
英文:

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;
}

huangapple
  • 本文由 发表于 2023年1月9日 18:51:05
  • 转载请务必保留本文链接:https://go.coder-hub.com/75056199.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定