Integer-এর বিট-রূপ — unsigned, sign-magnitude, two's complement আর overflow

১ · বিটের সারি নিজে কিছু বলে না — fixed width আর interpretation

পর্ব ০৪-এ (সংখ্যা পদ্ধতি) আপনি দেখেছেন, যেকোনো ধনাত্মক পূর্ণসংখ্যা binary-তে লেখা যায়। কিন্তু কাগজে লেখা আর CPU-র ভেতরে রাখার মধ্যে একটি বড় পার্থক্য আছে। কাগজে আপনি যত খুশি অঙ্ক লিখতে পারেন। CPU-র register-এর ঘর কিন্তু গোনা — ৮, ১৬, ৩২ বা ৬৪টি বিট। একে বলে fixed-width integer.

n বিটে প্রতিটি বিট ০ অথবা ১, তাই মোট 2ⁿটি আলাদা bit pattern সম্ভব। ৮ বিটে ২৫৬টি, ১৬ বিটে ৬৫,৫৩৬টি, ৩২ বিটে প্রায় ৪৩০ কোটি। এর বেশি একটিও নয়। কোন প্যাটার্ন কোন সংখ্যা বোঝাবে, সেটা আমরা ঠিক করি — hardware শুধু প্যাটার্ন রাখে। একই ৮টি বিট 1101 0011 নিচের প্রতিটি নিয়মে আলাদা অর্থ দেয় (প্রতিটি নিয়ম পরের অংশগুলোতে বিস্তারিত দেখবেন):

সবচেয়ে বাঁয়ের বিটকে বলে MSB (most significant bit — সবচেয়ে বেশি ওজনের বিট), আর সবচেয়ে ডানেরটিকে LSB. নিচের ছকে প্রচলিত width আর তাদের সীমা দেওয়া হলো — এই সংখ্যাগুলো বিশ্ববিদ্যালয় ও চাকরির পরীক্ষায় বারবার আসে:

২ · Unsigned — 0 থেকে 2ⁿ − 1, আর ঘুরে আসা (wrap-around)

সবচেয়ে সরল নিয়ম হলো unsigned integer — চিহ্নহীন সংখ্যা। বিটগুলো b_n−1 … b₁ b₀ হলে মান

সবচেয়ে ছোট মান ০ (সব বিট ০)। সবচেয়ে বড় মান সব বিট ১ হলে: 1 + 2 + 4 + … + 2ⁿ⁻¹. এটি একটি গুণোত্তর ধারা, যোগফল 2ⁿ − 1. সহজ প্রমাণ: এই সংখ্যার সাথে ১ যোগ করলে সব ঘরে carry ছড়িয়ে পড়ে আর পাওয়া যায় 1 000…0 (১-এর পরে n টি শূন্য), যা ঠিক 2ⁿ. তাই ৮ বিটে সর্বোচ্চ 255, ৩২ বিটে 4,294,967,295.

সীমা পেরোলে কী হয় — মিটারের মতো ঘুরে আসা

n বিটের hardware ঠিক এভাবে modular arithmetic করে — প্রতিটি যোগ, বিয়োগ আর গুণের ফল থেকে শুধু নিচের n বিট রাখে, অর্থাৎ ফল mod 2ⁿ. ৮ বিটে 255 + 1 = 0, 200 + 100 = 44 (কারণ 300 − 256 = 44), আর 0 − 1 = 255. একে বলে wrap-around. Unsigned যোগে আসল ফল 2ⁿ-এর সমান বা বেশি হলে MSB থেকে একটি carry বেরিয়ে যায় — সেই বেরিয়ে যাওয়া carry-ই বলে দেয় যে unsigned overflow হয়েছে। x86 বা ARM-এর মতো CPU সেটি carry flag (C)-এ লিখে রাখে; RISC-V-এ flag নেই, সেখানে তুলনা করে ধরতে হয় (flag-এর circuit পর্ব ১৩ আর ২০-এ)।

৩ · ঋণাত্মক সংখ্যার প্রথম দুই চেষ্টা — sign-magnitude আর one's complement

এবার ঋণাত্মক সংখ্যা, অর্থাৎ signed integer. কাগজে আমরা সামনে একটি “−” চিহ্ন বসাই। কিন্তু বিটের জগতে “−” বলে কিছু নেই, আছে শুধু ০ আর ১। তাই কোনো একটি নিয়মে কিছু প্যাটার্নকে ঋণাত্মক মান হিসেবে ধরতে হয়। ইতিহাসে তিনটি প্রধান নিয়ম চেষ্টা করা হয়েছে, আর একটি চতুর্থ নিয়ম বিশেষ কাজে টিকে আছে।

Sign-magnitude — মানুষের লেখার হুবহু নকল

Sign-magnitude-এ MSB চিহ্ন (০ = ধনাত্মক, ১ = ঋণাত্মক), বাকি n − 1 বিট পরম মান। ৪ বিটে +5 = 0101, −5 = 1101. সীমা −(2ⁿ⁻¹ − 1) থেকে +(2ⁿ⁻¹ − 1); ৪ বিটে −7 … +7. বোঝা সহজ, কিন্তু দুটি সমস্যা:

• দুটি শূন্য: 0000 = +0 আর 1000 = −0. তুলনার circuit-কে মনে রাখতে হয় যে দুটি আলাদা প্যাটার্ন সমান।
• যোগ ঝামেলার: সাধারণ binary যোগে +3 + (−2) = 0011 + 1010 = 1101 = −5, যা ভুল। ঠিক উত্তর পেতে আগে চিহ্ন দেখতে হয়, চিহ্ন ভিন্ন হলে বড় মান থেকে ছোট মান বিয়োগ করতে হয়, তারপর বড়টির চিহ্ন বসাতে হয় — মানে আলাদা subtractor আর তুলনার circuit.

তবু sign-magnitude মরেনি: IEEE 754 floating point-এ চিহ্নের বিট আলাদা, যা আসলে sign-magnitude চিন্তা (পর্ব ২৩)।

One's complement — সব বিট উল্টে দেওয়া

One's complement-এ −x পেতে x-এর প্রতিটি বিট উল্টানো হয়: −x = ~x (এই পর্বে ~ মানে bitwise NOT, অর্থাৎ প্রতিটি বিট উল্টানো)। ৪ বিটে +5 = 0101, −5 = 1010. সীমা sign-magnitude-এর মতোই −7 … +7, আর এখানেও দুটি শূন্য: 0000 আর 1111.

যোগ প্রায় সাধারণ binary যোগ, শুধু একটি বাড়তি নিয়ম: MSB থেকে carry বেরোলে সেটি ফেলে না দিয়ে আবার LSB-তে যোগ করতে হয় — একে বলে end-around carry. উদাহরণ: (−2) + 5 = 1101 + 0101 = 1 0010. বেরিয়ে যাওয়া ১-টি ঘুরিয়ে এনে 0010 + 1 = 0011 = +3. ঠিক উত্তর, কিন্তু carry-কে দুবার ঘুরতে হয় বলে hardware ধীর আর জটিল।

৪ · Two's complement — আজকের প্রায় সব CPU-র নিয়ম (প্রমাণসহ)

Two's complement-এর মূল চিন্তাটি এক লাইনের: MSB-এর ওজন ধনাত্মক নয়, ঋণাত্মক। n বিটে MSB-এর ওজন −2ⁿ⁻¹, বাকি সব আগের মতো:

৮ বিটে ওজনগুলো: −128, 64, 32, 16, 8, 4, 2, 1. MSB ০ হলে সংখ্যাটি unsigned-এর মতোই ০ … 127. MSB ১ হলে −128-এর সাথে বাকি সাত বিটের (০ … 127) যোগ, তাই −128 … −1. মোট সীমা −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1, আর শূন্য মাত্র একটি (0000 0000). দুটি শূন্য না থাকায় একটি প্যাটার্ন বেঁচে যায়, সেটিই বাড়তি ঋণাত্মক সংখ্যা −128 — এই অসমতার কথা অংশ ৭-এ আবার আসবে।

−x = ~x + 1 কেন ঠিক — ছোট্ট প্রমাণ

যেকোনো n বিটের x আর তার উল্টো ~x পাশাপাশি যোগ করুন। প্রতিটি ঘরে একটি ০ আর একটি ১, তাই কোনো carry হয় না, ফল সব-১: x + ~x = 2ⁿ − 1. দুই পাশে ১ যোগ করলে x + (~x + 1) = 2ⁿ. n বিটের hardware mod 2ⁿ হিসাব করে, আর 2ⁿ ≡ 0 (mod 2ⁿ). অর্থাৎ ~x + 1 এমন একটি সংখ্যা, যা x-এর সাথে যোগ করলে n বিটে ঠিক ০ পাওয়া যায় — এটাই −x-এর সংজ্ঞা। আরেকভাবে বললে, −x রাখা হয় 2ⁿ − x প্যাটার্নে; “two's complement” নামটিও এখান থেকে — 2ⁿ-এর পরিপূরক।

নিচের stepper-এ −45-এর ৮ বিট রূপ ধাপে ধাপে বের করা হলো। “পরে” চাপুন:

45 = 32 + 8 + 4 + 1
   = 101101 (binary)

weight  -128 64 32 16  8  4  2  1
+45        0  0  1  0  1  1  0  1   = 0010 1101

x       0010 1101
~x      1101 0010   (one's complement = -45 there)

~x      1101 0010
 +              1
        ---------
-45     1101 0011   = 0xD3

weight  -128 64 32 16  8  4  2  1
bits       1  1  0  1  0  0  1  1
value   -128 +64 +16 +2 +1 = -45

  0010 1101   (+45)
+ 1101 0011   (-45)
-----------
1 0000 0000   carry out is dropped -> 0

একই adder কেন signed আর unsigned দুটোতেই চলে

এটিই two's complement-এর জয়ের আসল কারণ, আর পরীক্ষায় এর প্রমাণ চাওয়া হয়। যেকোনো মান v-এর জন্য তার n বিটের প্যাটার্ন P(v) হলো v mod 2ⁿ — unsigned সংখ্যার জন্য এটি সরাসরি সত্য, আর ঋণাত্মক −x-এর প্যাটার্ন 2ⁿ − x, যা −x mod 2ⁿ. এবার adder শুধু দুটি প্যাটার্ন যোগ করে নিচের n বিট রাখে:

মাঝের সমতাটি modular গণিতের মৌলিক নিয়ম: (a mod m + b mod m) mod m = (a + b) mod m. তাই a আর b-কে unsigned ধরুন বা signed — যতক্ষণ আসল যোগফল a + b সেই নিয়মের সীমার ভেতরে থাকে, adder-এর দেওয়া প্যাটার্নই সঠিক উত্তরের প্যাটার্ন। Hardware-কে জানতেই হয় না সংখ্যাগুলো কোন চশমায় পড়া হবে। বিয়োগও একই adder-এ হয়: a − b = a + ~b + 1 (adder-subtractor circuit পর্ব ২০-এ)। শুধু একটি জিনিস আলাদা — ফল সীমার বাইরে গেল কি না, সেটি চেনার নিয়ম (অংশ ৭)। RISC-V-তে তাই add instruction একটিই, signed আর unsigned-এর আলাদা যোগ নেই।

নিচের simulator ৪ বিটের সব ১৬টি প্যাটার্নকে পাঁচ নিয়মে পড়ে, তারপর কয়েকটি ৮ বিট সংখ্যায় ~x + 1 ধাপে ধাপে দেখায়। N বা তালিকার সংখ্যা বদলে নিজে চালিয়ে দেখুন — Run চাপুন:

// 4-bit patterns under five interpretations, then 8-bit negation -x = ~x + 1.
const N = 4, M = 1 << N;                        // 16 patterns
const bin = (v, n) => v.toString(2).padStart(n, "0");
const signMag = p => (p >> (N - 1)) ? -(p & (M / 2 - 1)) : p;
const onesC   = p => (p >> (N - 1)) ? -(~p & (M - 1)) : p;
const twosC   = p => (p >> (N - 1)) ? p - M : p;
const excess  = p => p - M / 2;                 // bias K = 2^(N-1) = 8
const f = v => (Object.is(v, -0) ? "-0" : String(v)).padStart(6);
console.log("bits   uns s-mag  1'sC  2'sC  ex-8");
for (let p = 0; p < M; p++)
  console.log(`${bin(p, N)}${f(p)}${f(signMag(p))}${f(onesC(p))}` +
              `${f(twosC(p))}${f(excess(p))}`);

console.log("\n8-bit negation: -x = ~x + 1");
for (const x of [45, 1, 0, 127, -128]) {
  const p = x & 0xFF, inv = ~p & 0xFF, r = (inv + 1) & 0xFF;
  const s = r >= 128 ? r - 256 : r;
  console.log(`${String(x).padStart(4)}: ${bin(p, 8)}  ~ ${bin(inv, 8)}` +
              `  +1 ${bin(r, 8)} = ${s}`);
}

bits   uns s-mag  1'sC  2'sC  ex-8
0000     0     0     0     0    -8
0001     1     1     1     1    -7
0010     2     2     2     2    -6
0011     3     3     3     3    -5
0100     4     4     4     4    -4
0101     5     5     5     5    -3
0110     6     6     6     6    -2
0111     7     7     7     7    -1
1000     8    -0    -7    -8     0
1001     9    -1    -6    -7     1
1010    10    -2    -5    -6     2
1011    11    -3    -4    -5     3
1100    12    -4    -3    -4     4
1101    13    -5    -2    -3     5
1110    14    -6    -1    -2     6
1111    15    -7    -0    -1     7

8-bit negation: -x = ~x + 1
  45: 00101101  ~ 11010010  +1 11010011 = -45
   1: 00000001  ~ 11111110  +1 11111111 = -1
   0: 00000000  ~ 11111111  +1 00000000 = 0
 127: 01111111  ~ 10000000  +1 10000001 = -127
-128: 10000000  ~ 01111111  +1 10000000 = -128

৫ · Biased বা excess-K, আর চার পদ্ধতির পাশাপাশি তুলনা

চতুর্থ নিয়ম excess-K (biased representation). প্যাটার্নকে unsigned হিসেবে পড়ে তা থেকে একটি স্থির সংখ্যা K — যাকে বলে bias — বাদ দেওয়া হয়: মান = U − K. ৪ বিটে K = ৮ নিলে 0000 = −8, 1000 = 0, 1111 = +7.

এর বিশেষ সুবিধা: প্যাটার্নের unsigned ক্রম আর মানের ক্রম হুবহু এক। −8 থেকে +7 পর্যন্ত মানগুলো 0000 থেকে 1111 পর্যন্ত সোজা বাড়ে। তাই দুটি সংখ্যা তুলনা করতে সাধারণ unsigned comparator-ই যথেষ্ট। এজন্য IEEE 754 floating point-এর exponent excess-K রূপে রাখা হয় — single precision-এ K = 127, double-এ 1023 (পর্ব ২৩-এ বিস্তারিত)। খেয়াল করুন: K = 2ⁿ⁻¹ হলে excess-K আর two's complement-এর পার্থক্য শুধু MSB-তে — একটির MSB উল্টালেই অন্যটি পাওয়া যায়। ADC (analog-to-digital converter)-এর “offset binary” আউটপুটও আসলে এই নিয়ম।

৪ বিটে −8 থেকে +7 প্রতিটি মান কোন নিয়মে কোন প্যাটার্ন — পরীক্ষার জন্য সবচেয়ে কাজের ছক:

৬ · Width বদলানো — sign extension, zero extension আর truncation

প্রোগ্রামে প্রায়ই ছোট width থেকে বড় width-এ যেতে হয়: মেমরি থেকে একটি ৮ বিটের char এনে ৩২ বা ৬৪ বিটের register-এ রাখা, বা int-কে long বানানো। প্রশ্ন হলো, নতুন বাঁয়ের বিটগুলোতে কী বসবে?

• Zero extension: নতুন সব বিটে ০. Unsigned সংখ্যার জন্য ঠিক, কারণ নতুন ঘরগুলোর ওজন যোগ হয় না।
• Sign extension: নতুন সব বিটে MSB-র কপি। Two's complement সংখ্যার জন্য এটিই ঠিক।

MSB কপি করলে মান কেন একই থাকে — প্রমাণ

একবারে মাত্র একটি বিট বাড়ানোর কথা ভাবুন; বাকিটা একই যুক্তি বারবার প্রয়োগ (induction). MSB ০ হলে নতুন বিটও ০, কিছুই বদলায় না। MSB ১ হলে n বিটে মান −2ⁿ⁻¹ + R, যেখানে R নিচের n − 1 বিটের মান। n + 1 বিটে নতুন MSB ১ (ওজন −2ⁿ), আর পুরোনো MSB-টি এখন সাধারণ ধনাত্মক ঘর (ওজন +2ⁿ⁻¹). নতুন মান = −2ⁿ + 2ⁿ⁻¹ + R = −2ⁿ⁻¹ + R. হুবহু আগের মান। অর্থাৎ, একটি −2ⁿ⁻¹ ওজনকে ভেঙে “−2ⁿ + 2ⁿ⁻¹” লেখা হয়েছে মাত্র।

bit       7 6 5 4 3 2 1 0
          1 1 0 1 0 0 1 1    = 0xD3 = -45
          ^ MSB = 1 (negative)

1111 1111 1101 0011    = 0xFFD3

as unsigned: 0xFFD3 = 65491
65491 - 65536 = -45

by weights : -32768 + (16384+...+128)
           = -32768 + 32640 = -128   (same as old MSB)

0000 0000 1101 0011    = 0x00D3 = 211   (not -45!)

8-bit : 0010 1101
16-bit: 0000 0000 0010 1101 = 45   (sign = zero ext.)

উল্টো দিক — truncation

বড় width থেকে ছোট width-এ নিলে ওপরের বিটগুলো কেটে ফেলা হয় — একে বলে truncation. ফল হয় মূল মান mod 2^k (k = নতুন width). ১৬ বিটের 300 (0000 0001 0010 1100) ৮ বিটে নিলে থাকে 0010 1100 = 44. আর −129 (১৬ বিটে 1111 1111 0111 1111) ৮ বিটে নিলে থাকে 0111 1111 = +127 — চিহ্নই বদলে গেল! নিয়ম: মান নতুন width-এর সীমায় ধরলে truncation মান বদলায় না; না ধরলে বদলাবেই। C-তে ছোট unsigned type-এ রূপান্তর নিয়মমতো mod 2^k; ছোট signed type-এ সীমার বাইরের মান রূপান্তর মানদণ্ডে implementation-defined — GCC নথিতে বলে সে mod 2^k করে।

৭ · Overflow — unsigned-এর carry বনাম signed-এর V

অংশ ৪-এ দেখেছেন, একই adder দুই অর্থেই কাজ করে — যতক্ষণ ফল সীমার ভেতরে থাকে। সীমা ছাড়ালে কী হয়, আর কীভাবে চেনা যায়?

ভিন্ন চিহ্নের দুটি সংখ্যা যোগে কখনো signed overflow হয় না। কারণ: একটি ≥ ০ আর একটি < ০ হলে যোগফল দুটি সংখ্যার মাঝখানে থাকে — বড়টির চেয়ে বড় নয়, ছোটটির চেয়ে ছোট নয়। দুটিই সীমার ভেতরে ছিল, তাই যোগফলও ভেতরে। আর একই চিহ্নের দুটি সংখ্যার যোগফল সীমার বাইরে গেলে, সেটি বড়জোর 2 × (−2ⁿ⁻¹) = −2ⁿ বা 2 × (2ⁿ⁻¹ − 1) পর্যন্ত যায়; mod 2ⁿ-এ সেটি ঠিক এক “পাক” ঘুরে উল্টো চিহ্নের অর্ধেকে পড়ে। তাই চিহ্ন বদলে যাওয়াই নিশ্চিত লক্ষণ।

V = C_in ⊕ C_out — hardware-এর এক-গেটের নিয়ম

Hardware-এর জন্য “চিহ্ন দেখা” নিয়মটিকে একটি গেটে নামানো যায়। MSB-র ঘরে তিনটি ইনপুট: a₇, b₇ আর নিচ থেকে আসা carry C_in; আউটপুট sum বিট s₇ আর C_out. আটটি ক্ষেত্র দেখুন:

“Overflow?” কলাম আর শেষ কলাম আটটি সারিতেই মিলে যায় — এটাই প্রমাণ (সম্পূর্ণ ক্ষেত্র-বিশ্লেষণ বা truth table দিয়ে)। সমতুল্য আরেকটি রূপ, যা চিহ্নের বিট থেকে সরাসরি লেখা যায়: V = a₇·b₇·s₇′ + a₇′·b₇′·s₇ (এখানে ′ মানে উল্টো বা NOT). এখন সবচেয়ে বিখ্যাত উদাহরণটি বিট ধরে ধরে দেখুন:

bit        7 6 5 4 3 2 1 0
a          0 1 1 1 1 1 1 1   (+127)
b          0 0 0 0 0 0 0 1   (+1)

bit        7 6 5 4 3 2 1 0
carry-in   ? 1 1 1 1 1 1 0
a          0 1 1 1 1 1 1 1
b          0 0 0 0 0 0 0 1
sum        ? 0 0 0 0 0 0 0

bit        7 6 5 4 3 2 1 0
carry-in   1 1 1 1 1 1 1 0
a          0 1 1 1 1 1 1 1
b          0 0 0 0 0 0 0 1
sum        1 0 0 0 0 0 0 0
carry-out of bit 7 = 0

127 + 1 = 128 -> pattern 1000 0000 = 128   C = 0, correct

V = Cin(bit7) xor Cout(bit7) = 1 xor 0 = 1
+127 + +1 -> 1000 0000 = -128   overflow!
sign rule: (+) + (+) gave (-)

এবার আরও কয়েকটি ক্লাসিক জোড়া। নিচের simulator একটি ৮ বিটের ripple adder — প্রতিটি বিটে full adder-এর সূত্র চালায়, MSB-তে ঢোকা carry মনে রাখে, তারপর C আর V ছাপে আর দুই চশমায় উত্তর ঠিক কি না বলে। (বিয়োগ 60 − 90 এখানে 60 + (−90) হিসেবে যোগ করা হয়েছে।)

// 8-bit ripple adder: sum bits, carry out C and signed overflow V.
const bin8 = v => v.toString(2).padStart(8, "0");
const s8 = p => (p & 0x80) ? p - 256 : p;       // pattern -> signed value
function add8(a, b) {                           // a, b: patterns 0..255
  let carry = 0, sum = 0, cin7 = 0;
  for (let i = 0; i < 8; i++) {
    const x = (a >> i) & 1, y = (b >> i) & 1;
    if (i === 7) cin7 = carry;                  // carry INTO the MSB
    sum |= (x ^ y ^ carry) << i;
    carry = (x & y) | (x & carry) | (y & carry);
  }
  return { sum, C: carry, V: cin7 ^ carry };
}
const tests = [[100, 50], [-100, -50], [127, 1], [-128, -1],
               [60, -90], [-56, 100], [-1, 1]];
for (const [x, y] of tests) {
  const a = x & 0xFF, b = y & 0xFF, { sum, C, V } = add8(a, b);
  const uOk = a + b === sum ? "ok" : "WRONG";
  const sOk = x + y === s8(sum) ? "ok" : "WRONG";
  console.log(`${x} + ${y}: ${bin8(a)} + ${bin8(b)} = ${bin8(sum)}  C=${C} V=${V}`);
  console.log(`   unsigned ${a}+${b} -> ${sum} ${uOk};` +
              ` signed ${x}+${y} -> ${s8(sum)} ${sOk}`);
}

100 + 50: 01100100 + 00110010 = 10010110  C=0 V=1
   unsigned 100+50 -> 150 ok; signed 100+50 -> -106 WRONG
-100 + -50: 10011100 + 11001110 = 01101010  C=1 V=1
   unsigned 156+206 -> 106 WRONG; signed -100+-50 -> 106 WRONG
127 + 1: 01111111 + 00000001 = 10000000  C=0 V=1
   unsigned 127+1 -> 128 ok; signed 127+1 -> -128 WRONG
-128 + -1: 10000000 + 11111111 = 01111111  C=1 V=1
   unsigned 128+255 -> 127 WRONG; signed -128+-1 -> 127 WRONG
60 + -90: 00111100 + 10100110 = 11100010  C=0 V=0
   unsigned 60+166 -> 226 ok; signed 60+-90 -> -30 ok
-56 + 100: 11001000 + 01100100 = 00101100  C=1 V=0
   unsigned 200+100 -> 44 WRONG; signed -56+100 -> 44 ok
-1 + 1: 11111111 + 00000001 = 00000000  C=1 V=0
   unsigned 255+1 -> 0 WRONG; signed -1+1 -> 0 ok

অসমতার ফাঁদ — −(−128) আর INT_MIN

Two's complement-এ ঋণাত্মক দিকে একটি মান বেশি: ৮ বিটে −128 আছে, +128 নেই। তাই −(−128) হিসাব করলে ~1000 0000 + 1 = 0111 1111 + 1 = 1000 0000 — আবার −128 (প্রথম simulator-এর শেষ সারি)। ৩২ বিট int-এ একই ঘটনা INT_MIN = −2,147,483,648-এর সাথে: -INT_MIN, abs(INT_MIN), এমনকি INT_MIN / -1 — তিনটিরই আসল উত্তর +2,147,483,648, যা int-এ ধরে না। C-তে তিনটিই undefined behaviour; x86-64-এ INT_MIN / -1 সাধারণত hardware exception দিয়ে প্রোগ্রাম থামিয়ে দেয়, যদিও শূন্য দিয়ে ভাগ হয়নি। “একটি সংখ্যার পরম মান সবসময় ধনাত্মক” — integer-এর জগতে কথাটি সত্য নয়।

৮ · C ভাষায় integer — রূপান্তরের নিয়ম, ফাঁদ আর undefined behaviour

Hardware-এর নিয়ম সহজ: বিট যোগ হয়, flag ওঠে। কিন্তু C ভাষা এর ওপর নিজের কিছু নিয়ম বসিয়েছে, আর বাস্তবের বহু বাগ ও নিরাপত্তা-ত্রুটি এই নিয়মের ফাঁক থেকে আসে। (C-র bitwise operator-এর বিস্তারিত পাবেন C কোর্সের Bitwise operations পর্বে, আর type রূপান্তরের নিয়ম Type conversion পর্বে।)

ফাঁদ ১: -1 > 0u সত্য

C-তে কোনো operator-এর দুই পাশে ভিন্ন type থাকলে আগে usual arithmetic conversions হয়। তার আগে char, short-এর মতো ছোট type integer promotion-এ int হয়ে যায়। এরপর নিয়মটি মোটামুটি এমন: একই “rank”-এর (একই আকারের) int আর unsigned int মিললে int-টি unsigned-এ রূপান্তরিত হয়। আর −1-কে unsigned-এ নিলে পাওয়া যায় 2³² − 1 = 4,294,967,295 (mod 2³²). ফলে -1 > 0u আসলে তুলনা করে 4294967295 > 0 — সত্য।

আরও সূক্ষ্ম অংশ: ফল platform-এর ওপর নির্ভর করে। -1L > 0u (long বনাম unsigned int) x86-64 Linux-এ মিথ্যা, কারণ সেখানে long ৬৪ বিটের আর সব unsigned int মান ধরতে পারে, তাই unsigned-টিই long হয়ে যায়। কিন্তু ৬৪ বিট Windows-এ long ৩২ বিটের, তাই একই তুলনা সত্য! sizeof আর strlen ফেরত দেয় size_t, যা unsigned — তাই if (strlen(a) - strlen(b) < 0) কখনো সত্য হয় না।

ফাঁদ ২: কখনো শেষ না হওয়া লুপ

/* উদাহরণ — bug: i is unsigned, so i >= 0 is always true */
for (unsigned i = n; i >= 0; i--)
    process(a[i]);              /* after i = 0, i-- gives 4294967295 */

/* fix: test before decrementing */
for (size_t i = n; i-- > 0; )
    process(a[i]);              /* visits n-1 ... 0, then stops */

প্রথম লুপে i = 0-এর পরে i-- wrap করে সর্বোচ্চ মানে চলে যায়, শর্ত আবার সত্য, আর a[4294967295] পড়তে গিয়ে প্রোগ্রাম সাধারণত crash করে। GCC-তে -Wextra চালু থাকলে “comparison of unsigned expression in ‘>= 0’ is always true” ধরনের warning দেয় — warning চালু রাখার আরেকটি কারণ।

ফাঁদ ৩: signed overflow — undefined behaviour

C মানদণ্ড বলে: unsigned হিসাব সবসময় mod 2ⁿ — wrap করা নিয়মসিদ্ধ। কিন্তু signed হিসাবের ফল সীমার বাইরে গেলে সেটি undefined behaviour — মানদণ্ড কোনো ফলের প্রতিশ্রুতি দেয় না। হার্ডওয়্যার তো wrap-ই করত; তাহলে সমস্যা কোথায়? সমস্যা হলো optimizer (compiler-এর যে অংশ কোড দ্রুত করে) ধরে নেয় UB কখনো ঘটে না, আর সেই ধারণা থেকে কোড বদলে দেয়। নিচের overflow-যাচাইটি দেখুন:

/* উদাহরণ — a naive overflow check */
int will_overflow(int x) {
    return x + 100 < x;        /* "if it wrapped, the sum is smaller" */
}

; what gcc -O2 -masm=intel typically emits on x86-64 (Intel syntax, illustration)
will_overflow:
        xor     eax, eax        ; always return 0
        ret

Compiler-এর যুক্তি: “signed overflow হতেই পারে না, তাই x + 100 সবসময় x-এর চেয়ে বড়, তাই ফল সবসময় 0.” পাহারাদার শর্তটি পুরোপুরি মুছে গেল। নিরাপদ বিকল্প:

• যোগের আগেই যাচাই: if (b > 0 && a > INT_MAX - b) বা if (b < 0 && a < INT_MIN - b) — এখানে কোনো overflow ঘটে না।
• Compiler-এর built-in: GCC আর Clang-এর __builtin_add_overflow(a, b, &r) ফল r-এ (wrap করা রূপে) রাখে আর overflow হলে true ফেরত দেয়; C23 মানদণ্ডে একই কাজের জন্য <stdckdint.h>-এর ckd_add এসেছে।
• বড় type-এ হিসাব: দুটি ৩২ বিট int-কে int64_t-এ যোগ করলে overflow হয় না; তারপর সীমা যাচাই।
• যাচাইয়ের টুল: -fsanitize=undefined (UBSan) চলার সময় signed overflow ধরে জানায়; -fwrapv signed হিসাবকে নিয়মমতো wrap করতে বাধ্য করে।

আরও বিস্তারিত পাবেন C কোর্সের Undefined behavior ও নিরাপদ কোড পর্বে। নিচের প্রোগ্রাম চারটি ঘটনা দেখায় — কিন্তু কোথাও signed overflow ঘটায় না:

#include <stdio.h>
#include <stdint.h>
#include <limits.h>

int main(void) {
    unsigned int u = UINT_MAX;
    printf("UINT_MAX       = %u\n", u);
    printf("UINT_MAX + 1u  = %u\n", u + 1u);       /* defined: wraps mod 2^32 */

    int neg = -1;
    unsigned int zero = 0u;
    /* what C silently does in (neg > zero): int -> unsigned int */
    printf("(unsigned)-1   = %u\n", (unsigned int)neg);
    printf("-1 > 0u        = %d\n", (unsigned int)neg > zero);
    printf("-1 > 0 (int)   = %d\n", neg > (int)zero);

    int8_t   b = -45;
    int32_t  w = b;                                 /* sign extension */
    uint32_t z = (uint8_t)b;                        /* zero extension */
    printf("int8_t -45     = 0x%02X\n", (unsigned int)(uint8_t)b);
    printf("sign-extended  = 0x%08X = %d\n", (unsigned int)w, (int)w);
    printf("zero-extended  = 0x%08X = %u\n", (unsigned int)z, (unsigned int)z);

    int r;
    if (__builtin_add_overflow(INT_MAX, 1, &r))     /* no UB is executed */
        printf("INT_MAX + 1    : overflow caught, wrapped r = %d\n", r);
    return 0;
}

UINT_MAX       = 4294967295
UINT_MAX + 1u  = 0
(unsigned)-1   = 4294967295
-1 > 0u        = 1
-1 > 0 (int)   = 0
int8_t -45     = 0xD3
sign-extended  = 0xFFFFFFD3 = -45
zero-extended  = 0x000000D3 = 211
INT_MAX + 1    : overflow caught, wrapped r = -2147483648

Shell-এর হিসাবেও fixed width আছে। Bash-এর $(( )) ৬৪ বিট signed integer (C-র intmax_t) দিয়ে হিসাব করে; bash-এর manual নিজেই বলে, overflow যাচাই করা হয় না:

# bash arithmetic: 64-bit signed integers, no overflow check
echo "max       = $(( 9223372036854775807 ))"
echo "max + 1   = $(( 9223372036854775807 + 1 ))"
echo "min - 1   = $(( -9223372036854775808 - 1 ))"
echo "2**63     = $(( 2**63 ))"
echo "2**64     = $(( 2**64 ))"
x=$(( (100 + 50) & 0xFF ))                 # keep only the low 8 bits
echo "8-bit 100+50: pattern $x, signed $(( x >= 128 ? x - 256 : x ))"

max       = 9223372036854775807
max + 1   = -9223372036854775808
min - 1   = 9223372036854775807
2**63     = -9223372036854775808
2**64     = 0
8-bit 100+50: pattern 150, signed -106

৯ · বাস্তবের দুর্ঘটনা — Ariane 5, Gangnam Style আর Year 2038

এতক্ষণের নিয়মগুলো শুধু পরীক্ষার বিষয় নয়। নিচের তিনটি ঘটনা সবচেয়ে বেশি উদ্ধৃত হয়; প্রতিটি থেকে আলাদা শিক্ষা।

১০ · AI-এর যুগে integer-এর বিট-রূপ

AI টুল two's complement-এর সংজ্ঞা নির্ভুল বলতে পারে, কিন্তু সীমানার ক্ষেত্রগুলোতে প্রায়ই হোঁচট খায় — আর বাগ থাকে ঠিক সেখানেই। কয়েকটি সাধারণ ভুল:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Width (৮/১৬/৩২/৬৪ বিট) আর নিয়ম (unsigned, two's complement…) স্পষ্ট বলা আছে
• অন্তত একটি negation বা যোগ নিজে কাগজে করেছি, আর ওজন দিয়ে (−128, 64, …) মিলিয়েছি
• সীমানার মান দিয়ে পরীক্ষা করেছি: 0, −1, সর্বোচ্চ, সর্বনিম্ন (INT_MIN), সর্বোচ্চ + 1
• C আর V আলাদা করে দেখা হয়েছে — “carry মানেই overflow” লেখা থাকলে সন্দেহ করেছি
• C কোড -Wall -Wextra -fsanitize=undefined দিয়ে চালিয়েছি, signed-unsigned তুলনার warning শূন্য
• Instruction-এর দাবি (যেমন lb sign-extend করে) ISA manual-এ মিলিয়েছি, MIPS আর RISC-V গুলিয়ে যায়নি