একটি বাইনারি ট্রি দেওয়া আছে, ফাংশনটি নোডগুলোর কিগুলোর বাইনারি ভ্যালু জেনারেট করবে এবং তারপর সেই বাইনারি সমতুল্যে সেট বিট (১) এর সংখ্যা রিটার্ন করবে।
উদাহরণ
বাইনারি ট্রিতে কি হিসেবে: 10 3 211 140 162 100 এবং 146
| Key | বাইনারি সমতুল্য | সেট বিট (আউটপুট) |
|---|---|---|
| 10 | 1010 | 2 |
| 3 | 0011 | 2 |
| 211 | 11010011 | 5 |
| 140 | 10001100 | 3 |
| 162 | 10100010 | 3 |
| 100 | 1100100 | 3 |
| 146 | 10010010 | 3 |
এখানে আমরা __builtin_popcount ফাংশন ব্যবহার করছি
ফাংশন প্রোটোটাইপ হলো নিচের মতো −
int __builtin_popcount(unsigned int)
এটি একটি ইন্টিজারে সেট বিটের সংখ্যা রিটার্ন করে অর্থাৎ ইন্টিজারের বাইনারি রিপ্রেজেন্টেশনে ১-এর সংখ্যা।
অ্যালগরিদম
START Step 1 → create a structure of a node as struct Node struct node *left, *right int data End Step 2 → function to create a node node* newnode(int data) node->data = data node->left = node->right = NULL; return (node) Step 3 → Create function for generating bits of a node data void bits(Node* root) IF root = NULL return print __builtin_popcount(root->data) bits(root->left) bits(root->right) step 4 → In main() create tree using Node* root = newnode(10) root->left = newnode(3) call bits(root) STOP
উদাহরণ
#include <bits/stdc++.h> using namespace std; // structure of a node struct Node { int data; struct Node *left, *right; }; //function to create a new node Node* newnode(int data) { Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node); } //function for finding out the node void bits(Node* root){ if (root == NULL) return; //__builtin_popcount counts the number of set bit of a current node cout << "bits in node " << root->data << " = " <<__builtin_popcount(root->data)<< "\n"; bits(root->left); bits(root->right); } int main(){ Node* root = newnode(10); root->left = newnode(3); root->left->left = newnode(140); root->left->right = newnode(162); root->right = newnode(211); root->right->left = newnode(100); root->right->right = newnode(146); bits(root); return 0; }
আউটপুট
যদি আমরা উপরের প্রোগ্রামটি রান করি তবে এটি নিচের আউটপুট জেনারেট করবে
bits in node 10 = 2 bits in node 3 = 2 bits in node 140 = 3 bits in node 162 = 3 bits in node 211 = 5 bits in node 100 = 3 bits in node 146 = 3
