https://www.acmicpc.net/problem/15917
[C++] 주어진 숫자가 2의 제곱수인지 확인하기
알고리즘 문제에서 종종 주어진 수가 2의 제곱수($2^{n}$)인지 확인할 필요가 있다. 아래는 이를 위해 구현된 몇가지 예시들이다. while 문 사용 가장 쉽게 생각할 수 있는 방법 중 하나로 주어진 숫
velog.io
[비트 연산] 2진수를 활용한 여러가지 꼼수
이번 포스팅에서는 2진수의 특성과 비트연산을 활용해서 할수 있는 여러가지 프로그래밍적인 기법을 알아보겠다.성능을 위해서 실제로 우리가 작성한 코드를 컴파일러 수준에서 앞으로 배울
velog.io
https://www.acmicpc.net/problem/15917
비트 연산을 활용한 논리적 수학적 기법들
비트 연산은 컴퓨터 과학에서 매우 중요한 개념입니다. 비트 연산을 사용하면 수학적 계산을 더 빠르고 효율적으로 수행할 수 있습니다. 이번 글에서는 비트 연산을 논리적, 수학적으로 활용할 수 있는 여러 기법을 파이썬 예제와 함께 소개하겠습니다.
비트 연산자
파이썬에서는 여러 비트 연산자가 있습니다:
&(AND)|(OR)^(XOR)~(NOT)<<(Left Shift)>>(Right Shift)
1. 홀수와 짝수 판별
비트 연산자를 사용하면 홀수와 짝수를 빠르게 판별할 수 있습니다. 숫자의 마지막 비트가 1이면 홀수, 0이면 짝수입니다.
def is_even(n):
return n & 1 == 0
def is_odd(n):
return n & 1 == 1
# 테스트
print(is_even(4)) # True
print(is_odd(4)) # False
print(is_even(7)) # False
print(is_odd(7)) # True
2. 두 수를 XOR하여 서로 다른 비트 수 세기
두 수를 XOR하면 서로 다른 비트가 1이 됩니다. 이 결과에서 1의 개수를 세면 서로 다른 비트 수를 알 수 있습니다.
def count_different_bits(a, b):
xor = a ^ b
count = 0
while xor:
count += xor & 1
xor >>= 1
return count
# 테스트
print(count_different_bits(10, 15)) # 3
3. 비트 마스크를 사용한 특정 비트 설정
비트 마스크를 사용하면 특정 비트를 설정하거나 초기화할 수 있습니다.
def set_bit(n, position):
return n | (1 << position)
def clear_bit(n, position):
return n & ~(1 << position)
# 테스트
n = 0b1010
print(bin(set_bit(n, 1))) # 0b1010 (변화 없음)
print(bin(set_bit(n, 2))) # 0b1110
print(bin(clear_bit(n, 3))) # 0b10
4. 두 수의 교환
비트 연산을 사용하여 두 수를 임시 변수를 사용하지 않고 교환할 수 있습니다.
def swap(a, b):
a = a ^ b
b = a ^ b
a = a ^ b
return a, b
# 테스트
a, b = 5, 10
a, b = swap(a, b)
print(a, b) # 10 5
5. 가장 작은 2의 거듭제곱 찾기
어떤 수보다 크거나 같은 가장 작은 2의 거듭제곱을 찾을 수 있습니다.
def next_power_of_two(n):
if n == 0:
return 1
n -= 1
n |= n >> 1
n |= n >> 2
n |= n >> 4
n |= n >> 8
n |= n >> 16
n += 1
return n
# 테스트
print(next_power_of_two(5)) # 8
print(next_power_of_two(17)) # 32
6. 2의 거듭제곱 여부 확인
숫자가 2의 거듭제곱인지 확인하는 방법입니다. 2의 거듭제곱은 오직 하나의 비트만 1입니다.
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
# 테스트
print(is_power_of_two(16)) # True
print(is_power_of_two(18)) # False
7. 음수 판별
비트 연산을 사용하여 음수를 판별하는 방법도 간단합니다. 음수는 이진수 표현에서 가장 왼쪽 비트가 1입니다. 이 비트를 확인하여 음수를 판별할 수 있습니다.
def is_negative(n):
return (n >> (n.bit_length() - 1)) & 1 == 1
# 테스트
print(is_negative(-5)) # True
print(is_negative(5)) # False
8. n & -n == n의 의미
n & -n == n은 비트 연산에서 자주 사용되는 트릭입니다. 이 표현식의 의미를 이해하기 위해서는 -n이 어떻게 표현되는지를 이해해야 합니다.
2의 보수 표기법에서 음수는 양수의 비트를 모두 반전시키고 1을 더하여 표현됩니다. 예를 들어, n이 12라고 하면, 12의 이진 표현은 00001100입니다. 이를 비트 반전하면 11110011이 되고, 여기에 1을 더하면 11110100이 되어 -12를 나타냅니다.
따라서, n & -n은 n의 이진수에서 가장 오른쪽에 있는 1을 제외한 나머지 모든 비트를 0으로 만듭니다. 이는 n의 가장 오른쪽 비트 1을 찾는 데 사용됩니다.
def rightmost_set_bit(n):
return n & -n
# 테스트
print(bin(rightmost_set_bit(12))) # 0b100
print(bin(rightmost_set_bit(18))) # 0b10
9. 두 수의 평균 계산
비트 연산을 사용하여 두 수의 평균을 빠르게 계산할 수 있습니다. 이 방법은 오버플로를 방지하는 데 유용합니다.
def average(x, y):
return (x & y) + ((x ^ y) >> 1)
# 테스트
print(average(10, 20)) # 15
print(average(5, 7)) # 6
10. 모든 비트가 1인지 확인
주어진 숫자의 모든 비트가 1인지 확인하는 방법입니다.
def all_bits_set(n, bit_width):
return n == (1 << bit_width) - 1
# 테스트
print(all_bits_set(0b1111, 4)) # True
print(all_bits_set(0b1011, 4)) # False
11. 두 수의 차이 계산
비트 연산을 사용하여 두 수의 차이를 계산하는 방법입니다. 이 방법은 부호를 고려하여 차이를 계산합니다.
def subtract(x, y):
while y != 0:
borrow = (~x) & y
x = x ^ y
y = borrow << 1
return x
# 테스트
print(subtract(15, 10)) # 5
print(subtract(10, 15)) # -5
12. 비트 카운트 (1의 개수 세기)
비트 연산을 사용하여 주어진 숫자에서 1의 개수를 세는 방법입니다.
def count_set_bits(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
# 테스트
print(count_set_bits(15)) # 4 (0b1111)
print(count_set_bits(8)) # 1 (0b1000)
13. 두 수의 절대값 계산
비트 연산을 사용하여 두 수의 절대값을 빠르게 계산할 수 있습니다. 음수와 양수를 구분하는 비트 연산을 활용합니다.
def abs_val(n):
mask = n >> (n.bit_length() - 1)
return (n + mask) ^ mask
# 테스트
print(abs_val(-5)) # 5
print(abs_val(5)) # 5
14. 최소값과 최대값 구하기
비트 연산을 사용하여 두 수의 최소값과 최대값을 구할 수 있습니다.
def min_val(x, y):
return y ^ ((x ^ y) & -(x < y))
def max_val(x, y):
return x ^ ((x ^ y) & -(x < y))
# 테스트
print(min_val(10, 20)) # 10
print(max_val(10, 20)) # 20
15. 비트 반전 (1의 보수)
비트를 반전시키는 것은 모든 비트를 뒤집는 것을 의미합니다.
def bitwise_not(n, bit_width):
return ~n & ((1 << bit_width) - 1)
# 테스트
print(bin(bitwise_not(0b1010, 4))) # 0b0101
16. 가장 오른쪽에 있는 1의 위치 찾기
비트 연
산을 사용하여 가장 오른쪽에 있는 1의 위치를 찾을 수 있습니다.
def rightmost_set_bit_position(n):
if n == 0:
return 0
return (n & -n).bit_length()
# 테스트
print(rightmost_set_bit_position(18)) # 2 (0b10)
print(rightmost_set_bit_position(12)) # 3 (0b100)
17. n의 가장 높은 비트 위치 찾기
가장 높은 비트 위치를 찾는 방법입니다.
def highest_bit_position(n):
if n == 0:
return 0
position = 0
while n != 0:
position += 1
n >>= 1
return position
# 테스트
print(highest_bit_position(18)) # 5
print(highest_bit_position(12)) # 4
18. 비트 패리티 검사 (홀수/짝수 비트 1 개수 확인)
비트 패리티를 검사하여 1의 개수가 홀수인지 짝수인지를 확인할 수 있습니다.
def bit_parity(n):
parity = 0
while n:
parity = ~parity
n = n & (n - 1)
return parity & 1
# 테스트
print(bit_parity(7)) # 0 (0b111 -> 1의 개수는 3 -> 홀수)
print(bit_parity(5)) # 1 (0b101 -> 1의 개수는 2 -> 짝수)
19. 비트 회전 (로테이트)
비트를 좌우로 회전시키는 방법입니다.
def left_rotate(n, d, bit_width):
return (n << d % bit_width) | (n >> (bit_width - d % bit_width))
def right_rotate(n, d, bit_width):
return (n >> d % bit_width) | (n << (bit_width - d % bit_width)) & ((1 << bit_width) - 1)
# 테스트
n = 0b1011
print(bin(left_rotate(n, 2, 4))) # 0b1110
print(bin(right_rotate(n, 2, 4))) # 0b101
20. 두 수의 곱 계산 (곱셈 최적화)
비트 연산을 사용하여 두 수의 곱을 빠르게 계산하는 방법입니다. 이 방법은 특히 하나의 수가 2의 거듭제곱인 경우에 유용합니다.
def multiply(x, y):
result = 0
while y > 0:
if y & 1:
result += x
x <<= 1
y >>= 1
return result
# 테스트
print(multiply(3, 5)) # 15
print(multiply(7, 8)) # 56
21. 연속된 동일 구간 세기(1차원 edge 검출)
비트 연산을 사용하여 연속된 같은 숫자 구간의 개수를 빠르게 세는 방법을 설명하겠습니다. 여기서는 Python을 사용하여 이를 구현해 보겠습니다.
주어진 이진 문자열 00000011111111110000000000011111에서 연속된 '0' 또는 '1' 구간의 개수를 세는 방법을 다음과 같이 설명할 수 있습니다.
- 이진 문자열을 정수로 변환합니다.
- 해당 정수와 오른쪽으로 한 비트 이동한 값을 XOR 연산합니다.
- 결과에서 1의 개수를 셉니다.
- 최종적으로 1의 개수에 1을 더하면 구간의 개수가 나옵니다.
구현
다음은 Python 코드로 이를 구현한 예제입니다.
def count_segments(bit_string):
# 이진 문자열을 정수로 변환
num = int(bit_string, 2)
# 오른쪽으로 한 비트 이동한 값과 XOR 연산
xor_result = num ^ (num >> 1)
# XOR 결과에서 1의 개수 세기
segment_count = bin(xor_result).count('1')
# 구간의 개수는 1의 개수 + 1
return segment_count + 1
# 주어진 이진 문자열
bit_string = "00000011111111110000000000011111"
# 구간의 개수 세기
segment_count = count_segments(bit_string)
print(segment_count) # 결과 출력결론
비트 연산은 매우 강력한 도구로, 논리적 수학적 문제를 빠르고 효율적으로 해결할 수 있습니다. 다양한 비트 연산 기법을 통해 프로그램의 성능을 크게 향상시킬 수 있습니다. 이들 기법을 잘 활용하면 효율적인 코드를 작성할 수 있으며, 특히 고성능 컴퓨팅 및 최적화 문제를 해결하는 데 유용합니다.
