Signed Integer ও Two's Complement — ঋণাত্মক সংখ্যার তিনটা ইতিহাস

Two’s complement = arithmetic mod 2ⁿ — সম্পূর্ণ প্রমাণ

Level 0-এর number-systems লেসনে (mathematics/number-systems, “Two’s complement = arithmetic mod 2ⁿ” অংশ) আমরা এই দাবিটা করেছিলাম, প্রাথমিক আকারে। এখানে আমরা সেটা সম্পূর্ণভাবে derive করব — bit থেকে শুরু করে।

দাবি: ~x = (2ⁿ − 1) − x

x-এর প্রতিটা bit dᵢ উল্টে দিলে (1 − dᵢ) পাওয়া যায় (0 ↔ 1)। তাই ~x-এর মান:

$\sim x = \sum_{i=0}^{n-1} (1-d_i) \cdot 2^i = \sum_{i=0}^{n-1} 2^i \;-\; \sum_{i=0}^{n-1} d_i \cdot 2^i = (2^n - 1) - x$

প্রথম যোগফল \sum 2^i (i=0 থেকে n-1) একটা geometric series, যার যোগফল ঠিক 2ⁿ − 1 (Level 0-এর কম্বিনেটরিক্স লেসনের সূত্র)। দ্বিতীয় যোগফল সংজ্ঞা অনুযায়ী x নিজেই (unsigned interpretation-এ)। $\quad\blacksquare$

দাবি: two’s complement negation = ~x + 1 = 2ⁿ − x

উপরের ফলাফলে 1 যোগ করুন:

$\sim x + 1 = \big[(2^n - 1) - x\big] + 1 = 2^n - x$

$\quad\blacksquare$ — এটাই এই লেসনের কেন্দ্রীয় সমীকরণ।

এটাই ℤ_(2ⁿ)-এর additive inverse

2ⁿ − x চেনা লাগছে? এটা ঠিক Level 0-এর number-systems লেসনে শেখা concept — x-এর additive inverse mod 2ⁿ। কারণ:

$x + (2^n - x) = 2^n \equiv 0 \pmod{2^n}$

অর্থাৎ two’s complement negation আক্ষরিকভাবে সেই একই ℤ_(2ⁿ)-এ x-এর সাথে যোগ করলে 0 দেয় এমন উপাদান খোঁজা — ঠিক যেমন সাধারণ পাটিগণিতে -x-এর সংজ্ঞা x + (-x) = 0। কোনো নতুন গণিত লাগেনি — শুধু “0 থেকে 2ⁿ−1” জগতে “additive inverse”-এর অর্থ কী, সেটা প্রয়োগ করা হয়েছে।

যাচাই — 4-bit-এ x = 5 (0101):

$\sim x = 1010 = 10, \qquad \sim x + 1 = 1011 = 11$

আর 2⁴ − 5 = 16 − 5 = 11 ✓। টেবিলে 1011 মানে (two’s complement column) −5 ✓।

-128-এর রহস্য এবার সমাধান

x = -128 (bit pattern 1000 0000, ৮-bit)। Negation করতে ~x + 1 করি:

   x = 1000 0000
  ~x = 0111 1111
~x+1 = 1000 0000    ← 0111 1111 + 1 = 1000 0000, আবার সেই একই!

গাণিতিকভাবেও: 2⁸ − (−128) = 256 − (−128) = 384। কিন্তু 384 \bmod 256 = 128, আর 128-এর bit pattern (৮-bit-এ) 1000 0000 — যেটা two’s complement-এ পড়া হয় −128 হিসেবেই (কারণ MSB-এর ওজন ঋণাত্মক)! তাই গাণিতিক উত্তর +128 হওয়ার কথা থাকলেও, সেটা representable না বলে modular reduction তাকে আবার −128-এই ফিরিয়ে আনে। এটা প্রমাণ করে যে negation-ও একটা arithmetic operation, আর তাই এটাও overflow করতে পারে — ঠিক addition/subtraction-এর মতোই।

কেন একটা মাত্র adder circuit যথেষ্ট

x = 4-bit-এর উদাহরণেই দেখুন — bit pattern 1011-কে unsigned পড়লে 11, signed পড়লে -5। এবার এই pattern-এ 0011 (3) যোগ করুন:

  1011
+ 0011
-------
  1110

Unsigned পাঠ: 11 + 3 = 14, আর 1110 unsigned-এ 14 ✓

Signed পাঠ: -5 + 3 = -2, আর 1110 two’s complement-এ -2 ✓ (টেবিল দেখুন)

একই bit-level addition, একই circuit, দুইটা সম্পূর্ণ ভিন্ন কিন্তু দুইটাই সঠিক উত্তর — শুধু bit pattern-টা কীভাবে পড়া হচ্ছে তার উপর নির্ভর করে। এটাই দুই’s complement-এর সবচেয়ে বড় practical জয়: CPU-র ALU-তে signed আর unsigned addition-এর জন্য আলাদা circuit লাগে না। একটাই binary adder, দুই ভিন্ন interpretation।

এই কারণেই x86-এর ADD instruction-এর কোনো “signed” বা “unsigned” ভ্যারিয়েন্ট নেই — শুধু একটাই ADD। পার্থক্য আসে পরের instruction-এ (flag পড়ার সময়) — যেমন লেসন ৪-এ দেখেছেন, unsigned branch CF পড়ে, signed branch SF/OF পড়ে। Arithmetic-টা এক, শুধু ফলাফলের ব্যাখ্যা আলাদা।

বিয়োগও একই adder দিয়ে

a − b = a + (−b) = a + (\sim b + 1)। Hardware-এ এটা বাস্তবায়ন করা হয় একটা চমৎকার কৌশলে: প্রতিটা b-এর bit একটা XOR gate দিয়ে পাঠানো হয়, যার দ্বিতীয় input হলো একটা control সংকেত (subtract?)। subtract = 0 হলে XOR কিছু বদলায় না (b XOR 0 = b) — সাধারণ addition। subtract = 1 হলে XOR প্রতিটা bit উল্টে দেয় (b XOR 1 = ~b) — আর সেই একই control সংকেত adder-এর carry-in-এও 1 বসিয়ে দেয়, যা ঠিক ~b + 1 সম্পন্ন করে।

       control (0=add, 1=subtract)
              │
   b ────────XOR──────┐
                       ▼
   a ──────────────► ADDER ──► a + (b XOR control) + control
                       ▲
              carry-in = control

একটা মাত্র XOR-array আর একটা মাত্র adder circuit দিয়ে addition এবং subtraction দুটোই — এটা Level 2-এ (digital logic) আমরা পুরো circuit হিসেবে বানাব। এখানে শুধু এইটুকু বোঝাই যথেষ্ট: এই সরলীকরণ সম্ভবই হতো না যদি negation-এর সংজ্ঞা 2ⁿ − x (modular additive inverse) না হতো।

Sign extension — টাইপ বড় করার সঠিক নিয়ম

একটা int8_t-কে int32_t-তে convert করলে bit pattern-এর কী হওয়া উচিত? মান অপরিবর্তিত থাকতে হবে — -5 তখনও -5। কিন্তু bit pattern তো ৮-bit থেকে ৩২-bit-এ বড় হচ্ছে, নতুন bit গুলো কী দিয়ে ভরবেন?

উত্তর: sign bit repeat করে (sign extension), শূন্য দিয়ে নয়।

int8_t -5 = 1111 1011। int32_t-তে সঠিকভাবে widen করলে:

int8_t  (8-bit):  1111 1011
int32_t (32-bit): 1111 1111 1111 1111 1111 1111 1111 1011
                   └──────────────────────────────┘└──────┘
                        নতুন ২৪টা bit — সবই sign bit             আসল ৭ bit
                        (MSB) copy করা

কেন sign bit repeat করলে মান টিকে থাকে — প্রমাণ:

আমাদের ওজনযুক্ত সূত্র মনে করুন: value = -dₙ₋₁2^(n-1) + \sum d_i 2^i।

n-bit থেকে m-bit-এ (m > n) widen করে যদি নতুন সব bit (পজিশন n থেকে m-1) পুরনো sign bit dₙ₋₁-এর কপি হয়, তাহলে নতুন মান:

$-d_{n-1}2^{m-1} + \sum_{i=n-1}^{m-2} d_{n-1} \cdot 2^i + \sum_{i=0}^{n-2} d_i \cdot 2^i$

মাঝের যোগফলটা geometric series: d_{n-1} (2^{m-1} - 2^{n-1})। পুরোটা একসাথে সাজালে (বীজগণিত একটু ঘন, কিন্তু ফলাফল পরিষ্কার):

$= -d_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-2} d_i \cdot 2^i = \text{আগের মান, অপরিবর্তিত}$

মূল অন্তর্দৃষ্টি: sign extension আসলে n-1 থেকে m-1 পর্যন্ত “নতুন” bit-দের একসাথে যোগফলে শূন্য বানিয়ে দেয় যদি sign 0 হয় (কারণ সবগুলোই 0), আর ঋণাত্মক দিকে ঠিক পরিমাণ যোগ করে যদি sign 1 হয় — নিট ফল: মান অপরিবর্তিত।

ভুল করলে কী হয় — zero-extend দিয়ে:

int8_t  -5 =              1111 1011
ভুল (zero-extend):  0000 0000 0000 0000 0000 0000 1111 1011
                                                    = 251, signed পড়লে +251!

-5 হঠাৎ 251 হয়ে গেল — সম্পূর্ণ ভুল মান। এটা কোনো তাত্ত্বিক ভয় না, বাস্তব bug-এর প্রকৃত উৎস, নিচে দেখব।

char কি signed না unsigned — একটা লুকানো portability বিপদ

C standard char-কে ইচ্ছাকৃতভাবে implementation-defined রেখেছে — signed নাকি unsigned, সেটা compiler/platform ঠিক করে। ঐতিহাসিকভাবে x86-এ char সাধারণত signed (-128 থেকে 127), কিন্তু ARM-এ প্রায়ই unsigned (0 থেকে 255) ডিফল্ট।

এই অনিশ্চয়তা একটা ক্লাসিক bug তৈরি করে — K&R যুগ থেকে পরিচিত, আজও লেখা হয়:

#include <stdio.h>

int main(void) {
    char c;
    while ((c = getchar()) != EOF) {   /* বিপজ্জনক! */
        putchar(c);
    }
    return 0;
}

getchar() রিটার্ন করে int, আর EOF সাধারণত -1। এই কোড c-কে char-এ রাখছে — সমস্যা এখানেই।

• ইনপুটে যদি byte value 0xFF (255) আসে (যেমন UTF-8-এর অংশ, বা কোনো binary data), সেটা getchar() থেকে int হিসেবে 255 ফেরত দেয় (সঠিক)।
• এখন সেটা char c-তে রাখা হচ্ছে। যদি char signed হয় এই platform-এ, 255-এর bit pattern (1111 1111) char-এ রাখলে সেটা signed interpretation পায় — -1!
• while condition-এ c আবার int-এ sign-extend হয়ে ফেরত promote হয় (কারণ signed char → int promotion sign-extend করে): -1 (char) থেকে -1 (int)।
• আর EOF-ও -1। তুলনা c != EOF মিথ্যা — loop ভুলভাবে থেমে যায়, যদিও প্রকৃত ফাইলের শেষ আসেনি! একটা সাধারণ 0xFF byte পুরো read-loop ভেঙে দিল।

সঠিক লেখা:

int c;                              /* char নয়, int — getchar()-এর প্রকৃত রিটার্ন টাইপ */
while ((c = getchar()) != EOF) {
    putchar(c);
}

এখানে c সরাসরি int, তাই getchar()-এর ফেরত 255 (byte 0xFF) আর EOF-এর -1 — দুইটা স্পষ্টভাবে ভিন্ন int মান, কোনো signed-char সংকোচনের মধ্য দিয়ে যেতে হয়নি।

এই bug-টা সরাসরি sign extension-এর গল্প — char থেকে int-এ promote হওয়ার সময় compiler sign bit repeat করে (যদি char signed হয়), আর সেই sign-extension-ই 255-কে -1-এ রূপান্তরিত করে দেয়।