비트 연산을 활용한 비트 마스킹(BitMask) feat. kotlin
컴퓨터 과학에서 마스크 또는 비트마스크는 비트 필드의 비트 연산에 특별히 사용되는 데이터입니다
컴퓨터의 CPU에서 실제 연산이 이루어지는 비트연산을 통하여 어떤 상태를 숫자로 표현한다.
예) 세명의 사람의 식사를 한다고 하자. 이때, 한식과 양식 둘 중 하나만 주문할 수 있다.
첫번째 사람은 양식, 두번째 사람은 한식, 세번째 사람은 양식을 골랐다고 하면,
한식 = 0 , 양식 = 1이라 생각을 해보자.
첫번째 사람 = 1
두번째 사람 = 0
세번째 사람 = 1
1 0 1(2) = 5
즉, 사람마다 선택한 식사를 정수 = 5, 이진수 101로 표현 가능하다.
비트연산을 통하여 이 상태를 표현, 변경, 확인 하는것을 비트마스킹이라 한다.
* Java 및 kotlin에서는 Int(정수) type을 저장하기 위해서 4byte(32bit)를 사용한다.
MSB(맨 앞에 비트는 음/양수를 표현을 위한 비트)로 제외하고,
MSB가 0인
0 ~ 2147483647 0을 포함한 양수까지를 활용 하여 총 31개의 비트로 최대 2147483647 가지의 경우의수를 표현 가능하다.
0000 0000 0000 0000 0000 0000 0000 0101 => 5
0111 1111 1111 1111 1111 1111 1111 1111 = 2147483647
0. 1<< n , 1 shl n
1을 n번 왼쪽으로 이동시킴
즉. 1에 곱하기 2^(n-1)
fun main() {
println("${1 shl 0} --> 2진수: ${Integer.toBinaryString(1 shl 0)}")
println("${1 shl 1} --> 2진수: ${Integer.toBinaryString(1 shl 1)}")
println("${1 shl 2} --> 2진수: ${Integer.toBinaryString(1 shl 2)}")
println("${1 shl 3} --> 2진수: ${Integer.toBinaryString(1 shl 3)}")
}
* 모든 비트가 켜진 상태를 만들고 싶다면,
1 shl n - 1
fun main() {
println("(1 shl 1) - 1 --> 2진수: ${Integer.toBinaryString((1 shl 1) - 1)}")
println("(1 shl 2) - 1 --> 2진수: ${Integer.toBinaryString((1 shl 2) - 1)}")
println("(1 shl 3) - 1 --> 2진수: ${Integer.toBinaryString((1 shl 3) - 1)}")
println("(1 shl 4) - 1 --> 2진수: ${Integer.toBinaryString((1 shl 4) - 1)}")
}
1. 특정 비트의 상태가 1(On)인지 확인한다.
87 --> 1010111(2) 의 특정 자릿수 비트가 켜져있는지 꺼져있는 확인하고 싶다면
1 << i - 1 과 AND 연산의 성질(두개다 1이면 1이다 아니면 전부 0)을 통해 확인 가능하다.
특정 자릿수 만큼 1인 비트를 이동시켜서 연산후 결과가 전부 0이면 꺼져있고 아니면 켜져있다.
101111 & 001000 = 001000
fun isOn(n: Int) {
for (i in 1..7) {
if (n and (1 shl i - 1) == 0)
println("$i 번째 비트는 0(off)")
else
println("$i 번째 비트는 1(on)")
}
}
fun main() {
isOn("1010111".toInt(2))
}
2. 특정 자릿수 비트를 1(On) 상태로 만든다. (이미 1(On)이면 그대로 1(On))
or 연산의 성질 (하나라도 1이면 1이다)을 이용하여,
특정 자릿수 만큼 1인 비트를 이동시켜서 연산후 결과는 무조건 1이다.
fun on(n: Int, idx: Int): Int {
val temp = n or (1 shl idx - 1)
println("결과 ${Integer.toBinaryString(temp)}")
return temp
}
fun main() {
on("100101".toInt(2),5)
}3. 특정 자릿수 비트를 1(Off) 상태로 만든다. (이미 1(Off)이면 그대로 1(Off))
1 << i - 1 을 반전시킨 후 AND 연산의 성질(두개다 1이면 1이다 아니면 전부 0)을 통해 확인 가능하다.
특정 자릿수 만큼 1인 비트를 이동시켜서 연산후 결과가 전부 0이면 꺼져있고 아니면 켜져있다.
fun off(n: Int, idx: Int): Int {
val temp = n and (1 shl idx - 1).inv()
println("결과 ${Integer.toBinaryString(temp)}")
return temp
}
fun main() {
off("10010101".toInt(2), 3)
}
4. 특정 자릿수 비트를 반대로 바꾼다. 1 -> 0, 0 -> 1
xor 연산의 성질 (두 비트가 같으면 1 다르면 0)을 이용하여,
0 xor 1 = 1
1 xor 1 = 0
0 xor 0 = 0
1 xor 0 = 1
1하고 xor 연산을 하면, 피연산자는 반전됨 -> 이 성질을 이용함
0하고 xor 연산을 하면, 피연산자는 변하지 않음. -> 다른자릿수는 문제 없음
fun reverse(n: Int, idx: Int): Int {
val temp = n xor (1 shl idx - 1)
println("결과 ${Integer.toBinaryString(temp)}")
return temp
}
fun main() {
reverse("100101".toInt(2), 5)
reverse("100101".toInt(2), 3)
}
5. 모든 비트를 뒤집기
19 -> 0000 0000 0000 0000 0000 0000 0001 0011
1. 반전시키려는 숫자의 2진수 자릿수 만큼 전부 1인 수를 만든다.
(1 shl k) - 1
31 -> 0000 0000 0000 0000 0000 0000 0001 1111
NOT 19 -> 1111 1111 1111 1111 1111 1111 1110 1100
AND 연산을 하면 성질상 모든 비트가 반전된 정수가 된다.
fun allReverse(n: Int, k: Int): Int {
val a = (1 shl k) - 1
return a and n.inv()
}
fun main() {
println("10011 --> ${Integer.toBinaryString(allReverse("10011".toInt(2), 5))}")
println("111 --> ${Integer.toBinaryString(allReverse("111".toInt(2), 3))}")
}6. 최초로 1인 비트 찾기.
100100 에서 최초로 1이 나오는건 3번째 비트이다.
N = 36
2의 보수의 음수 표현에 따라서
N.inv() + 1 = -N
fun main() {
println("${Integer.toBinaryString(36.inv() + 1)}")
println("${Integer.toBinaryString(-36)}")
}
36 -> 0000 0000 0000 0000 0000 0000 0010 0100
-36 -> 1111 1111 1111 1111 1111 1111 1101 1100
이둘을 AND 연산을 하면, 4 --> 100 가 반환됨.
fun findFirstOnBit(n: Int): Int {
val temp = n and -n
println("결과 ${Integer.toBinaryString(temp)}")
return temp
}
fun main() {
findFirstOnBit("100100".toInt(2))
findFirstOnBit("1001001".toInt(2))
findFirstOnBit("10000".toInt(2))
}