জোড়-বিজোড় বের করার পাঁচটি পদ্ধতি (সি প্রোগ্রামিং ও অন্যান্য)

Post updated on 28th November, 2016 at 01:43 pm

শিরোনাম দেখে নাক সিঁটকে বলো না “এএহ… জোড়-বিজোড় বের করা কোন ঘটনা হইলো? এইটা নিয়ে পোস্ট করার কী আছে? সব খালি post quantity বাড়ানোর ধান্দা!”

আমরা খুব সহজেই জোড় বিজোড় সংখ্যা চিনতে পারি। কম্পিউটারকেও চেনাতে পারি প্রোগ্রাম লিখে। এই পোস্টে আলোচনা করব কোন একটা সংখ্যা জোড় নাকি বিজোড় সেটা বের করার চারটা পদ্ধতি নিয়ে। তোমার যদি চারটি পদ্ধতিই জানা থাকে তাহলে পোস্টটা skip করতে পারো। এতে তোমার কিছুটা সময় বাঁচবে। 🙂

ইয়া লম্বা কোন একটা সংখ্যা তোমাকে দিয়ে সেটা জোড় নাকি বিজোড় বের করতে বললে কিন্তু তুমি চোখ বন্ধ করে ঐ সংখ্যাটার শেষ ডিজিটের দিকে তাকাবা। শেষ ডিজিট যদি ০, ২, ৪, ৬, ৮ এর মধ্যের কোনটা হয় তাহলে সেটা জোড়, অন্যথায় বিজোড়। এটা আমরা ছোট বেলাতে শিখেছিলাম অনেকটা মুখস্ত করার মত করে। যদিও ঘটনাটা হচ্ছে কোন একটা সংখ্যাকে ২ দিয়ে ভাগ করলে যদি তা নিঃশেষে বিভাজ্য হয় তবে সেটা জোড় আর যদি ভাগশেষ থাকে তবে তা বিজোড়। আর পুরো সংখ্যাটা নিয়ে চিন্তা না করে এই ২ দিয়ে ভাগ করার কাজটা যদি কোন একটা সংখ্যার শেষ ডিজিটের উপর করি তাহলেও একই রেজাল্টই আসবে। প্রোগ্রামিং এ যখন জোড় বিজোড় বের করার দরকার হয় তখন নিচের চারটা নিয়মে জোড়-বিজোড় বের করা যায়। আরো হয়ত কোন নিয়ম থেকে থাকতে পারে। তোমার সামনে পড়লে অবশ্যই শেয়ার করবে।

মোডুলো অপারেটর (Modulo Operator ‘%’) ব্যবহার করে ভাগশেষ বের করার মাধ্যমেঃ

প্রোগ্রামিং শেখার বাচ্চাকালে আমরা even odd checking এর জন্য নিচের মত কোড করেছিলাম-

if(num%2 == 0)
    printf("even");
else
    printf("odd");

অর্থাৎ num কে ২ দিয়ে mod করে ভাগশেষ বের করা হয়েছে। এবং চেক করা হচ্ছে ভাগশেষটি শূণ্য কিনা। আর ২ দিয়ে কোন পূর্ণসংখ্যাকে ভাগ করলে ভাগশেষ শূণ্য অথবা ১ হবে সেটা তো বুঝতেই পারছো। যদি ভাগশেষ শূণ্য হয় তবে প্রিন্ট করা হচ্ছে সংখ্যাটি জোড়, অন্যথায় ভাগশেষ হবে ১ আর সে জন্য প্রিন্ট করা হচ্ছে বিজোড়। এই কোড আমরা সবাই জানি তাই এর চেয়ে বেশি কথাবার্তা না বলি।

 

Division operator ‘/’ দিয়ে ভাগফল বের করার মাধ্যমেঃ

কোন একটা সংখ্যাকে ২ দিয়ে ভাগ করলে সেটি অর্ধেক হয়ে যায়। এই অর্ধেক অংশকে আবার ২ দিয়ে গুণ করলে আবার আগের সংখ্যাটাই কিন্তু পাওয়া যায়। এই ধারণাটা কাজে লাগিয়ে নিচের কোডটা করা হয়েছেঃ

if((num/2) * 2 == num)
    printf("even");
else
    printf("odd");

num যদি জোড় সংখ্যা হয় তাহলে num/2 করার ফলে এটি সমান দুই ভাগে ভাগ হয়ে যাবে। মানে পুরোপুরি অর্ধেক হয়ে যাবে। এই অর্ধেক হওয়া সংখ্যাটাকে আবার ২ দিয়ে গুণ করা হচ্ছে তাহলে কিন্তু সেটা দ্বিগুণ হয়ে আগের সংখ্যাতেই পরিণত হচ্ছে। এরপর চেক করা হচ্ছে তা num এর সমান কিনা। যদি সমান হয় তাহলে num আসলেই জোড়।

অপরপক্ষে যদি num বিজোড় হয়। ধরি, num = 5। তাহলে 5/2 করা হলে ভাগফল আসবে 2। 2.5 কিন্তু আসবে না, কারণ এটা integer division. কোন একটা সংখ্যাকে int টাইপের কোন সংখ্যা দিয়ে ভাগ করলে ভাগফলে একটি int টাইপের সংখ্যাই পাওয়া যায়। কোন ভগ্নাংশ পাওয়া যায় না। ভগ্নাংশ সহ মান পেতে হলে তাই float বা double type এর মান দিয়ে ভাগ করতে হবে। যেহেতু ৫ কে ২ দিয়ে ভাগ করলে ভাগফল পাওয়া যাচ্ছে ২ এরপর এর সাথে ২ গুণ করা হলে সংখ্যাটা দাঁড়াচ্ছে 4 যা মূল সংখ্যা 5 এর সমান নয়। তাই IF block এর statement-টা প্রিন্ট না হয়ে ELSE block এর statement-টা প্রিন্ট হচ্ছে যে, সংখ্যাটা বিজোড়। আশা করি বুঝাতে পেরেছি।

 

বিটওয়াজ এন্ড (Bitwise AND operator ‘&’) ব্যবহার করেঃ

দুটি সংখ্যার মধ্যে AND operation, OR operation এর মত ব্যাসিক কাজগুলো আশা করি তুমি জানো। এরপরেও ভুলে গিয়ে থাকলে ৫ মিনিটের এই ইউটিউব ভিডিওটা দেখে নিতে পারো।

প্রোগ্রামিং এর ক্ষেত্রে দুটি ডেসিমেল নাম্বারের মধ্যে AND অপারেশন করলে মূলত তাদের বাইনারি নাম্বারের মধ্যেই অপারেশনটা ঘটে। (5 & 1) করা হলে মূলত কাজটা হবে এরকমঃ (101 & 001) অর্থাৎ প্রথমটা পাঁচের বাইনারি আর দ্বিতীয়টা ১ এর বাইনারি। ১ এর শুরুতে যতগুলো দরকার শূণ্য বসানো হয়েছে। অর্থাৎ কোন একটা সংখ্যার সাথে ১ এর এন্ড অপারেশন চালানো হলে ফলাফল মূলত নির্ভর করবে ঐ বাইনারি সংখ্যাটার প্রথম বিটের উপর (বাইনারি বিট count করা হয় ডান পাশ থেকে)। কারণ 5 এর সাথে 1 এর AND করলে 1 এর আগে দুইটা 00 চলে আসছে। যা 5 এর বাইনারি সংখ্যার শেষ দুইটা বিটের সাথে AND হয়ে রেজাল্ট দিবে 00. আর প্রথম জোড়া 1 – 1 এর AND এর ফলে রেজাল্ট আসছে 1. সুতরাং, (5&1) = 1.

একই কাজ যদি করা হয় কোন একটা জোড় সংখ্যার ক্ষেত্রে তাহলে বুঝতে সহজ হবে। (4 & 1) = 0. কারণ (100 & 001) = 0. শেষ দুই জোড়া bit তো জানিই 00 হবে। প্রথম জোড়া বিট 0 এবং 1 এর AND এর রেজাল্ট হবে 0.

অতএব, আমরা এই সিদ্ধান্তে উপনীত হতে পারি যে, যে কোন জোড় সংখ্যার সাথে 1 কে AND করা হলে রেজাল্ট আসে 0 এবং বিজোড় সংখ্যার সাথে 1 কে AND করা হলে রেজাল্ট আসবে 1. এই সিদ্ধান্তের উপর ভিত্তি করে আমরা নিচের মত কোড করে জোড়-বিজোড় বের করতে পারি। যা modulo operator বা division operator দিয়ে চেক করার চেয়ে অনেক বেশি fast. কারণ এখানে একদম bit level এ কাজগুলো হচ্ছে।

if((num & 1) == 0)
    printf("even");
else
    printf("odd");

//আমি আরেকটু শর্টকাট করি নিচের মত করে

if(num & 1)
    printf("odd");
else
    printf("even);

আমাদের প্রোগ্রামিং গ্রুপের অন্যতম শ্রদ্ধাভাজন এডমিন ইমরুল ভাইয়া AND operator ব্যবহার করে নিচের এই কোডটা দিয়েছেন। ভাইয়া বলেছেন এটা একটু less efficient.

if ((n & -n) == 1)
    printf("odd");
else
    printf("even");

লেফট শিফট ও রাইট শিফট (Left shift ‘<<‘ and Right shift ‘>>’ operator) বিটওয়াইজ অপারেশনের মাধ্যমেঃ

Left shift operator এর মাধ্যমে গুণের কাজ আর Right shift operator এর মাধ্যমে ভাগের কাজ করা যায়। এ বিষয়ে ধারণা না থাকলে নিচের ভিডিও দুইটা দেখা যেতে পারে।

দ্বিতীয় পয়েন্টে ভাগ করার মাধ্যমে যেভাবে বের করা হয়েছিল জোড়-বিজোড় কিনা সেই একই concept এর উপর base করে এখানে কাজটা করা হবে শিফট অপারেটরের মাধ্যমে। যা ভাগ করার চেয়ে অনেক বেশি faster!

একটা জোড় সংখ্যাকে একবার রাইট শিফট করলাম, আর একবার লেফট শিফট করলাম। প্রথমটায় অর্ধেক হল আর দ্বিতীয়টায় সংখ্যাটা দ্বিগুণ হল।

4 >> 1 – ( 0100 ) >> 1 = 2. [সমান ২ ভাগে বিভক্ত]
4 << 1 – ( 0100 ) << 1 = 8.

একই কাজ একটা বিজোড় সংখ্যার উপর করিঃ

5 >> 1 – ( 0101 ) >> 1 = 2. [সমান ভাবে বিভক্ত হয় নি]
5 << 1 – ( 0101 ) << 1 = 10.

আমাদের algorithm টা হবে কোন একটা সংখ্যাকে প্রথমে ১ বিট রাইট শিফট করব (অর্থাৎ ২ দিয়ে ভাগ) এরপর প্রাপ্ত ফলাফলকে ১ বিট লেফট শিফট করব (অর্থাৎ ২ দিয়ে গুণ করব) এরপর প্রাপ্ত ফলাফলকে চেক করব আমাদের মূল সংখ্যার সাথে। যদি তারা সমান হয় তবে সেটি জোড়, কারণ ভাগ করার কারণে সমান ২ ভাগ হয়েছে আবার গুণ করার কারণে আগের অবস্থায় ফেরত এসেছে। কিন্তু যদি সংখ্যা দুটি সমান না হয় তাহলে বুঝতে হবে সেটি ছিল বিজোড় সংখ্যা। লেফট শিফট করার সময় 0.5 অংশ হারিয়ে গেছে এর ফলে ২ গুণ করার পরে সংখ্যা দুটি সমান হয় নি।

হিসাবটা দেখা যাকঃ

( 4 >> 1 ) << 1 = ( 2 ) << 1 = 4 [জোড় সংখ্যা। রাইট শিফট,লেফট শিফট। আগের আগের সংখ্যা ফেরত পাওয়া গেল]
( 5 >> 1 ) << 1 = ( 2 ) << 1 = 4 [বিজোড় সংখ্যা। রাইট শিফটেই সংখ্যা কমে গেল। লেফট শিফটে দ্বিগুণ হল কিন্তু মূল সংখ্যার সমান হল না]

কোডটা করে ফেলিঃ

int res = (num >> 1) << 1; // right shift by 1 bit and then left shift by 1 bit

if(res == num)
    printf("even");
else
    printf("odd");


//প্রথম লাইনটাও কমাতে চাইলে এভাবে লেখা যায় 

if(((num >> 1) << 1) == num)
    printf("even");
else
    printf("odd");

 

XOR ব্যবহার করেঃ

২০১৬ সালের ACM ICPC World Finalist নিলয় ভাইয়ের থেকে এই কোডটা পাইঃ

if ( (num ^ 1) < num)
    printf("odd");
else
    printf("even");

 

আমি পারসোনাল্যি AND অপারেটর ব্যবহার করেই চেক করি। শিফট দিয়ে এত হাবিজাবি করার কোন দরকার দেখি না। কিন্তু ব্যাপারটা জানা থাকলে লস নাই। হুট করে হয়ত কখনো এই bit shifting এর concept টা কোথাও কাজে লেগে যেতে পারে।

ফেসবুকের প্রোগ্রামিং গ্রুপে এই লেখা পোস্টের সময় ক্যাপশন দিয়েছিলাম “এটা বাচ্চাদের জন্য পোস্ট”।  শ্রদ্ধেয় শান্ত ভাইয়া কমেন্টে এই কথাটা বললেনঃ “it might be fun/interesting if you challenge “seniors” to figure out the limit of num (considering int as the data type) for each of the methods.”

সুতরাং মেথডগুলো ব্যবহার করার সময় এটাও মাথায় রাখা উচিত যে ইনপুটের নাম্বারগুলো কত বড় হবে? বেশি বড় সংখ্যা হলে over flow হতে পারে। শান্ত ভাইয়াকে ধন্যবাদ, বিষয়টা উল্লেখ করায়। আরো বেশি ধন্যবাদ কষ্ট করে আমার লেখা পড়ার জন্য! :O

আরো কোন ভাবে জোড়-বিজোড় বের করা গেলে জানাতে পারো। চেষ্টা করব এড করে দেয়ার জন্য। আর বাংলা ভাষায় কনটেন্ট বাড়ানোর জন্যেই লেখালেখির চেষ্টা করা। বাংলা ভাষাভাষী মানুষদের কাছে না পৌঁছালে এই পরিশ্রম বৃথা। তাই শেয়ার করতে ভুলো না… 🙂