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

user_9415489 0
Viewed 164

I've recently encountered a piece of code that supposedly works fine, but I don't quite understand why.

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

This piece of code will invert the least significant bit of a given unsigned integer. I would prefer to just write a ^= 1;, but I'm puzzled by why the piece of code above actually works. I would think that making an unsigned int negative will result in undefined behavior?

bit bit-manipulation c++
2 Answers

a & -a gives you the least significant 1-bit set in a. For an odd number it is indeed 1, but that's not the case in general of course.

Making an unsigned negative is a well-defined and occasionally useful notation: -a for positive a is -a + 2N where N is the number of bits in the type. An alternative to writing size_t a = std::numeric_limits<size_t>::max(); is to write size_t a = -1; for example.

So a ^= a & -a; flips the least significant 1-bit to 0.

Rather clever really.

user_23808300

As @Bathsheba has already pointed out, this trick gives you the least significant 1-bit set in a. However I would like to go into more detail why this happens. C++ unsigned integer negation is equivalent to two's complement negation:

Unary arithmetic operators

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

(see cppreference/Arithmetic operators)

For two's complement numbers, a negation can be done as follows:

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

If it wasn't for the increment, then ~a would have no bits in common with a and the result would be zero. This is the case for one's complement numbers. However, due to the increment, the last significant set 1-bit in a also becomes set. For example:

 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 then flips the least significant 1-bit to 0. What this mathematically does is:

  • round up to the next multiple of a power of two
  • turn any power of 2 into 0
  • 0 stays the same

Also note that as of C++20, signed numbers must be represented using two's complement. For example, this means that signed integer overflow is no longer undefined behavior.

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 -(2N-1-1) to +2N-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 -2N-1 to +2N-1 -1 (e.g. -128 to 127 for a signed 8-bit type).

(See cppreference/Fundamental types)

user_57404280
Related