2
$\begingroup$

I have a question about the binary of negative integer number in Mathematica.

In most implementations, negative signed integers are stored in what is called two's complement. The other major way of storing negative signed numbers is called one's complement.

The two's complement of an N-bit number x is defined as 2^N - x. For example, the two's complement of 8-bit 1 is 2^8 - 1, or 1111 1111. The two's complement of 8-bit 8 is 2^8 - 8, which in binary is 1111 1000. This can also be calculated by flipping the bits of x and adding one. For example:

 1 = 0000 0001
~1 = 1111 1110
-1 = ~1 + 1 = 1111 1111

 21 = 0001 0101
~21 = 1110 1010
-21 = 1110 1011

 128 = 1000 0000
~128 = 0111 1111
-128 = 1000 0000

They can also be calculated as:

-1   = 2^8 - 1   = 255 = 1111 1111
-21  = 2^8 - 21  = 234 = 1110 1010
-128 = 2^8 - 128 = 128 = 1000 0000

These results are exactly identical to the results calculated in C language. However, when using Mathematica (I use Mathematica 11.1.0), the results are quite different:

BaseForm[-1, 2]   = -1
BaseForm[-21, 2]  = -10101
BaseForm[-128, 2] = -1000 0000

My question is: How to get the right results using Mathematica? Am I use the WRONG command?

Thanks a lot!

$\endgroup$
3
  • $\begingroup$ Mathematica assumes an infinite two's complement, since there is otherwise no notion of finite bits; see e.g. the docs for BitNot[]. You can use Mod[] if you wish to simulate a finite amount of bits that spill over. $\endgroup$ Oct 2, 2017 at 23:33
  • $\begingroup$ Another note: when you post the same question on another place like Community, it is common courtesy to include a link to the other post, so that you don't waste other folks' time. $\endgroup$ Oct 3, 2017 at 0:04
  • $\begingroup$ @J.M. Thank you for your explanation and nice reminder. I read the document and found there is no implementation of finite two's complement. I have to write it by myself. This is my code: $\endgroup$
    – zchenkui
    Oct 8, 2017 at 1:49

1 Answer 1

1
$\begingroup$

I am not expert and I am mostly posting this for future me but here is how I implement 2's complement in Mathematica

twosComplement[x_, n_] := 
 UnitBox@IntegerDigits[x, 2, n] // FromDigits[#, 2] & // 
    Plus[#, 1] & // IntegerDigits[#, 2] & // PadLeft[#, n] &

I've seen other places on this site that claim to show 2's complement (can't seem to find them now) but they are actually calculating 1's complement. Or if they calculate using the definition correctly, the MSB bits are not 1's like they should be. This accounts for that. Also retains the array length when the complement has only 0's in its prefix.

$\endgroup$
10
  • $\begingroup$ Why not simply tc[n_Integer, bits_Integer] := BaseForm[Mod[n, 2^bits], 2]? $\endgroup$
    – John Doty
    Dec 21, 2020 at 17:26
  • $\begingroup$ twos complement of an $n$-bit binary number $N$ is defined by $2^n-N$ for $N \neq 0$ and as $0$ for $N=0$. $\endgroup$
    – skyfire
    Dec 21, 2020 at 17:56
  • $\begingroup$ guess I should add that $1$'s complement is $(2^n -1)-N$ and so the Plus[#,1]& in the formula is because 2's complement is achieved from 1's complement through $((2^n -1) - N)+1$ $\endgroup$
    – skyfire
    Dec 21, 2020 at 18:25
  • $\begingroup$ tc[n,bits] gives you the twos complement representation of n for word size bits. Apparently you want the twos complement representation of -n, so just use tc[-n,bits]. $\endgroup$
    – John Doty
    Dec 21, 2020 at 19:45
  • 1
    $\begingroup$ The definition is the one that the OP apparently wanted, where BaseForm[_,2] of a negative number would result in the twos complement representation of the number. You're confusing the process of twos complement negation with the representation of a number in twos complement, so you have positive numbers in making negative numbers out. $\endgroup$
    – John Doty
    Dec 21, 2020 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.