# 2's complement

[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="/files/d75EIWVhbcN19aHFLwaA" alt="signed integer additon is a modular arithmetic" class="gitbook-drawing">

<img src="/files/UGfHFO3iObumfmVpH1j9" 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 %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lochiwei.gitbook.io/web/js/grammar/op/arithmetic/bitwise/2s-complement.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.