C++로 이진 트리 각 노드의 설정 비트(Set Bit) 개수 출력하기

이진 트리가 주어졌을 때, 노드에 저장된 키(key) 값들을 이진수로 변환한 뒤, 해당 이진 표현에서 1로 설정된 비트(set bit)의 개수를 구해 출력하는 것이 이 글의 목표입니다.

예시

키 값이 10, 3, 211, 140, 162, 100, 146인 이진 트리가 있다고 가정해 보겠습니다.

__builtin_popcount 함수란?

여기서는 GCC 컴파일러에서 제공하는 내장 함수 __builtin_popcount를 사용합니다. 함수 원형은 다음과 같습니다.

int __builtin_popcount(unsigned int)

이 함수는 정수의 이진 표현에서 1로 설정된 비트의 개수를 반환합니다. 별도의 반복문 없이 하드웨어 명령을 활용하기 때문에 매우 빠르게 동작한다는 장점이 있습니다.

알고리즘

START
Step 1 -> 노드 구조체 정의
    struct Node
      struct node *left, *right
      int data
    End
Step 2 -> 새 노드를 생성하는 함수
    node* newnode(int data)
    node->data = data
    node->left = node->right = NULL;
    return (node)
Step 3 -> 노드 데이터의 설정 비트를 세는 함수 작성
    void bits(Node* root)
    IF root = NULL
       return
    print __builtin_popcount(root->data)
    bits(root->left)
    bits(root->right)
Step 4 -> main() 함수에서
    Node* root = newnode(10) 으로 트리 생성
    root->left = newnode(3)
    bits(root) 호출
STOP

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
// 노드 구조체 정의
struct Node {
    int data;
    struct Node *left, *right;
};
// 새 노드를 생성하는 함수
Node* newnode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
// 각 노드의 설정 비트 개수를 찾는 함수
void bits(Node* root){
    if (root == NULL)
    return;
    // __builtin_popcount는 현재 노드 데이터의 설정 비트 개수를 셉니다
    cout << "bits in node " << root->data << " = " <<__builtin_popcount(root->data)<< "
";
    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

이처럼 트리를 순회하면서 각 노드의 데이터에 대해 __builtin_popcount를 호출하면, 전위 순회(preorder traversal) 방식으로 모든 노드의 설정 비트 개수를 손쉽게 확인할 수 있습니다.