how to take twos complement of a byte in c++

Question

I am looking at some c++ code and I see:

 byte b = someByteValue;
 // take twos complement
 byte TwosComplement = -b;

Is this code taking the twos complement of b? If not, What is it doing?

Solution 1

This code definitely does compute the twos-complement of an 8-bit binary number, on any implementation where stdint.h defines uint8_t:

#include <stdint.h>
uint8_t twos_complement(uint8_t val)
{
    return -(unsigned int)val;
}

That is because, if uint8_t is available, it must be an unsigned type that is exactly 8 bits wide. The conversion to unsigned int is necessary because uint8_t is definitely narrower than int. Without the conversion, the value will be promoted to int before it is negated, so, if you're on a non-twos-complement machine, it will not take the twos-complement.

More generally, this code computes the twos-complement of a value with any unsigned type (using C++ constructs for illustration - the behavior of unary minus is the same in both languages, assuming no user-defined overloads):

#include <cstdint>
#include <type_traits>

template <typename T>
T twos_complement(T val,
                  // "allow this template to be instantiated only for unsigned types"
                  typename std::enable_if<std::is_unsigned<T>::value>::type* = 0)
{
    return -std::uintmax_t(val);
}

because unary minus is defined to take the twos-complement when applied to unsigned types. We still need a cast to an unsigned type that is no narrower than int, but now we need it to be at least as wide as any possible T, hence uintmax_t.

However, unary minus does not necessarily compute the twos-complement of a value whose type is signed, because C (and C++) still explicitly allow implementations based on CPUs that don't use twos-complement for signed quantities. As far as I know, no such CPU has been manufactured in at least 20 years, so the continued provision for them is kind of silly, but there it is. If you want to compute the twos-complement of a value even if its type happens to be signed, you have to do this: (C++ again)

#include <type_traits>

template <typename T>
T twos_complement(T val)
{
    typedef std::make_unsigned<T>::type U;

    return T(-uintmax_t(U(val)));
}

i.e. convert to the corresponding unsigned type, then to uintmax_t, then apply unary minus, then back-convert to the possibly-signed type. (The cast to U is required to make sure the value is zero- rather than sign-extended from its natural width.)

(If you find yourself doing this, though, stop and change the types in question to unsigned instead. Your future self will thank you.)

Solution 2

The correct expression will look

byte TwosComplement = ~b + 1;

Note: provided that byte is defined as unsigned char

Solution 3

On a two's complement machine negation computes the two's complement, yes.

On the Unisys something-something, hopefully now dead and buried (but was still extant a few years ago), no for a signed type.

C and C++ supports two's complement, one's complement and sign-and-magnitude representation of signed integers, and only with two's complement does negation do a two's complement.

---

With byte as an unsigned type negation plus conversion to byte produces the two's complement bitpattern, regardless of integer representation, because conversion to unsigned as well as unsigned arithmetic is modulo 2ⁿ where n is the number of value representation bits.

That is, the resulting value after assigning or initializing with -x is 2ⁿ - x which is the two's complement of x.

This does not mean that the negation itself necessarily computes the two's complement bitpattern. To understand this, note that with byte defined as unsigned char, and with sizeof(int) > 1, the byte value is promoted to int before the negation, i.e. the negation operation is done with a signed type. But converting the resulting negative value to unsigned byte, creates the two's complement bitpattern by definition and the C++ guarantee of modulo arithmetic and conversion to unsigned type.

---

The usefulness of 2's complement form follows from 2ⁿ - x = 1 + ((2ⁿ - 1) - x), where the last parenthesis is an all-ones bitpattern minus x, i.e. a simple bitwise inversion of x.

Comments

[zwol]

I think you have confused - with ~. And either way it could still do something unexpected depending on the ABI and what byte is.

[Vlad from Moscow]

@Zack As far as I know byte is always defined as unsigned character.

[zwol]

byte is not a standard-defined fundamental type nor typedef-name, so we have no way of knowing what it's defined as. It seriously would not surprise me at all to discover an application that did typedef int byte; in its headers.

[amalgamate]

While this is relevant, it does not address whether the code is correct.

[Cheers and hth. - Alf]

Sorry for many edits, due to non-cooperative network and small screen. :(

[Cheers and hth. - Alf]

@Zack: the c++ standard defines the size of "byte" as 1. so a reasonable definition is limited to either char, unsigned char or signed char. of course the definition might be unreasonable.

[zwol]

@Cheersandhth.-Alf My whole point here is that given the information provided to date, we simply do not know whether the definition of "byte" in the OP's code is "reasonable". (We now know it's unsigned, but we still don't know how wide it is.)

[FlashMcQueen]

Why is it necessary to cast to uintmax_t instead of just doing static_cast<T>(-static_cast<U>(val))?

[zwol]

@FlashMcQueen If T (and therefore also U) is narrower than int, and you don't have the cast to uintmax_t in there, the "integer promotions" will convert the value to int before doing the negation, ruining the effect of casting to an unsigned type.

[FlashMcQueen]

of course but "If the destination type is signed, the value does not change if the source integer can be represented in the destination type." and in this case the value of -uintmax_t(U(val)) can always be represented in T, can't be?

[zwol]

@FlashMcQueen That's not the issue. The issue is that if U is narrower than int, T(-U(val)) becomes T(-int(val)) after integer promotion, and thus performs the negation on a signed quantity, and therefore might not take the twos-complement.