비트연산
-
백준 1094 막대기 (비트 개수 세기)Algorithm/BOJ 2021. 6. 3. 15:31
출처: https://www.acmicpc.net/problem/1094 분류: 비트마스킹 접근방식 주어진 문제의 조건을 맹목적으로 따라서 풀 수도 있지만, 조건을 해보면 결국은 주어진 x를 몇 개의 2의 배수를 사용해 만들 수 있느냐 하는 문제입니다. 다시 생각해보면 "x를 이진수로 만들었을 때 1이 몇 개냐" 라는 말과 같은 말이라는 걸 알 수 있습니다 :) 따라서 이진수에서 1이 몇 개인지 세는 방법을 알아보겠습니다. 2로 나누기 우선 비트 연산을 하지 않는다면 주어진 수를 x로 나눠가면서 셀 수가 있겠네요. 중학생(?)때 배우는 10진수를 2진수로 바꿀 때 나눠가면서 나머지를 세는 바로 그 방식입니다. while x > 0 { bitCount += x % 2 x /= 2 } >> 1 2로 나누는 ..