Two's complement semantics for bitwise operators?

[littledan]

Are two's complement semantics for bitwise operations the best ones? Are they very efficiently implementable? cc @jaro-sevcik

[jaro-sevcik]

I believe two's complement is the intuitive semantics for bitwise ops. This is what Java, Python and GMP specify (https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html, https://wiki.python.org/moin/BitwiseOperators, https://gmplib.org/manual/Integer-Logic-and-Bit-Fiddling.html).

Efficiency depends on what the underlying representation is. If it is two's complement (Java BigInteger), it is super-fast. If it is sign-magnitude (Python, GMP), then one needs to convert to two's complement, do the bitwise op and convert back (e.g., see Python's implementation here: https://github.com/python/cpython/blob/master/Objects/longobject.c#L4406). Even that should be cheap-ish.

[jaro-sevcik]

Note: I think that for small integers, Python's representation is also two's complement, so bitwise ops on those are very fast. (For long integers, the cost of complements should not matter much because the allocation and loads/stores will dominate.)

[littledan]

OK, the specification is clear that we do have this infinite two's complement semantics. Anyone, if you discover more information here, let's reopen this bug and discuss it. Closing for now.

[chharvey]

Should this line in the spec be updated? It says “one’s complement”.

proposal-bigint/spec.html

Lines 266 to 269 in f26c2c7

	<emu-clause id="sec-numeric-types-bigint-bitwiseNOT">
	<h1>BigInt::bitwiseNOT (_x_)</h1>
	<p>The abstract operation BigInt::bitwiseNOT with an argument _x_ of BigInt type returns the one's complement of _x_; that is, -_x_ - 1.</p>
	</emu-clause>

[jakobkummerow]

@chharvey I believe the statement is correct. bitwise-not == ones' complement; unary-minus == two's complement.

(According to Wikipedia, the correct spelling is "ones' complement", not "one's complement", so that's a nit that could be fixed.)

[chharvey]

@jakobkummerow But doesn’t the bitwise-not operator use two’s complement? e.g.:

~6
~0b0110
0b1001

I thought 0b1001 (signed) is -7 in two’s and -6 in ones’. Since ~6 === -7, wouldn’t that be two’s?

[jakobkummerow]

What the bitwise-not operator (conceptually) does is to invert every bit, and "inverting every bit" is how "ones' complement" is defined. (What it actually does in all implementations I know of is to compute -x-1; that ends up being the same because this spec does force implementations to pretend to be using two's complement representations for negative BigInts.)

Sure, if you have 0b111...111001 and you read that back as -7 then you've interpreted it as a two's complement representation. But that's unrelated to what ~ does.

Saying that "the ones' complement value of 6 is -7" would be illogical -- the accurate statement is "the ones' complement value of 6 is the same bit pattern as the two's complement value of 7". The ~ operator gives you the ones' complement, the (unary) - operator gives you the two's complement, hence ~6 === -7. If you had a system that used ones' complement to store negative numbers, then ~6 would be "minus six" in that system (such a system should probably define the unary-minus operator to also perform ones' complement).

It's a bit confusing :-)

[chharvey]

It goes way over my head! Thanks for the explanation. 😃