[백준 20360] Binary numbers (C#, C++) - soo:bak

문제 링크

20360번 - Binary numbers

설명

양의 정수 n의 이진 표현에서 값이 1인 비트의 위치를 모두 찾고, 최하위 비트를 0번으로 하여 오름차순으로 출력하는 문제입니다.

접근법

이진수에서 1인 비트 위치를 찾으려면 최하위 비트부터 차례로 검사하면 됩니다. n을 오른쪽으로 한 비트씩 시프트하면서 현재 최하위 비트가 1인지 확인하고, 1이면 해당 위치를 저장합니다.

n이 0이 될 때까지 반복하면 모든 1인 비트 위치를 오름차순으로 얻을 수 있습니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var pos = new List<int>();
    var idx = 0;
    while (n > 0) {
      if ((n & 1) == 1) pos.Add(idx);
      n >>= 1;
      idx++;
    }
    Console.WriteLine(string.Join(" ", pos));
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;

  vi pos;
  int idx = 0;
  while (n > 0) {
    if (n & 1) pos.push_back(idx);
    n >>= 1;
    idx++;
  }

  for (int i = 0; i < (int)pos.size(); i++) {
    if (i) cout << ' ';
    cout << pos[i];
  }
  cout << "\n";

  return 0;
}