SUM from XOR and AND.

আসসালামুআলাইকুম

আপনারা কি জানেন❓ দুইটি সংখ্যা যদি a ও b হয়   তাহলে,

                       a+b=(a⊕b)+2∗(a&b)

যদি না জেনে থাকেন তাহলে জেনে নিন এই গাণিতিক বাক্যটি সত্য।

এখন আপনাদের মনে প্রশ্ন জাগতে পারে এটি কেন কাজ করে ❓

তা বোঝার জন্য চলুন ধাপে ধাপে এগোনো যাক।

প্রথম ধাপঃ

SUM ও XOR  অপারেশন দুটিকে বিটওয়াইজ চিন্তা করলে তাদের মধ্যে কোথায় কোথায় মিল আছেঃ

১।যদি দুইটি বিট এই শুন্য থাকে তাহলে আন্সার এর সাথে শুন্য যোগ হয়।

২।যদি দুইটির যেকোনো একটি বিটের মান ১ হয় তাহলে আন্সার এর সাথে ওই বিট এর মান যোগ হয়।

দ্বিতীয় ধাপঃ

SUM ও XOR অপারেশন দুটিকে বিটওয়াইজ চিন্তা করলে তাদের মধ্যে  কোথায় অমিল আছেঃ

১।যদি দুইটি বিটের মান ই  ১ হয় তাহলে SUM এর ক্ষেত্রে ওই বিটের মানের দ্বিগুন আন্সারে  কন্ট্রিবিউট হয় অন্যদিকে  XOR এর ক্ষেত্রে ০ কন্ট্রিবিউট হয়।

এখন আমরা যদি SUM কে XOR দিয়ে রিপ্লেস করতে চাই তাহলে কোথায় সমস্যা হবে ?

উত্তর হচ্ছে  দুইটি  সংখ্যারই একই পজিশনের বিট যখন  ১ হবে  তখন আন্সার এর সাথে ওই বিটের মানের দ্বিগুন কম যোগ হবে  XOR এর ক্ষেত্রে ।

এখন প্রশ্ন হচ্ছে  XOR  ব্যবহার করার ফলে যে লস হলো সেটা কি উদ্ধার করা সম্ভব ?

উত্তর হচ্ছে  সেক্ষেত্রে আমরা AND অপারেশন ব্যবহার করতে পারি।✅

আমরা জানি যে, AND অপারেশন এর ক্ষেত্রে দুইটি বিটের ই  মান যখন ১ হয় তখন আন্সার এর সাথে ওই বিটের সমান মান কন্ট্রিবিউট হয় এবং বাকি সব ক্ষেত্রে ০ যোগ হয়।অর্থাৎ,আমরা যদি দুইটি সংখ্যার AND এর মান এর দ্বিগুন XOR এর সাথে যোগ করে দেই তাহলে ওই ক্ষতিটা পুষিয়ে নেয়া যাবে।

   অর্থাৎ, আমরা বলতে পারি যে উপরের গাণিতিক বাক্যটি সত্য ।✅

আরো ভাল করে বুজতে আপনারা বাইনারিতে দুইটি সংখ্যা খাতায় লিখে ব্যপারটা লক্ষ্য করতে পারেন।

যদি ভালোভাবে বুঝতে পারেন তাহলে এই সমস্যাটি সমাদধানের চেষ্টা করতে পারেন।

1. https://codeforces.com/problemset/problem/1451/E1

না পারলে আমার সমাধান দেখতে পারেন ।

আমার লেখায় যদি কোনো ভুল আছে বলে মনে হয় অথবা কোথাও বুঝতে সমস্যা হয় তাহলে দয়াকরে কমেন্ট করে জানাবেন।

Happy Programming 💗