🌟2's complement

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

JS ⟩ statement ⟩ expression ⟩ operator ⟩ arithmetic ⟩ bitwise ⟩ 2's complement

(inverts the bits, then add 1)

in signed integer addition, -x (the 2's complement of x) is defined to be ~x + 1.

// (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 

💡 proof: ~(x ± M) ≡ ~x , ~~(x ± M) ≡ ~~x (mod M)

// 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

🗺️ 圖表

⭐ signed integer addition is a modular arithmetic.

signed integer additon is a modular arithmetic

integer addition may overflow/underflow.

🧨 雷區

num.toString(2) doesn't show 2's complement for negative integers❗

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

⭐️ 重點

for n-bit signed integers,

• -x = ~x + 1.

• ~x = -x- 1.

• ~(x± M) ≡ ~x (mod M), where $M = 2ⁿ$

• ~~(x± M) ≡ ~~x (mod M)

• $-M \le x + y <M$ , where $-\frac{M}{2} \le x, y < \frac{M}{2}$ (may overflow/underflow)

👥 相關

• bitwise not (~) - inverts the bits.

• double tilde (~~) - nearest integer towards 0.

💈範例

• replit： bitwise not (~)

// ⭐ 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)

📗 參考

• JavaScript: The Definitive Guide ⟩ 4.8.3 Bitwise Operators

• Cornell ⟩ Two's Complement

• Wikipedia ⟩ modulo operation, modular arithmetic

📘 手冊

• Bitwise NOT (~) - invert the bits.

• Number.prototype.toString() - specify the radix.