> For the complete documentation index, see [llms.txt](https://lochiwei.gitbook.io/web/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lochiwei.gitbook.io/web/js/grammar/op/arithmetic/bitwise/2s-complement.md).

# 2's complement

-x = \~x + 1 (invert bits, then add 1).

[JS](/web/js.md) ⟩ [statement](/web/js/grammar/statement.md) ⟩ [expression](/web/js/grammar/statement/expr.md) ⟩ [operator](/web/js/grammar/op.md) ⟩ [arithmetic](/web/js/grammar/op/arithmetic.md) ⟩ [bitwise](/web/js/grammar/op/arithmetic/bitwise.md) ⟩ 2's complement

{% hint style="success" %}
(<mark style="color:yellow;">**inverts**</mark> the <mark style="color:yellow;">**bits**</mark>, then <mark style="color:yellow;">**add**</mark>**&#x20;**<mark style="color:red;">**1**</mark>)&#x20;

in <mark style="color:red;">**signed**</mark>**&#x20;**<mark style="color:yellow;">**integer addition**</mark>, <mark style="color:purple;">**`-x`**</mark> (the <mark style="color:yellow;">**2**</mark><mark style="color:purple;">**'s complement**</mark> of <mark style="color:blue;">**`x`**</mark>) is <mark style="color:yellow;">**defined**</mark> to be <mark style="color:yellow;">**`~x + 1`**</mark>.

```javascript
// (for simplicity, 8-bit signed integer)
//
// ┌─ (⭐️ sign bit: 0 nonnegative, 1 negative)
   0110 1010    //  x
+  1001 0101    // ~x (⭐️ invert the bits)
------------
   1111 1111    // x + (~x) = 1111 1111 = M - 1, where M = 2⁸
+          1    // +1 (⭐️ add 1)
------------    // 
  10000 0000    // x + (~x + 1) ≡ 0 (mod M)
                //     ╰─ -x ─╯ <---- 🔸 define -x = ~x + 1
                //
                // 🔸 Definition: -x = ~x + 1 (2's complement)
                // ⭐️ this is why ~x = -x - 1 
```

{% endhint %}

<details>

<summary><span data-gb-custom-inline data-tag="emoji" data-code="1f4a1">💡</span> proof:  ~(x ± M)  ≡  ~x  ,  ~~(x ± M)  ≡  ~~x (mod M)</summary>

```javascript
// 1. ~(x ± M)  ≡  ~x
// proof:
~(x ± M) = -(x ± M) - 1        // definition
         = -x ± M -1
         ≡ -x - 1 (mod M)      // modular arithmetic
         = ~x                  // definition
// 2. ~~(x ± M)  ≡  ~~x
// proof:
~~(x ± M) = ~(~(x ± M))        // `~` is right-to-left associative
          ≡ ~(~x)              // by proof 1.
          = ~~x                // `~` is right-to-left associative
```

</details>

{% tabs %}
{% tab title="🗺️ 圖表" %}
{% hint style="success" %}
:star: <mark style="color:red;">**signed**</mark>**&#x20;**<mark style="color:yellow;">**integer addition**</mark> is a [**modular arithmetic**](https://en.wikipedia.org/wiki/Modular_arithmetic).
{% endhint %}

<img src="https://2527454625-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MfvEFZnSBhKT6fJmus0%2Fuploads%2F9v8b29tGe0A1ATmxplwZ%2Ftwo.complement.svg?alt=media&amp;token=a6bec8df-5117-49cb-83f9-aa3eea639809" alt="signed integer additon is a modular arithmetic" class="gitbook-drawing">

<img src="https://2527454625-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MfvEFZnSBhKT6fJmus0%2Fuploads%2FpNZA5LCUfTRKIJA7C0vI%2Foverflow.underflow.svg?alt=media&amp;token=b400a35c-e4d9-4ce8-bf26-cb8fe9034cfa" alt="integer addition may overflow/underflow." class="gitbook-drawing">
{% endtab %}

{% tab title="🧨 雷區" %}
{% hint style="danger" %}
[num.toString(2)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/toString) <mark style="color:red;">**doesn't**</mark>**&#x20;**<mark style="color:yellow;">**show**</mark> <mark style="color:yellow;">**2**</mark><mark style="color:purple;">**'s complement**</mark> for <mark style="color:red;">**negative**</mark>**&#x20;**<mark style="color:yellow;">**integers**</mark>:exclamation:

```javascript
(-12).toString(2),                    // -1100    (what the ❗)
(~~(-12)).toString(2),                // -1100    (what the ❗)
```

{% endhint %}
{% endtab %}

{% tab title="⭐️ 重點" %}
{% hint style="success" %}
for <mark style="color:blue;">**n**</mark><mark style="color:yellow;">**-bit**</mark> <mark style="color:red;">**signed**</mark>**&#x20;**<mark style="color:yellow;">**integers**</mark>,&#x20;

* <mark style="color:purple;">**`-x`**</mark> = <mark style="color:yellow;">**`~x + 1`**</mark>.
* <mark style="color:yellow;">**`~x`**</mark> = <mark style="color:purple;">**`-x`**</mark><mark style="color:yellow;">**`- 1`**</mark>.
* <mark style="color:yellow;">**`~(x`**</mark>± M<mark style="color:yellow;">**`)`**</mark> ≡ <mark style="color:yellow;">**`~x`**</mark> (mod M), where $$M = 2ⁿ$$
* <mark style="color:yellow;">**`~~(x`**</mark>± M<mark style="color:yellow;">**`)`**</mark> ≡ <mark style="color:yellow;">**`~~x`**</mark> (mod M)
* $$-M \le x + y \<M$$ , where $$-\frac{M}{2} \le x, y < \frac{M}{2}$$ (<mark style="color:yellow;">**may**</mark> <mark style="color:red;">**overflow**</mark>/<mark style="color:red;">**underflow**</mark>)
  {% endhint %}
  {% endtab %}

{% tab title="👥 相關" %}

* [bitwise not (\~)](/web/js/grammar/op/arithmetic/bitwise/not.md) - inverts the bits.
* [double tilde (\~\~)](/web/js/grammar/op/arithmetic/bitwise/not/double-tilde.md) - nearest integer towards 0.
  {% endtab %}

{% tab title="💈範例" %}

* replit： [bitwise not (\~)](https://replit.com/@pegasusroe/bitwise-not-v2#index.js)

```javascript
// ⭐ test ~x
const M = 2 ** 32;        // 4294967296
const m = M/8;            //  536870912

// ⭐ overflow: 3m + 2m ≡ -3m (mod M)
~~(5*m),        // -1610612736    (overflow)❗
-3*m,           // -1610612736

// ⭐ underflow: -5m ≡ 3m (mod M)
~~(-5*m),       //  1610612736    (underflow)❗
3*m,            //  1610612736
-5*m,           // -2684354560

// ⭐ ~(x ± M) = ~x
~1234,          // -1235
~(1234 - M),    // -1235
~(1234 + M),    // -1235

'----------',

// ⭐ `~x` === -x - 1 (truncate decimal if needed)
~(3),       // -4     (-3 - 1)
~(-5),      //  4     ( 5 - 1)

~(3.4),     // -4     ( 3.4 ->  3 -> -3 - 1 = -4)
~(-5.5),    //  4     (-5.5 -> -5 ->  5 - 1 =  4)

// ⭐ `~~x`: 
~~(7.8),    //  7     (⭐ nearest integer towards 0)
~~(-3.4),   // -3
~~(6),      //  6     (⭐ `~~x = x`, if x integer)
```

{% endtab %}

{% tab title="📗 參考" %}

* [ ] [JavaScript: The Definitive Guide](/web/master/ref/javascript-the-definitive-guide.md) ⟩ 4.8.3 Bitwise Operators
* [ ] Cornell ⟩ [Two's Complement](https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html)
* [ ] Wikipedia ⟩ [modulo operation](https://en.wikipedia.org/wiki/Modulo_operation), [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic)
  {% endtab %}

{% tab title="📘 手冊" %}

* [Bitwise NOT (\~)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_NOT) - invert the bits.
* [Number.prototype.toString()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/toString) - specify the radix.
  {% endtab %}
  {% endtabs %}