通过使用 size_t 的否定翻转最低有效一位

Question

我最近遇到一段代码，据说可以正常工作，但我不太明白为什么。

size_t a = 19;
std::cout<<std::bitset<8>(a)<<std::endl;
a ^= a & -a;
std::cout<<std::bitset<8>(a)<<std::endl;

这段代码将反转给定无符号整数的最低有效位。我宁愿只写 a ^= 1;，但我对上面这段代码为什么能正常工作感到困惑。我认为 unsigned int 否定会导致未定义的行为？

Answer 1

a & -a 为您提供 a 中设置的最低有效 1 位。对于奇数确实是1，但一般情况下当然不是这样。

制作一个 unsigned 负数是 well-defined 并且偶尔有用的符号：-a 正数 a 是 -a + 2^N 其中 N 是类型中的位数。例如，写 size_t a = std::numeric_limits<size_t>::max(); 的另一种方法是写 size_t a = -1;。

因此 a ^= a & -a; 将最低有效 1 位翻转为 0。

真的很聪明。

Answer 2

正如@Bathsheba 已经指出的那样，这个技巧为您提供了 a 中最低有效的 1 位集。但是，我想更详细地说明为什么会发生这种情况。 C++无符号整数取反等价于补码取反：

Unary arithmetic operators

[...]
The builtin unary minus operator calculates the negative of its promoted operand. For unsigned a, the value of -a is 2^b -a, where b is the number of bits after promotion.

（参见 cppreference/Arithmetic operators）

对于二进制补码，可以按如下方式取反：

unsigned a = ...;
a = ~a;
a += 1;

如果不是增量，那么 ~a 将没有与 a 相同的位，结果将为零。一个人的补数就是这种情况。但是，由于递增，a 中的最后一个有效设置 1 位也被设置。例如：

 16      = 0b0001'0000
~16      = 0b1110'1111 = -17
~16 + 1  = 0b1111'0000 = -16
-16 & 16 = 0b0001'0000 =  16

 10      = 0b0000'1010
~10      = 0b1111'0101 = -11
~10 + 1  = 0b1111'0110 = -10
-10 & 10 = 0b0000'0010 =   2

a ^= a & -a 然后将最低有效 1 位翻转为 0。这在数学上的作用是：

四舍五入到下一个二的幂的倍数
将 2 的任意次方变成 0
0 保持不变

另请注意，自 C++20 起，有符号数必须使用二进制补码表示。例如，这意味着有符号整数溢出不再是未定义的行为。

Range of values

[...]

Prior to C++20, the C++ Standard allowed any signed integer representation, and the minimum guaranteed range of N-bit signed integers was from -(2^N-1-1) to +2^N-1-1 (e.g. -127 to 127 for a signed 8-bit type), which corresponds to the limits of one's complement or sign-and-magnitude.

However, all C++ compilers use two's complement representation, and as of C++20, it is the only representation allowed by the standard, with the guaranteed range from -2^N-1 to +2^N-1 -1 (e.g. -128 to 127 for a signed 8-bit type).

（见cppreference/Fundamental types）

通过使用 size_t 的否定翻转最低有效一位

Flip least significant one-bit by using negation of a size_t

c++

bit-manipulation

bit

Unary arithmetic operators

Range of values