Unsigned Integer — শুধু অ-ঋণাত্মক সংখ্যার জগৎ

দ্রুত recap — n bit থেকে মান

আগের লেসনে দেখেছেন: n bit-এর একটা pattern dₙ₋₁ … d₁ d₀ (প্রতিটা dᵢ ∈ {0, 1}) unsigned interpretation-এ মানে:

$\text{value} = \sum_{i=0}^{n-1} d_i \cdot 2^i$

এটা ঠিক দশমিকের মতোই positional notation, শুধু base 10-এর বদলে base 2। এই লেসন এই সূত্রটা আবার derive করবে না — এটা ধরে নিচ্ছি আপনি জানেন। আমাদের আগ্রহ এখন দুইটা নতুন প্রশ্নে: range আর arithmetic।

Range — কতদূর যেতে পারে

n bit-এ মোট 2ⁿ টা আলাদা pattern সম্ভব (প্রতিটা bit স্বাধীনভাবে 0 বা 1)। Unsigned interpretation-এ এই 2ⁿ টা pattern সবচেয়ে ছোট থেকে সবচেয়ে বড় পর্যন্ত ফাঁকহীনভাবে সাজানো — 0 থেকে 2ⁿ − 1।

কেন 2ⁿ − 1, 2ⁿ নয়: সব bit 1 হলে মান 2^(n-1) + 2^(n-2) + \cdots + 2^0 = 2ⁿ − 1। এটা geometric series-এর যোগফল — Level 0-এর কম্বিনেটরিক্স লেসনে এই যোগফলের প্রমাণ দেখেছেন। মনে রাখার সহজ কৌশল: 2ⁿ মানে 1 তারপর n টা শূন্য (10000...0₂), তার থেকে 1 বিয়োগ করলে ঠিক n টা 1 (0111...1₂)।

C-তে unsigned টাইপগুলো

#include <stdint.h>   // exact-width টাইপের জন্য

uint8_t  a = 200;      // 0 .. 255,                 ঠিক ৮ bit
uint16_t b = 40000;     // 0 .. 65,535,              ঠিক ১৬ bit
uint32_t c = 3000000000u; // 0 .. 4,294,967,295,      ঠিক ৩২ bit
uint64_t d = 10000000000000000000ull; // 0 .. ~1.8×10¹⁹, ঠিক ৬৪ bit

stdint.h-এর uintN_t টাইপগুলো exact-width — গ্যারান্টি দেয় ঠিক N bit, কোনো platform-এ কম-বেশি নয়। এর আগে (C99-এর আগে) unsigned int, unsigned long ইত্যাদির প্রস্থ platform-ভেদে বদলাত — একটা unsigned long কোথাও 32-bit, কোথাও 64-bit। এই অনিশ্চয়তাই stdint.h তৈরির মূল কারণ।

Unsigned addition = arithmetic mod 2ⁿ

এবার আসল বিষয়ে। ধরুন uint8_t-এ 250 + 10 করছেন। গাণিতিকভাবে উত্তর 260। কিন্তু uint8_t মাত্র 256 টা মান ধরে রাখতে পারে (0–255)। 260 তার মধ্যে নেই। তাহলে কী হবে?

uint8_t a = 250, b = 10;
uint8_t c = a + b;
printf("%u\n", c);   // ছাপবে: 4

260 নয়, 4। কেন? কারণ:

$260 \bmod 256 = 4$

এটা কাকতালীয় নয় — এটা সংজ্ঞা। Number-systems লেসনে আমরা প্রমাণ করেছিলাম:

একটা n-bit unsigned integer আসলে ℤ_(2ⁿ)-এর একটা সদস্য। CPU-র যোগ, বিয়োগ ও গুণ আক্ষরিকভাবে mod 2ⁿ operation।

এখানে সেই লাইনটাই ফিরে আসছে, শুধু এবার পুরোপুরি unsigned-এর প্রসঙ্গে, কোনো signed জটিলতা ছাড়া। C standard (ISO/IEC 9899:2018, §6.2.5 ¶9) আক্ষরিকভাবে বলে:

“A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented.”

মানে: uint8_t-এর যোগফল সবসময় mod 256 reduce হয়। এটা কোনো accident বা hardware limitation না ধরা পড়া bug — এটা ভাষার নিয়ম।

বিট দিয়ে দেখা যাক — carry chain

250 + 10 কে বাইনারিতে যোগ করুন, হাতে-কলমে ripple carry দিয়ে:

  250 = 1111 1010
+  10 = 0000 1010
-------------------
        1 0000 0100    ← ৯ bit ফলাফল!

কলাম ধরে ধরে (ডান থেকে বাঁয়ে, প্রতিটায় carry-in যোগ):

সবচেয়ে বাঁয়ের (bit 7) carry-out 1 — এই 1 টাই ৯ম bit হয়ে “উপচে” পড়ছে। কিন্তু uint8_t মাত্র ৮টা bit ধরে রাখতে পারে। সেই ৯ম bit-টা রাখার কোনো জায়গা নেই — CPU সেটা register-এর বাইরে ফেলে দেয় (একটা flag-এ সংরক্ষণ করে, নিচে দেখব)। যা টিকে থাকে সেটা নিচের ৮টা bit: 0000 0100 = 4। ঠিক 260 mod 256।

   পূর্ণ গাণিতিক যোগফল:   1 0000 0100   (৯ bit, = 260)
                          ↓  ফেলে দেওয়া হলো
   uint8_t-এ যা থাকে:      0000 0100   (৮ bit, = 4)

এটাই ঘড়ির গণিত হাতে-নাতে। ৯টা বাজে ৫ ঘণ্টা যোগ করলে ঘড়ি “১৪” দেখায় না — কারণ ঘড়িতে “১৪”-এর জন্য কোনো ঘর নেই, শুধু ১২টা ঘর (mod 12, সাধারণত 1-12 লেখা থাকে বলে সামান্য shift আছে)। uint8_t-তে 256 টা ঘর — 0 থেকে 255।

Carry-out বনাম overflow — unsigned-এ এরা একই জিনিস

এখানে একটা পরিভাষাগত পার্থক্য স্পষ্ট করা দরকার, কারণ পরের লেসনে (signed integers) এই দুটো আলাদা হয়ে যাবে।

• Carry-out: সবচেয়ে গুরুত্বপূর্ণ bit (MSB) যোগ করার সময় যদি একটা অতিরিক্ত 1 “উপচে” পড়ে, সেটাই carry-out। এটা CPU-র একটা hardware সংকেত — x86-এ এটা Carry Flag (CF)-এ সংরক্ষিত হয়।
• Unsigned overflow: গাণিতিক ফলাফল representable range-এর বাইরে গেছে কি না।

Unsigned addition-এ এই দুইটা ঠিক একই ঘটনা। যদি a + b representable range-এর (0–2ⁿ−1) বাইরে যায়, সেটা ঘটে কেবল তখনই যখন MSB-তে carry-out হয়। প্রমাণ সহজ: a, b \< 2ⁿ, তাই a + b \< 2 \times 2ⁿ = 2^(n+1)। ফলাফল 2ⁿ বা তার বেশি হলেই তা n-bit ঘরে আঁটবে না, আর সেটা মানেই ঠিক n-তম bit-এ (bit index n, অর্থাৎ MSB-এর পরের bit) একটা 1 — যেটাই carry-out।

তাই unsigned-এ:

$\text{overflow ঘটেছে} \iff \text{carry-out} = 1$

uint32_t a = 4000000000u, b = 1000000000u;
uint32_t sum = a + b;          // wraps
int overflowed = (sum \< a);    // যদি ফলাফল a-এর চেয়ে ছোট হয়ে যায়, wrap হয়েছে
printf("sum=%u overflow=%d\n", sum, overflowed);
// sum=705032704 overflow=1

sum \< a চেকটা কাজ করে কারণ unsigned addition monotonic — b \geq 0 হলে a + b \geq a হওয়ার কথা। এটা না হলে বোঝা যায় wraparound ঘটেছে। (সতর্কতা: পরের লেসনে দেখবেন এই একই ধরনের চেক signed-এ কাজ করে না — এটা এই লেসনের সবচেয়ে গুরুত্বপূর্ণ সতর্কবার্তা, যেটার পুরো ব্যাখ্যা লেসন ৬-এ।)

Unsigned subtraction “wrap” করে — এটা bug নয়, সংজ্ঞা

এবার সবচেয়ে গুরুত্বপূর্ণ প্রশ্ন: uint8_t-এ 5 - 8 কী?

uint8_t a = 5, b = 8;
uint8_t c = a - b;
printf("%u\n", c);   // ছাপবে: 253

253? গাণিতিকভাবে 5 - 8 = -3, একটা ঋণাত্মক সংখ্যা। কিন্তু uint8_t-এ ঋণাত্মক সংখ্যা বলে কিছু নেই — সব মান 0 থেকে 255। তাহলে -3 কোথায় গেল?

$-3 \equiv 253 \pmod{256}$

কারণ 253 = 256 - 3। ঠিক number-systems লেসনের congruence-এর সংজ্ঞা: a ≡ b (mod m) ⟺ m | (a - b)। এখানে -3 আর 253 একই equivalence class [253]-এর সদস্য mod 256-এ।

এটা কোনো ত্রুটি না, কোনো “undefined” আচরণ না। C standard (§6.2.5 ¶9, উপরে উদ্ধৃত) এটাকে সরাসরি সংজ্ঞায়িত করে: unsigned বিয়োগের ফলাফল যদি representable range-এর বাইরে যায় (অর্থাৎ ঋণাত্মক হয়), সেটা mod 2ⁿ reduce হয়ে ফিরে আসে — সবসময়, প্রতিটা compiler-এ, প্রতিটা platform-এ, একইভাবে।

হাতে-কলমে — বিয়োগও আসলে যোগ

CPU-তে বিয়োগের জন্য আলাদা circuit লাগে না। a - b গণনা করা হয় a + (2ⁿ - b) হিসেবে — অর্থাৎ b-এর additive inverse mod 2ⁿ যোগ করে।

uint8_t-এ:  5 - 8
          = 5 + (256 - 8)
          = 5 + 248
          = 253            ✓ (মড়ুলো ৮ কেটে গেলে যা থাকে)

256 - 8 = 248-কে বাইনারিতে বানানোর কৌশলটাই — bit উল্টে 1 যোগ — পরের লেসনের (signed integers, two’s complement) কেন্দ্রীয় বিষয়। এখানে শুধু এইটুকু মনে রাখুন: unsigned world-এও বিয়োগ আসলে গোপনে একটা যোগ, আর সেই গোপন কৌশলটাই দুই লেসন পরে সম্পূর্ণ প্রকাশ পাবে।

size_t — কেন unsigned, আর কোথায় কামড়ায়

size_t হলো C/C++-এর একটা built-in typedef, যেটা “কোনো object-এর আকার ধরে রাখার জন্য যথেষ্ট বড় unsigned integer টাইপ” হিসেবে সংজ্ঞায়িত (C standard, stddef.h)। sizeof operator-এর ফলাফলের টাইপ এটাই, আর malloc(), strlen(), std::vector::size() — সবাই size_t ফেরত দেয়।

কেন unsigned: একটা array বা memory block-এর আকার কখনো ঋণাত্মক হতে পারে না — -5 byte-এর কোনো অর্থ নেই। তাই টাইপ-সিস্টেমে সেই সত্যটা এনকোড করে দেওয়া স্বাভাবিক মনে হয়েছিল ডিজাইনারদের কাছে: “যদি এটা ঋণাত্মক হতেই না পারে, unsigned দাও, তাহলে অর্ধেক representable range নষ্ট হবে না, আর ভুল করে ঋণাত্মক মান পাঠালে কম্পাইলার সতর্ক করবে।”

সমস্যাটা হলো এই দ্বিতীয় আশাটা বাস্তবে উল্টো ফল দেয়। size_t ঋণাত্মক হতে পারে না বলে representation-এ কোনো ভুল ঋণাত্মক মান “clamp” হয় না — বরং wrap করে বিশাল ধনাত্মক সংখ্যায় পরিণত হয়, যেটা প্রায়ই আরও বিপজ্জনক, কারণ সেটা দেখতে একটা বৈধ, বড় array-index-এর মতো।

সেই for loop-টা আবার, এবার পুরোপুরি বিশ্লেষণ করে

std::vector<int> v = {10, 20, 30};
for (size_t i = v.size() - 1; i >= 0; i--) {
    std::cout << v[i] << " ";
}

দুইটা আলাদা সমস্যা এখানে জড়িয়ে আছে — দুটোকেই আলাদা করে দেখা দরকার, কারণ মানুষ প্রায়ই শুধু একটা ধরে অন্যটা মিস করে।

সমস্যা ১ — i >= 0 শর্তটা কখনোই মিথ্যা হয় না।

size_t unsigned। Unsigned-এর সবচেয়ে ছোট মান 0। তাই i >= 0 সবসময় সত্য, i-এর মান যাই হোক — এটা tautology। Compiler এটা জানে, আর -Wall -Wextra দিলে ঠিক এই কথাই সতর্ক করে:

warning: comparison of unsigned expression '>= 0' is always true

তাই loop-টা আসলে i-- করতে করতে যখন i == 0 হয়, তার পরের বার i-- করলে i হয় SIZE_MAX (৬৪-bit-এ 18,446,744,073,709,551,615) — এখনো >= 0। Loop থামে না। v[i]-তে astronomically বড় একটা index দিয়ে access — undefined behavior, সাধারণত crash।

সমস্যা ২ — খালি vector হলে প্রথম iteration-এই বিপর্যয়।

v যদি খালি থাকে, v.size() হয় 0। v.size() - 1 তখন 0 - 1 — unsigned world-এ, যেটা আমরা এইমাত্র শিখলাম, mod 2⁶⁴ হিসেবে wrap করে SIZE_MAX। Loop প্রথম iteration-এই v[SIZE_MAX]-এ হাত দেয় — কোনো warning ছাড়াই, কারণ syntax-এর দিক থেকে সবকিছু বৈধ।

সঠিক লেখা — তিনটা বিকল্প:

// বিকল্প ১: signed loop variable, size()-কে cast করুন
for (int i = (int)v.size() - 1; i >= 0; i--) { ... }

// বিকল্প ২: postfix i-- trick — i শূন্যে পৌঁছানোর *আগেই* থামে
for (size_t i = v.size(); i-- > 0; ) {
    std::cout << v[i] << " ";
}

// বিকল্প ৩ (C++20+): reverse iterator, index-ই লাগে না
for (auto it = v.rbegin(); it != v.rend(); ++it) {
    std::cout << *it << " ";
}

দ্বিতীয় বিকল্পটা কেন কাজ করে, একটু থেমে বুঝে নেওয়া দরকার: i-- > 0 এক্সপ্রেশনে প্রথমে তুলনা হয় পুরনো i দিয়ে, তারপর i কমে। তাই i = v.size() (যেমন 3) দিয়ে শুরু হয়ে, লুপের ভেতরে ব্যবহৃত i-এর মান হয় 2, 1, 0 — আর i যখন 0-এ পৌঁছে 0 > 0 মিথ্যা হয়ে যায়, তখনই থামে, তার আগেই — কখনো wrap হওয়ার সুযোগ পায় না। v.size() == 0 হলেও নিরাপদ: i = 0, 0 > 0 মিথ্যা, loop body একবারও চলে না।

Integer promotion — ছোট unsigned টাইপের একটা চমক

শেষ একটা সূক্ষ্ম কিন্তু গুরুত্বপূর্ণ ব্যাপার। uint8_t বা uint16_t-এর মতো ছোট unsigned টাইপে arithmetic করলে C একটা আশ্চর্যজনক নিয়ম প্রয়োগ করে — integer promotion।

uint8_t a = 200, b = 100;

// আপনি ভাবতে পারেন a + b একটা uint8_t, তাই wrap করবে (300 mod 256 = 44)
if (a + b > 255) {
    printf("overflow!\n");   // এটা কি ছাপা হবে?
}

হ্যাঁ, "overflow!" ছাপা হবে — কিন্তু কারণটা আপনার ধারণার উল্টো। C-র নিয়ম বলে: int-এর চেয়ে ছোট যেকোনো integer টাইপ, arithmetic operation-এ অংশ নেওয়ার আগে, int-এ promote হয় (যদি int তার সব মান ধারণ করতে পারে, যা uint8_t-এর ক্ষেত্রে সবসময় সত্য, কারণ int কমপক্ষে ১৬ bit, বাস্তবে প্রায় সবসময় ৩২)।

তাই a + b আসলে (int)a + (int)b = 200 + 100 = 300 হিসেবে গণনা হয় — কোনো wraparound হয় না, কারণ 300 সহজেই int-এ আঁটে। তুলনাটা 300 > 255 — সত্য।

কিন্তু:

uint8_t c = a + b;
printf("%u\n", c);   // ছাপবে: 44

এখানে int-এ গণনা করা 300-কে যখন uint8_t ভেরিয়েবলে assign করা হয়, তখনই mod 256 reduction ঘটে — 300 mod 256 = 44।

শিক্ষা: wraparound ঘটে assignment বা explicit cast-এর সময়, expression evaluation-এর মাঝপথে নয় — যদি না পুরো expression-ই int-এর চেয়ে বড় বা সমান প্রস্থের unsigned টাইপে হয় (uint32_t, uint64_t — এদের int-এ promote করা হয় না, বরং উল্টোটা, int এদের টাইপে convert হয়)। uint32_t/uint64_t নিয়ে কাজ করলে promotion-এর এই চমক নেই — সরাসরি সেই টাইপেই wrap করে, যেমনটা এই লেসনের বাকি সব উদাহরণে দেখিয়েছি।