How does this line of code negate a std::uint64

I'm trying to understand what this code does. This is supposed to negate the coefficient coeff of type uint64_t* of a polynomial with coefficients modulus modulus_value of type const uint64_t:

std::int64_t non_zero = (*coeff != 0);
*coeff = (modulus_value - *coeff) & static_cast<std::uint64_t>(-non_zero);

What's up with the & static_cast<std::uint64_t>(-non_zero)? How does this negate anything?

The code is from here.

CodePudding user response：

This code is a branchless version of

if (*coeff) *coeff = (modulus_value - *coeff);
// else *coeff = *coeff;

The negation is (modulus_value - *coeff).

The & static_cast<std::uint64_t>(-non_zero) implements the condition without a branch, and is totally unrelated to negation.

FWIW you're probably better off with the easy-to-understand if statement version. Architectures with a "conditional MOV" will use it instead of a branch, and compilers for other architectures will almost invariably know how to optimize a conditional assignment to the branchless version.

Two other equivalent versions are:

*coeff = (*coeff) ? (modulus_value - *coeff) : (*coeff);

and

*coeff = (*coeff) ? (modulus_value - *coeff) : 0;

all of which are easier to understand for both humans and compilers than the version in the question.

CodePudding user response：

non_zero will be either 1 or 0.

-non_zero will turn that into -1 or 0.

static_cast<std::uint64_t>(-non_zero) will tell the compiler to treat the signed number as unsigned, which will turn 0 into 0, and -1 into 0xffffffffffffffff.

Then the bitwise AND will either clear all bits of (modulus_value - *coeff) (if non_zero is 0) or keep all the bits of (modulus_value - *coeff) as they are (i.e. it's a no-op really).

So the result assigned back to *coeff will be either 0 or modulus_value - *coeff.

It's equivalent to (modulus_value - *coeff) * non_zero. Or in shorter form (modulus_value - *coeff) * !!*coeff.