i + =(i& -i)会做什么?它是便携式的吗? [英] What does i+=(i&-i) do? Is it portable?

问题描述

让i为有符号整数类型.考虑

i += (i&-i);
i -= (i&-i);

最初是i>0.

1. 这些是做什么的?是否只有使用算术的等效代码?
2. 这是否取决于负整数的特定位表示形式?

来源:在线编码难题的二传手代码(无任何解释/评论).

解决方案

如果i具有无符号类型，则表达式是完全可移植的且定义明确.

如果i具有带符号的类型，则它不是可移植的，因为&是根据表示形式定义的，而一元-，+=和-=是根据值定义的.但是，如果下一版本的C ++标准要求二进制补码，它将变得可移植，并且与未签名的情况一样.

在无符号情况(和二进制补码情况)下，很容易确认i&-i是2的幂(只有一位非零)，并且具有与(也是-i的最低位).因此:

• i -= i&-i;清除i的最低设置位.
• i += i&-i;递增(清零，但有更高的进位位)i的最低置位位.

对于无符号类型，任何一个表达式都不会溢出.对于有符号类型，当i最初具有该类型的最小值时，i -= i&-i溢出而使用-i，而当i最初具有该类型的最大值时，i += i&-i在+=中溢出. >

Let i be a signed integer type. Consider

i += (i&-i);
i -= (i&-i);

where initially i>0.

1. What do these do? Is there an equivalent code using arithmetic only?
2. Is this dependent on a specific bit representation of negative integers?

Source: setter's code of an online coding puzzle (w/o any explanation/comments).

解决方案

If i has unsigned type, the expressions are completely portable and well-defined.

If i has signed type, it's not portable, since & is defined in terms of representations but unary -, +=, and -= are defined in terms of values. If the next version of the C++ standard mandates twos complement, though, it will become portable, and will do the same thing as in the unsigned case.

In the unsigned case (and the twos complement case), it's easy to confirm that i&-i is a power of two (has only one bit nonzero), and has the same value as the lowest-place bit of i (which is also the lowest-place bit of -i). Therefore:

• i -= i&-i; clears the lowest-set bit of i.
• i += i&-i; increments (clearing, but with carry to higher bits) the lowest-set bit of i.

For unsigned types there is never overflow for either expression. For signed types, i -= i&-i overflows taking -i when i initially has the minimum value of the type, and i += i&-i overflows in the += when i initially has the max value of the type.

这篇关于i + =(i& -i)会做什么?它是便携式的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！